An approximation result for the interval coloring problem on claw-free chordal graphs

DOI10.1016/S0166-218X(01)00282-7zbMath0999.05033OpenAlexW2025453327MaRDI QIDQ1613366

Stefano Giordani, Giuseppe Confessore, Paolo Dell'Olmo

Publication date: 29 August 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(01)00282-7

zbMATH Keywords

approximation algorithmcliquesacyclic orientationinterval coloringmultiprocessor task schedulingclaw-free chordal graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15)

Related Items

On spectrum assignment in elastic optical tree-networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation result for a duo-processor task scheduling problem
• Characterizations of strongly chordal graphs
• The complexity of scheduling independent two-processor tasks on dedicated processors
• Efficiency and effectiveness of normal schedules on three dedicated processors
• An approximation algorithm for scheduling on three dedicated machines
• An Introduction to Combinatorial Models of Dynamic Storage Allocation
• An approximation result for a periodic allocation problem
• Comparability graph augmentation for some multiprocessor scheduling problems