Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
From MaRDI portal
Publication:896655
DOI10.1016/j.dam.2015.01.040zbMath1326.05095MaRDI 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
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C17: Perfect graphs
05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
Related Items
Subgraph isomorphism on graph classes that exclude a substructure, Streaming deletion problems Parameterized by vertex cover, Finding a chain graph in a bipartite permutation graph, Families of nested graphs with compatible symmetric-group actions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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"
