Induced subgraph isomorphism on interval and proper interval graphs

DOI10.1007/978-3-642-17514-5_34MaRDI QIDQ3060791zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Daniel Meister, Yngve Villanger

Publication date 9 December 2010

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17514-5_34

Mathematics Subject Classification ID

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

Recommendations

• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Induced subtrees in interval graphs
• Cleaning interval graphs
• Subgraph isomorphism in graph classes
• Understanding the Complexity of Induced Subgraph Isomorphisms

Cited in

(11)

• Parameterized graph cleaning problems
• Edge contractions in subclasses of chordal graphs
• Subgraph isomorphism in graph classes
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• Parameterized Graph Cleaning Problems
• Induced subgraph isomorphism on proper interval and bipartite permutation graphs
• Induced subtrees in interval graphs
• Understanding the Complexity of Induced Subgraph Isomorphisms
• Parameterized complexity of induced graph matching on claw-free graphs
• Cleaning interval graphs
• Edge contractions in subclasses of chordal graphs

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

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