Online Dual Edge Coloring of Paths and Trees

DOI10.1007/978-3-319-18263-6_16MaRDI QIDQ3453294zbMATHOpenAlexFDO

Authors Jesper W. Mikkelsen, Lene M. 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

Mathematics Subject Classification ID

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

Recommendations

• Online edge coloring of paths and trees with a fixed number of colors
• A refined analysis of online path coloring in trees
• Online multi-coloring on the path revisited
• Online edge coloring via tree recurrences and correlation decay
• On-line DP-coloring of graphs
• On-line P-coloring of graphs
• Online coloring of hypergraphs
• On-Line Coloring and Recursive Graph Theory
• On-line coloring \(k\)-colorable graphs
• Online coloring co-interval graphs

Cites work

• scientific article; zbMATH DE number 1232130 (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- and 4-edge-colorable subgraph (extended abstract)
• Approximating the maximum 3-edge-colorable subgraph problem
• Comparing first-fit and next-fit for online edge coloring
• Competitive snoopy caching
• 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

Cited in

(5)

• Online edge coloring of paths and trees with a fixed number of colors
• A refined analysis of online path coloring in trees
• Online algorithms for the maximum \(k\)-colorable subgraph problem
• Online multi-coloring on the path revisited
• Online edge coloring via tree recurrences and correlation decay

This page was built for publication: Online Dual Edge Coloring of Paths and Trees

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