Optimal on-line coloring of circular arc graphs

DOI10.1051/ITA/1995290504231zbMATH Open0838.68090OpenAlexW182747812MaRDI QIDQ4858840FDOQ4858840

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

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

zbMATH Keywords

coloring algorithm

Mathematics Subject Classification ID

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

Cites Work

• The Complexity of Coloring Circular Arcs and Chords
• On some packing problem related to dynamic storage allocation
• Title not available (Why is that?)
• A polynomial time approximation algorithm for dynamic storage allocation
• Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs
• Title not available (Why is that?)

Cited In (10)

• On-line graph coloring of \({\mathbb{P}_5}\)-free graphs
• Precoloring extension. I: Interval graphs
• Revisiting Tucker's Algorithm to Color Circular Arc Graphs
• On-line chain partitions of orders: a survey
• 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)