Induced subgraph isomorphism on proper interval and bipartite permutation graphs

DOI10.1016/j.tcs.2014.10.002zbMath1303.68060OpenAlexW2079856162MaRDI QIDQ476868

Daniel Meister, Pinar Heggernes, Yngve Villanger, Pim van 't Hof

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.10.002

zbMATH Keywords

induced subgraphsisomorphismpolynomial-timefixed-parameter tractable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (13)

FO model checking on geometric graphs ⋮ Labelled well-quasi-order for permutation classes ⋮ On the complexity of various parameterizations of common induced subgraph isomorphism ⋮ Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Critical properties of bipartite permutation graphs ⋮ Unnamed Item ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Unnamed Item ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Unnamed Item ⋮ Combinatorics and algorithms for quasi-chain graphs ⋮ Improved Hardness of Maximum Common Subgraph Problems on Labeled Graphs of Bounded Treewidth and Bounded Degree ⋮ Linear-time recognition of double-threshold graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Edge contractions in subclasses of chordal graphs
• Subgraph isomorphism in graph classes
• Simple linear time recognition of unit interval graphs
• The clique-separator graph for chordal graphs
• The subgraph isomorphism problem for outerplanar graphs
• Bipartite permutation graphs
• Modular decomposition and transitive orientation
• Algorithmic graph theory and perfect graphs
• Cleaning interval graphs
• Optimal greedy algorithms for indifference graphs
• Induced Subgraph Isomorphism on Interval and Proper Interval Graphs
• Domination on Cocomparability Graphs
• Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
• Subtree Isomorphism in O(n5/2)
• Graph Classes: A Survey
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs

This page was built for publication: Induced subgraph isomorphism on proper interval and bipartite permutation graphs