|
Maximum Common Edge Subgraph Problem
Given two graphs G and G', the maximum common edge subgraph problem is the problem of finding a graph H with as many edges as possible which is isomorphic to both a subgraph of G and a subgraph of G'. The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism: a graph H is isomorphic to a subgraph of another graph G if and only if the maximum common edge subgraph of G and H has the same number of edges as H. Unless the two inputs G and G' to the maximum common edge subgraph problem are required to have the same number of vertices, the problem is APX-hard.. See also * Maximum common subgraph isomorphism problem *Subgraph isomorphism problem *Induced subgraph isomorphism problem In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph. Problem statement Formally, the problem takes as input t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph (discrete Mathematics)
In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a Set (mathematics), set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') and each of the related pairs of vertices is called an ''edge'' (also called ''link'' or ''line''). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics. The edges may be directed or undirected. For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person ''A'' can shake hands with a person ''B'' only if ''B'' also shakes hands with ''A''. In contrast, if an edge from a person ''A'' to a person ''B'' m ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Isomorphism
In graph theory, an isomorphism of graphs ''G'' and ''H'' is a bijection between the vertex sets of ''G'' and ''H'' : f \colon V(G) \to V(H) such that any two vertices ''u'' and ''v'' of ''G'' are adjacent in ''G'' if and only if f(u) and f(v) are adjacent in ''H''. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as G\simeq H. In the case when the bijection is a mapping of a graph onto itself, i.e., when ''G'' and ''H'' are one and the same graph, the bijection is called an automorphism of ''G''. If a graph is finite, we can prove it to be bijective by showing it is one-one/onto; no need to show both. Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Glossary Of Graph Theory
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges. Symbols A B C D E F G H I K L M N O ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-complete
In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. # the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified. The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a de ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Subgraph Isomorphism
In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs ''G'' and ''H'' are given as input, and one must determine whether ''G'' contains a subgraph that is isomorphic to ''H''. Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time. Sometimes the name subgraph matching is also used for the same problem. This name puts emphasis on finding such a subgraph as opposed to the bare decision problem. Decision problem and computational complexity To prove subgraph isomorphism is NP-complete, it must be formulated as a decision problem. The input to the decision problem is a pair of graphs ''G'' and ''H''. The answer to the problem is positive if ''H'' is isomorphic to a subgraph of ''G'', and negative otherwise. Formal question: ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
APX-hard
In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor approximation algorithms for short). In simple terms, problems in this class have efficient algorithms that can find an answer within some fixed multiplicative factor of the optimal answer. An approximation algorithm is called an f(n)-approximation algorithm for input size n if it can be proven that the solution that the algorithm finds is at most a multiplicative factor of f(n) times worse than the optimal solution. Here, f(n) is called the ''approximation ratio''. Problems in APX are those with algorithms for which the approximation ratio f(n) is a constant c. The approximation ratio is conventionally stated greater than 1. In the case of minimization problems, f(n) is the found solution's score divided by the optimum solution's score, whi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Maximum Common Subgraph Isomorphism Problem
In graph theory and theoretical computer science, a maximum common subgraph may mean either: *Maximum common induced subgraph In graph theory and theoretical computer science, a maximum common induced subgraph of two graphs ''G'' and ''H'' is a graph that is an induced subgraph of both ''G'' and ''H'', and that has as many vertices as possible. Finding this graph is NP-ha ..., a graph that is an induced subgraph of two given graphs and has as many vertices as possible * Maximum common edge subgraph, a graph that is a subgraph of two given graphs and has as many edges as possible {{sia ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Subgraph Isomorphism Problem
In theoretical computer science, the subgraph isomorphism problem is a computational task in which two graphs ''G'' and ''H'' are given as input, and one must determine whether ''G'' contains a subgraph that is isomorphic to ''H''. Subgraph isomorphism is a generalization of both the maximum clique problem and the problem of testing whether a graph contains a Hamiltonian cycle, and is therefore NP-complete. However certain other cases of subgraph isomorphism may be solved in polynomial time. Sometimes the name subgraph matching is also used for the same problem. This name puts emphasis on finding such a subgraph as opposed to the bare decision problem. Decision problem and computational complexity To prove subgraph isomorphism is NP-complete, it must be formulated as a decision problem. The input to the decision problem is a pair of graphs ''G'' and ''H''. The answer to the problem is positive if ''H'' is isomorphic to a subgraph of ''G'', and negative otherwise. Formal question: ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Induced Subgraph Isomorphism Problem
In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph. Problem statement Formally, the problem takes as input two graphs ''G''1=(''V''1, ''E''1) and ''G''2=(''V''2, ''E''2), where the number of vertices in ''V''1 can be assumed to be less than or equal to the number of vertices in ''V''2. ''G''1 is isomorphic to an induced subgraph of ''G''2 if there is an injective function ''f'' which maps the vertices of ''G''1 to vertices of ''G''2 such that for all pairs of vertices ''x'', ''y'' in ''V''1, edge (''x'', ''y'') is in ''E''1 if and only if the edge (''f''(''x''), ''f''(''y'')) is in ''E''2. The answer to the decision problem is yes if this function ''f'' exists, and no otherwise. This is different from the subgraph isomorphism problem in that the absence of an edge in ''G''1 implies that the corresponding edge in ''G''2 must also be absent. In subgraph i ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
