An approximation result for a periodic allocation problem

DOI10.1016/S0166-218X(00)00309-7zbMath0994.90065OpenAlexW1991815181WikidataQ126975307 ScholiaQ126975307MaRDI QIDQ5946816

Stefano Giordani, Paolo Dell'Olmo, Giuseppe Confessore

Publication date: 30 July 2002

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

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

zbMATH Keywords

graphapproximation algorithmcircular arc graphHelly propertyclique partitioninterval coloringmultiprocessor task schedulingperiodic allocation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of graph theory (05C90) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

An approximation result for the interval coloring problem on claw-free chordal graphs ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation result for a duo-processor task scheduling problem
• A polynomial time approximation algorithm for dynamic storage allocation
• On chordal proper circular arc graphs
• On the compatibility between a graph and a simple order
• Structure theorems for some circular-arc graphs
• An Introduction to Combinatorial Models of Dynamic Storage Allocation
• The Linearity of First-Fit Coloring of Interval Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Algorithms on circular-arc graphs
• Approximation algorithms for dynamic storage allocation
• A Characterization of Comparability Graphs and of Interval Graphs
• Comparability graph augmentation for some multiprocessor scheduling problems

This page was built for publication: An approximation result for a periodic allocation problem