Subgraph Isomorphism, log-Bounded Fragmentation and Graphs of (Locally) Bounded Treewidth.
Mohammad Taghi HajiaghayiNaomi NishimuraPublished in: MFCS (2002)
Keyphrases
- bounded treewidth
- subgraph isomorphism
- np complete
- graph matching
- maximum common subgraph
- graph isomorphism
- graph databases
- conjunctive queries
- search tree
- decision problems
- edit distance
- graph mining
- boolean functions
- weighted graph
- relational learning
- computational complexity
- graph data
- graph patterns
- frequent subgraphs
- constraint satisfaction problems
- bounded degree
- pairwise
- query answering
- data exchange
- depth first search
- information extraction
- np hard