A new representation of proper interval graphs with an application to clique-width
From MaRDI portal
Publication:2839207
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
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