Induced subgraph isomorphism on proper interval and bipartite permutation graphs

DOI10.1016/J.TCS.2014.10.002MaRDI QIDQ476868zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

induced subgraphsisomorphismpolynomial-timefixed-parameter tractable

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)

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

Cites work

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

Cited in

(16)

• Critical properties of bipartite permutation graphs
• Subgraph isomorphism in graph classes
• FO model checking on geometric graphs
• Linear-time recognition of double-threshold graphs
• Simultaneous representation of proper and unit interval graphs
• Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs
• FO model checking of geometric 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
• Induced subtrees in interval graphs
• Combinatorics and algorithms for quasi-chain graphs
• Combinatorics and algorithms for quasi-chain graphs
• Parameterized complexity of induced graph matching on claw-free graphs
• scientific article; zbMATH DE number 7765365 (Why is no real title available?)
• 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)