Induced Subgraph Isomorphism on Interval and Proper Interval Graphs

DOI10.1007/978-3-642-17514-5_34zbMath1310.68109OpenAlexW1533352539MaRDI QIDQ3060791

Daniel Meister, Pinar Heggernes, 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) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (6)

Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs ⋮ Edge contractions in subclasses of chordal graphs ⋮ Subgraph isomorphism in graph classes ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ Parameterized complexity of induced graph matching on claw-free graphs ⋮ Edge Contractions in Subclasses of Chordal Graphs

This page was built for publication: Induced Subgraph Isomorphism on Interval and Proper Interval Graphs