On partitioning interval graphs into proper interval subgraphs and related problems

DOI10.1002/jgt.20539zbMath1233.05157MaRDI QIDQ3174235

Frédéric Gardi

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

zbMATH Keywords

interval graphs; circular-arc graphs; proper interval graphs; efficient graph algorithms; graph partitioning problems

Mathematics Subject Classification ID

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