Induced subgraph isomorphism on proper interval and bipartite permutation graphs
DOI10.1016/J.TCS.2014.10.002zbMATH Open1303.68060OpenAlexW2079856162MaRDI QIDQ476868FDOQ476868
Authors: Pinar Heggernes, Daniel Meister, 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
Recommendations
- Induced subgraph isomorphism on interval and proper interval graphs
- Subgraph isomorphism in graph classes
- Induced subtrees in interval graphs
- Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
- Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
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)
Cites Work
- Title not available (Why is that?)
- Graph Classes: A Survey
- Modular decomposition and transitive orientation
- Algorithmic graph theory and perfect graphs
- Optimal greedy algorithms for indifference graphs
- Domination on Cocomparability Graphs
- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
- Simple linear time recognition of unit interval graphs
- Title not available (Why is that?)
- Bipartite permutation graphs
- Title not available (Why is that?)
- Subgraph isomorphism in graph classes
- The clique-separator graph for chordal graphs
- Subgraph Isomorphism in Planar Graphs and Related Problems
- Induced subgraph isomorphism on interval and proper interval graphs
- Edge contractions in subclasses of chordal graphs
- The subgraph isomorphism problem for outerplanar graphs
- Cleaning interval graphs
- Subtree Isomorphism in O(n5/2)
Cited In (16)
- Critical properties of bipartite permutation graphs
- Linear-time recognition of double-threshold graphs
- Subgraph isomorphism in graph classes
- FO model checking on geometric graphs
- Simultaneous representation of proper and unit interval graphs
- FO model checking of geometric graphs
- Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
- Labelled well-quasi-order for permutation classes
- Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree
- Induced subgraph isomorphism on interval and proper interval graphs
- Combinatorics and algorithms for quasi-chain graphs
- Combinatorics and algorithms for quasi-chain graphs
- Induced subtrees in interval graphs
- Parameterized complexity of induced graph matching on claw-free graphs
- Title not available (Why is that?)
- Cleaning interval graphs
This page was built for publication: Induced subgraph isomorphism on proper interval and bipartite permutation graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476868)
