iPedia Free Information Center

Information about Substructure Search

In complexity theory, Subgraph-Isomorphism is a decision problem that is known to be NP-complete. The formal description of the decision problem is as follows.

Subgraph-Isomorphism(G1, G2)
Input: Two graphs G1 and G2.
Question: Is G1 isomorphic to a subgraph of G2?

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.

Subgraph isomorphism is a generalization of the potentially easier graph isomorphism problem; if the graph isomorphism problem is NP-complete, the polynomial hierarchy collapses, so it is suspected not to be.

Application areas

In the area of cheminformatics often the term substructure search is used. Typically a query structure is defined as SMARTS, a SMILES extension.

Also of main importance to graph grammars.

See also

References

As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g.
..... Click the link for more information.
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem.
..... Click the link for more information.
In complexity theory, the NP-complete problems are the most difficult problems in NP ("non-deterministic polynomial time") in the sense that they are the smallest subclass of NP that could conceivably remain outside of P, the class of deterministic polynomial-time problems.
..... Click the link for more information.
graph theory is the study of graphs; mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges
..... Click the link for more information.
In graph theory, a graph isomorphism is a bijection (a one-to-one and onto mapping) between the vertices of two graphs G and H
with the property that any two vertices u and v from G are adjacent if and only if
..... Click the link for more information.
In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.

Definitions

There are multiple equivalent definitions of the classes of the polynomial hierarchy.
..... Click the link for more information.
Cheminformatics (also known as chemoinformatics and chemical informatics) is the use of computer and informational techniques, applied to a range of problems in the field of chemistry.
..... Click the link for more information.
Query languages are computer languages used to make queries into databases and information systems.

Broadly, query languages can be classified according to whether they are database query languages or information retrieval query languages. Examples include:
  • .

..... Click the link for more information.
smile is a facial expression formed by flexing the muscles most notably near both ends of the mouth. The smile can be also around the eyes. Among humans, it's customarily an expression of pleasure, happiness, or amusement, but can also be an involuntary expression of anxiety, in
..... Click the link for more information.
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.
..... Click the link for more information.
In complexity theory, Maximum Common Subgraph-Isomorphism (MCS) is an optimization problem that is known to be NP-hard. The formal description of the problem is as follows:

Maximum Common Subgraph-Isomorphism(G1, G2)
  • Input: Two graphs G

..... Click the link for more information.
Journal of the ACM (JACM) is the leading scientific journal of the Association for Computing Machinery (ACM) in the broad area of computer science. It was started in 1954.
..... Click the link for more information.
Michael R. Garey is a computer science researcher, and co-author (with David S. Johnson) of Computers and Intractability: A Guide to the Theory of NP-completeness. In 1995 he was inducted as a Fellow of the Association for Computing Machinery.

Garey's personal web page
..... Click the link for more information.
David Stifler Johnson (born December 9, 1945) is a computer scientist specializing in algorithms and optimization. He is currently the head of the Algorithms and Optimization Department of AT&T Labs Research.
..... Click the link for more information.


This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus


page counter