On the classes of interval graphs of limited nesting and count of lengths
From MaRDI portal
Publication:1739103
DOI10.1007/s00453-018-0481-yzbMath1423.05109OpenAlexW2883994934WikidataQ129558292 ScholiaQ129558292MaRDI QIDQ1739103
Pavel Klavík, Yota Otachi, Jiří Šejnoha
Publication date: 25 April 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2016/6815/
Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)
Related Items
Maximum cut on interval graphs of interval count four is NP-complete, Stick graphs with length constraints, Unnamed Item, Recognizing Stick Graphs with and without Length Constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extending partial representations of proper and unit interval graphs
- On counting interval lengths of interval graphs
- Simple linear time recognition of unit interval graphs
- Chronological orderings of interval graphs
- Interval graphs and interval orders
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Extending partial representations of trapezoid graphs
- Graphs of interval count two with a given partition
- Paradoxes of two-length interval orders
- Extending partial representations of subclasses of chordal graphs
- Incidence matrices and interval graphs
- Extending partial representations of interval graphs
- On the thinness and proper thinness of a graph
- Extending Partial Representations of Circle Graphs
- Extending Partial Representations of Function Graphs and Permutation Graphs
- Minimal Obstructions for Partial Representations of Interval Graphs
- Contact Representations of Planar Graphs: Extending a Partial Representation is Hard
- Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory
- Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms
- Representation of a finite graph by a set of intervals on the real line
- FO Model Checking of Interval Graphs
- The Interval Count of a Graph
- An Incremental Linear-Time Algorithm for Recognizing Interval Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Complexity Results for Multiprocessor Scheduling under Resource Constraints
- On the Classes of Interval Graphs of Limited Nesting and Count of Lengths
- Simultaneous PQ-Ordering with Applications to Constrained Embedding Problems
