Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth

DOI10.1016/j.jcss.2007.01.003zbMath1115.68114OpenAlexW2000945011MaRDI QIDQ881594

Naomi Nishimura, Mohammad Taghi Hajiaghayi

Publication date: 30 May 2007

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.01.003

zbMATH Keywords

treewidthsubgraph isomorphismlocally-bounded treewidthlog-bounded-fragmentation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Parameterized Graph Cleaning Problems, Cleaning interval graphs, Probabilistic and exact frequent subtree mining in graphs beyond forests, A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree, Unnamed Item, Parameterized graph cleaning problems, Efficient frequent connected subgraph mining in graphs of bounded tree-width, Subgraph isomorphism on graph classes that exclude a substructure, Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of subgraph isomorphism for classes of partial k-trees
• The subgraph isomorphism problem for outerplanar graphs
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• A partial k-arboretum of graphs with bounded treewidth
• A note on the bounded fragmentation property and its applications in network reliability
• Diameter and treewidth in minor-closed graph families
• Faster algorithms for subgraph isomorphism of \(k\)-connected partial \(k\)-trees
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Maximum packing for \(k\)-connected partial \(k\)-trees in polynomial time
• Local tree-width, excluded minors, and approximation algorithms
• On Graph Powers for Leaf-Labeled Trees
• Deciding first-order properties of locally tree-decomposable structures
• Easy problems for tree-decomposable graphs
• Characterization and Recognition of Partial 3-Trees
• Graph minors. II. Algorithmic aspects of tree-width
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Subtree Isomorphism in O(n5/2)
• Approximation algorithms for NP-complete problems on planar graphs
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Linear-time computation of optimal subgraphs of decomposable graphs
• On Linear Recognition of Tree-Width at Most Four
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth