Subgraph isomorphism in graph classes

DOI10.1016/j.disc.2012.07.010zbMath1251.05109OpenAlexW2032950096WikidataQ29031096 ScholiaQ29031096MaRDI QIDQ456655

Takeaki Uno, Yota Otachi, Shuji Kijima, Toshiki Saitoh

Publication date: 16 October 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2012.07.010

zbMATH Keywords

graph algorithmNP-completenesssubgraph isomorphismgraph class

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

Finding a chain graph in a bipartite permutation graph, Algorithmic problems in right-angled Artin groups: complexity and applications, Streaming deletion problems Parameterized by vertex cover, Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs, A time-based solution for the graph isomorphism problem, Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs, Induced subgraph isomorphism on proper interval and bipartite permutation graphs, Subgraph isomorphism on graph classes that exclude a substructure, Notes on integer partitions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random generation and enumeration of bipartite permutation graphs
• The complexity of subgraph isomorphism for classes of partial k-trees
• Bandwidth of bipartite permutation graphs in polynomial time
• The subgraph isomorphism problem for outerplanar graphs
• Finding Hamiltonian circuits in interval graphs
• Hamiltonian circuits in interval graph generalizations
• Complement reducible graphs
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• A short proof that `proper = unit'
• Efficient graph representations
• Cleaning interval graphs
• A structure theorem for the consecutive 1's property
• Induced Subgraph Isomorphism on Interval and Proper Interval Graphs
• Planar Subgraph Isomorphism Revisited
• Computing the Bandwidth of Interval Graphs
• Bandwidth of Bipartite Permutation Graphs
• The NP-completeness column: an ongoing guide
• On testing isomorphism of permutation graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Graph Classes: A Survey
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Ordered and Unordered Tree Inclusion