On partitioning interval graphs into proper interval subgraphs and related problems
From MaRDI portal
Publication:3174235
DOI10.1002/jgt.20539zbMath1233.05157MaRDI QIDQ3174235
Publication date: 12 October 2011
Published in: Journal of Graph Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/jgt.20539
interval graphs; circular-arc graphs; proper interval graphs; efficient graph algorithms; graph partitioning problems
05C35: Extremal problems in graph theory
68R10: Graph theory (including graph drawing) in computer science
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
Cites Work
- Unnamed Item
- Unnamed Item
- Restrictions of graph partition problems. I
- Simple linear time recognition of unit interval graphs
- Mutual exclusion scheduling with interval graphs or related classes: complexity and algorithms
- Mutual exclusion scheduling with interval graphs or related classes. I
- Mutual exclusion scheduling
- Linear-time recognition of circular-arc graphs
- Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
- On the Lambert \(w\) function
- The Roberts characterization of proper and unit interval graphs
- Mutual exclusion scheduling with interval graphs or related classes. II
- Efficient algorithms for interval graphs and circular-arc graphs
- Graph Classes: A Survey
- Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs