On the performance of the first-fit coloring algorithm on permutation graphs

DOI10.1016/S0020-0190(00)00109-5zbMath1339.68320OpenAlexW2132976302MaRDI QIDQ294842

Stavros D. Nikolopoulos, Charis Papadopoulos

Publication date: 16 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019000001095?np=y

zbMATH Keywords

perfect graphspermutation graphsfirst-fit algorithmonline coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Perfect graphs (05C17) Online algorithms; streaming algorithms (68W27)

Related Items (5)

Coloring permutation graphs in parallel ⋮ Online Bounded Coloring of Permutation and Overlap Graphs ⋮ On the online track assignment problem ⋮ Track assignment ⋮ Generalised online colouring problems in overlap graphs

Cites Work

• Unnamed Item
• On-line coloring \(k\)-colorable graphs
• Coloring inductive graphs on-line
• On Comparability and Permutation Graphs
• On-line and first fit colorings of graphs
• The Linearity of First-Fit Coloring of Interval Graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• 25 pretty graph colouring problems

This page was built for publication: On the performance of the first-fit coloring algorithm on permutation graphs