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

DOI10.1007/S00236-016-0283-0zbMATH Open1387.05250arXiv1405.3817OpenAlexW2543320042MaRDI QIDQ1702302FDOQ1702302

Authors: Jesper W. Mikkelsen, Lene M. Favrholdt 

Publication date: 28 February 2018

Published in: Acta Informatica (Search for Journal in Brave)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Online edge coloring via tree recurrences and correlation decay
• Comparing first-fit and next-fit for online edge coloring
• 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
• Title not available (Why is that?)
• Online multi-coloring on the path revisited
• 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)