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

DOI10.1016/j.endm.2009.02.005zbMath1267.05176OpenAlexW1966894219MaRDI QIDQ2839207

Daniel Meister, Pinar Heggernes, 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)

Related Items

Tuza's Conjecture for Threshold Graphs, Complexity of maximum cut on interval graphs, Defensive domination in proper interval graphs, Dynamic algorithms for monotonic interval scheduling problem, A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs, Unnamed Item, The complexity of the defensive domination problem in special graph classes, 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, A new representation of proper interval graphs with an application to clique-width, Clique-width of full bubble model graphs

Cites Work

• Unnamed Item
• A linear-time algorithm for proper interval graph recognition
• Simple linear time recognition of unit interval graphs
• A linear time recognition algorithm for proper interval graphs
• Efficient graph representations
• Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• Algorithmic graph theory and perfect graphs
• Upper bounds to the clique width of graphs
• Optimal greedy algorithms for indifference graphs
• Handle-rewriting hypergraph grammars
• A new representation of proper interval graphs with an application to clique-width
• Clique-width minimization is NP-hard
• Graph Classes: A Survey
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the Relationship Between Clique-Width and Treewidth
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs