Online edge coloring of paths and trees with a fixed number of colors

DOI10.1007/S00236-016-0283-0MaRDI QIDQ1702302zbMATH OpenOpenAlexFDO

Authors Jesper W. Mikkelsen, Lene M. Favrholdt

Publication date 28 February 2018

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.3817

Mathematics Subject Classification ID

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

Abstract: We study a version of online edge coloring, where the goal is to color as many edges as possible using only a given number, $k$, of available colors. All of our results are with regard to competitive analysis. Previous attempts to identify optimal algorithms for this problem have failed, even for bipartite graphs. Thus, in this paper, we analyze even more restricted graph classes, paths and trees. For paths, we consider $k=2$, and for trees, we consider any $kgeq2$. We prove that a natural greedy algorithm called First-Fit is optimal among deterministic algorithms, on paths as well as trees. For paths, we give a randomized algorithm, which is optimal and better than the best possible deterministic algorithm. For trees, we prove that to obtain a better competitive ratio than First-Fit, the algorithm would have to be both randomized and unfair (i.e., reject edges that could have been colored), and even such algorithms cannot be much better than First-Fit.

Recommendations

• Online Dual Edge Coloring of Paths and Trees
• On-line edge-coloring with a fixed number of colors
• Online graph edge-coloring in the random-order arrival model
• scientific article; zbMATH DE number 2080195
• The greedy algorithm is optimal for on-line edge coloring

Cites work

• scientific article; zbMATH DE number 3651705 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1947051 (Why is no real title available?)
• Approximating maximum edge 2-coloring in simple graphs
• Approximating the maximum 2- and 3-edge-colorable subgraph problems
• Approximating the maximum 3-edge-colorable subgraph problem
• Beyond the Vizing's bound for at most seven colors
• Comparing first-fit and next-fit for online edge coloring
• Competitive snoopy caching
• On-line coloring \(k\)-colorable graphs
• On-line edge-coloring with a fixed number of colors
• The greedy algorithm is optimal for on-line edge coloring
• The relative worst order ratio for online algorithms
• The relative worst-order ratio applied to paging
• The seat reservation problem
• Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem

Cited in

(9)

• Comparing first-fit and next-fit for online edge coloring
• Online edge coloring via tree recurrences and correlation decay
• A refined analysis of online path coloring in trees
• The greedy algorithm is optimal for on-line edge coloring
• Online Dual Edge Coloring of Paths and Trees
• Comparing First-Fit and Next-Fit for Online Edge Coloring
• Online multi-coloring on the path revisited
• scientific article; zbMATH DE number 2080195 (Why is no real title available?)
• On-line edge-coloring with a fixed number of colors

This page was built for publication: Online edge coloring of paths and trees with a fixed number of colors

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