Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs

DOI10.1016/J.DAM.2015.01.040MaRDI QIDQ896655zbMATH OpenOpenAlexFDO

Authors Matsuo Konagaya, Yota Otachi, Ryuhei Uehara

Publication date 10 December 2015

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

Full work available at URL https://doi.org/10.1016/j.dam.2015.01.040

zbMATH Keywords

graph classNP-completenesspolynomial-time algorithmsubgraph isomorphism

Mathematics Subject Classification ID

Perfect graphs (05C17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
• Subgraph isomorphism in graph classes
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Induced subgraph isomorphism on interval and proper interval graphs
• scientific article; zbMATH DE number 4072379

Cites work

• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• A Note on "The Comparability Graph of a Tree"
• Algorithmic graph theory and perfect graphs
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• Cleaning interval graphs
• Containment relations in split graphs
• Edge contractions in subclasses of chordal graphs
• Efficient graph representations
• Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask)
• Finding maximum edge bicliques in convex bipartite graphs
• Graph Classes: A Survey
• 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 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 1156661 (Why is no real title available?)
• scientific article; zbMATH DE number 2191997 (Why is no real title available?)
• Induced subgraph isomorphism on interval and proper interval graphs
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Linear structure of bipartite permutation graphs and the longest path problem
• 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
• Planar subgraph isomorphism revisited
• Quasi-threshold graphs
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Subgraph isomorphism in graph classes
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Subtree Isomorphism in O(n5/2)
• The complexity of subgraph isomorphism for classes of partial k-trees
• The ellipsoid method and its consequences in combinatorial optimization
• The maximum edge biclique problem is NP-complete
• The subgraph isomorphism problem for outerplanar graphs

Cited in

(7)

• Families of nested graphs with compatible symmetric-group actions
• Finding a chain graph in a bipartite permutation graph
• Subgraph isomorphism in graph classes
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
• Subgraph isomorphism on graph classes that exclude a substructure
• Streaming deletion problems Parameterized by vertex cover

This page was built for publication: Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs

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