Subgraph isomorphism in graph classes

DOI10.1016/J.DISC.2012.07.010MaRDI QIDQ456655zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno

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

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

Recommendations

• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
• The complexity of subgraph isomorphism for classes of partial k-trees
• Induced subgraph isomorphism on interval and proper interval graphs
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3919840 (Why is no real title available?)
• scientific article; zbMATH DE number 3963193 (Why is no real title available?)
• scientific article; zbMATH DE number 139780 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A short proof that `proper = unit'
• A structure theorem for the consecutive 1's property
• Bandwidth of Bipartite Permutation Graphs
• Bandwidth of bipartite permutation graphs in polynomial time
• Cleaning interval graphs
• Complement reducible graphs
• Computing the Bandwidth of Interval Graphs
• Efficient graph representations
• Finding Hamiltonian circuits in interval graphs
• Graph Classes: A Survey
• Hamiltonian circuits in interval graph generalizations
• Induced subgraph isomorphism on interval and proper interval graphs
• Linear-time certifying recognition algorithms and forbidden induced subgraphs
• On testing isomorphism of permutation graphs
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Ordered and Unordered Tree Inclusion
• Planar subgraph isomorphism revisited
• Random generation and enumeration of bipartite permutation graphs
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The NP-completeness column: an ongoing guide
• The complexity of subgraph isomorphism for classes of partial k-trees
• The subgraph isomorphism problem for outerplanar graphs

Cited in

(21)

• The subgraph isomorphism problem on a class of hyperedge replacement languages
• scientific article; zbMATH DE number 1974109 (Why is no real title available?)
• scientific article; zbMATH DE number 889957 (Why is no real title available?)
• scientific article; zbMATH DE number 4043266 (Why is no real title available?)
• Finding a chain graph in a bipartite permutation graph
• Algorithmic problems in right-angled Artin groups: complexity and applications
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• Notes on integer partitions
• Induced subgraph isomorphism on interval and proper interval graphs
• Computing and Drawing Isomorphic Subgraphs
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Induced subtrees in interval graphs
• Graph isomorphism for graph classes characterized by two forbidden induced subgraphs
• Filtering for Subgraph Isomorphism
• Subgraph isomorphism on graph classes that exclude a substructure
• Subgraph isomorphism on graph classes that exclude a substructure
• scientific article; zbMATH DE number 6770116 (Why is no real title available?)
• Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs
• A time-based solution for the graph isomorphism problem
• Efficient non-isomorphic graph enumeration algorithms for several intersection graph classes
• Streaming deletion problems Parameterized by vertex cover

This page was built for publication: Subgraph isomorphism in graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q456655)