A new representation of proper interval graphs with an application to clique-width

DOI10.1016/J.ENDM.2009.02.005MaRDI QIDQ2839207zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Daniel Meister, Charis Papadopoulos

Publication date 4 July 2013

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.endm.2009.02.005

zbMATH Keywords

clique-widthproper interval graphsrepresentation model

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Bounded representations of interval and proper interval graphs
• Exploiting Restricted Linear Structure to Cope with the Hardness of Clique-Width
• A linear-time algorithm for proper interval graph recognition
• Clique-width of full bubble model graphs
• The clique-separator graph for chordal graphs

Cites work

• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A linear time recognition algorithm for proper interval graphs
• A linear-time algorithm for proper interval graph recognition
• A new representation of proper interval graphs with an application to clique-width
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic graph theory and perfect graphs
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Clique-width minimization is NP-hard
• Efficient graph representations
• Graph Classes: A Survey
• Handle-rewriting hypergraph grammars
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• On the Relationship Between Clique-Width and Treewidth
• On the clique-width of some perfect graph classes
• Optimal greedy algorithms for indifference graphs
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• Simple linear time recognition of unit interval graphs
• Upper bounds to the clique width of graphs

Cited in

(18)

• Bounded representations of interval and proper interval graphs
• A new representation of proper interval graphs with an application to clique-width
• Complexity of maximum cut on interval graphs
• On the m-clique free interval subgraphs polytope: polyhedral analysis and applications
• On the thinness and proper thinness of a graph
• The complexity of the defensive domination problem in special graph classes
• Dynamic algorithms for monotonic interval scheduling problem
• U-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• Probe interval and probe unit interval graphs on superclasses of cographs
• Clique-width of full bubble model graphs
• Economic genome assembly from low coverage illumina and nanopore data
• On the maximum cardinality cut problem in proper interval graphs and related graph classes
• \(\mathcal{U}\)-bubble model for mixed unit interval graphs and its applications: the MaxCut problem revisited
• Defensive domination in proper interval graphs
• A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
• A matrix characterization of interval and proper interval graphs
• scientific article; zbMATH DE number 1439435 (Why is no real title available?)
• Tuza's Conjecture for Threshold Graphs

This page was built for publication: A new representation of proper interval graphs with an application to clique-width

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