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

DOI10.1016/j.dam.2015.01.040zbMath1326.05095OpenAlexW1971319751MaRDI QIDQ896655

Yota Otachi, Matsuo Konagaya, 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

NP-completenesspolynomial-time algorithmsubgraph isomorphismgraph class

Mathematics Subject Classification ID

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

Related Items (4)

Finding a chain graph in a bipartite permutation graph ⋮ Streaming deletion problems Parameterized by vertex cover ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Families of nested graphs with compatible symmetric-group actions

Cites Work

• Edge contractions in subclasses of chordal graphs
• Subgraph isomorphism in graph classes
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• The complexity of subgraph isomorphism for classes of partial k-trees
• Containment relations in split graphs
• The subgraph isomorphism problem for outerplanar graphs
• The ellipsoid method and its consequences in combinatorial optimization
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Efficient graph representations
• The maximum edge biclique problem is NP-complete
• Finding maximum edge bicliques in convex bipartite graphs
• Subgraph isomorphism for biconnected outerplanar graphs in cubic time
• Algorithmic graph theory and perfect graphs
• Quasi-threshold graphs
• Cleaning interval graphs
• Linear structure of bipartite permutation graphs and the longest path problem
• Everything you always wanted to know about the parameterized complexity of Subgraph Isomorphism (but were afraid to ask).
• Induced Subgraph Isomorphism on Interval and Proper Interval Graphs
• Planar Subgraph Isomorphism Revisited
• On testing isomorphism of permutation graphs
• Subtree Isomorphism in O(n5/2)
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Graph Classes: A Survey
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
• A Note on "The Comparability Graph of a Tree"
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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