Online Dual Edge Coloring of Paths and Trees
From MaRDI portal
Publication:3453294
DOI10.1007/978-3-319-18263-6_16zbMath1387.05249OpenAlexW1825079874MaRDI QIDQ3453294
Jesper W. Mikkelsen, Lene Monrad Favrholdt
Publication date: 20 November 2015
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-18263-6_16
Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (1)
Cites Work
- Unnamed Item
- Approximating maximum edge 2-coloring in simple graphs
- The relative worst-order ratio applied to paging
- Comparing first-fit and next-fit for online edge coloring
- Approximating the maximum 2- and 3-edge-colorable subgraph problems
- Approximating the maximum 3-edge-colorable subgraph problem
- Competitive snoopy caching
- The greedy algorithm is optimal for on-line edge coloring
- On-line edge-coloring with a fixed number of colors
- The relative worst order ratio for online algorithms
- Approximating the Maximum 3- and 4-Edge-Colorable Subgraph
This page was built for publication: Online Dual Edge Coloring of Paths and Trees