An approximation result for a periodic allocation problem

DOI10.1016/S0166-218X(00)00309-7MaRDI QIDQ5946816zbMATH OpenOpenAlexWikidataFDO

Authors Giuseppe Confessore, Paolo Dell'Olmo, Stefano Giordani

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 algorithmHelly propertyclique partitionmultiprocessor task schedulinginterval coloringcircular arc graphperiodic allocation

Mathematics Subject Classification ID

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

Recommendations

• A polynomial time approximation algorithm for dynamic storage allocation
• Periodic assignment and graph colouring
• An approximation algorithm for circular arc colouring
• On \(k\)-coloring of weighted circular-arc graphs
• Perfect circular arc coloring

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1304159 (Why is no real title available?)
• scientific article; zbMATH DE number 3307330 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• A polynomial time approximation algorithm for dynamic storage allocation
• Algorithms on circular-arc graphs
• An Introduction to Combinatorial Models of Dynamic Storage Allocation
• An approximation result for a duo-processor task scheduling problem
• Approximation algorithms for dynamic storage allocation
• Comparability graph augmentation for some multiprocessor scheduling problems
• On chordal proper circular arc graphs
• On the compatibility between a graph and a simple order
• Structure theorems for some circular-arc graphs
• The Complexity of Coloring Circular Arcs and Chords
• The Linearity of First-Fit Coloring of Interval Graphs

Cited in

(5)

• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• An approximation result for the interval coloring problem on claw-free chordal graphs
• Periodic assignment and graph colouring
• On some subclasses of oriented catch digraphs
• Characterizations and recognition of circular-arc graphs and subclasses: a survey

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5946816)