Comparing first-fit and next-fit for online edge coloring
type: Item
instance of: scholarly article
title: Comparing first-fit and next-fit for online edge coloring
zbMATH Open document ID: 1191.68881
author: Martin R. Ehmsen
author: Jens S. Kohrt
author: Rodica Mihai
author: Lene M. Favrholdt
published in: Theoretical Computer Science
publication date: 2010-04-15T00:00:00Z
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 5693340
zbMATH Keywords: online algorithms
zbMATH Keywords: edge coloring
zbMATH Keywords: competitive ratio
zbMATH Keywords: relative worst-order ratio
zbMATH Keywords: next-fit
zbMATH Keywords: first-fit
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.01.015
OpenAlex ID: W2093548869
cites work: On-line edge-coloring with a fixed number of colors
cites work: Competitive snoopy caching
cites work: The greedy algorithm is optimal for on-line edge coloring
cites work: The relative worst-order ratio applied to paging
cites work: Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem
cites work: The relative worst order ratio for online algorithms
cites work: Separating online scheduling algorithms with the relative worst order ratio
cites work: Algorithm Theory - SWAT 2004
cites work: Q4223058
cites work: A new measure for the study of on-line algorithms
cites work: Q4875207
cites work: Explicit constructions of linear-sized superconcentrators
cites work: Q4856179
DOI: 10.1016/J.TCS.2010.01.015
Recommended article: Comparing First-Fit and Next-Fit for Online Edge Coloring
Recommended article: On-line edge-coloring with a fixed number of colors
Recommended article: Q4472437
Recommended article: On-line and first fit colorings of graphs
Recommended article: On-line interval graphs coloring — Modification of the First-Fit algorithm and its performance ratio
Recommended article: A comparison of two edge-coloring formulations
Recommended article: A note on the online first-fit algorithm for coloring \(k\)-inductive graphs
Recommended article: Dynamic Edge Coloring with Improved Approximation
Recommended article: Online edge coloring of paths and trees with a fixed number of colors
Recommended article: Online edge coloring via tree recurrences and correlation decay
description: scientific article; zbMATH DE number 5693340