Optimal on-line coloring of circular arc graphs

DOI10.1051/ITA/1995290504231MaRDI QIDQ4858840zbMATH OpenOpenAlexFDO

Authors Maciej Ślusarek

Publication date 20 December 1995

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92516

zbMATH Keywords

coloring algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs
• On-line and first fit colorings of graphs
• scientific article; zbMATH DE number 17824
• An on-line graph coloring algorithm with sublinear performance ratio
• On-line coloring \(k\)-colorable graphs

Cites work

• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 17824 (Why is no real title available?)
• A polynomial time approximation algorithm for dynamic storage allocation
• Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs
• On some packing problem related to dynamic storage allocation
• The Complexity of Coloring Circular Arcs and Chords

Cited in

(10)

• On-line graph coloring of \({\mathbb{P}_5}\)-free graphs
• Precoloring extension. I: Interval graphs
• On-line chain partitions of orders: a survey
• Revisiting Tucker's Algorithm to Color Circular Arc Graphs
• The on-line first-fit algorithm for radio frequency assignment problems.
• On-line coloring and cliques covering for \(\mathbb K_{s,t}\)-free graphs
• On-line routing in all-optical networks
• An \(0(n^{1.5})\) algorithm to color proper circular arcs
• On-line routing in all-optical networks
• Selfish Routing and Path Coloring in All-Optical Networks

This page was built for publication: Optimal on-line coloring of circular arc graphs

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