The greedy algorithm is optimal for on-line edge coloring
type: Item
instance of: scholarly article
title: The greedy algorithm is optimal for on-line edge coloring
zbMATH Open document ID: 0768.68117
DOI: 10.1016/0020-0190(92)90209-E
author: Amotz Bar-Noy
author: Joseph (Seffi) Naor
author: Rajeev Motwani
published in: Information Processing Letters
publication date: 1993-05-16T00:00:00Z
review text: In this note we are concerned with on-line edge coloring. We show that the greedy algorithm, which has performance ratio 2, is optimal in both the deterministic and the randomized case. In both cases, we define a graph such that any on-line algorithm must use \(2\Delta-1\) colors, independent of whether the graph is given edge-by-edge or vertex-by- vertex. In the deterministic case \(\Delta=O(\log n)\), and in the randomized case \(\Delta=O((\log n)^{1/2})\).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 167756
zbMATH Keywords: graph coloring
zbMATH Keywords: randomized algorithm
zbMATH Keywords: optimal greedy algorithm
zbMATH Keywords: on-line edge coloring
Wikidata QID: Q56390611
MaRDI profile type: Publication
cites work: Q4198056
cites work: On-line and first fit colorings of graphs
cites work: The Linearity of First-Fit Coloring of Interval Graphs
cites work: An on-line graph coloring algorithm with sublinear performance ratio
cites work: Improving the performance guarantee for approximate graph coloring
description: scientific article; zbMATH DE number 167756