Online Dual Edge Coloring of Paths and Trees

DOI10.1007/978-3-319-18263-6_16MaRDI QIDQ3453294zbMATH OpenOpenAlexFDO

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

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

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

• 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
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• 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 algorithms for the maximum \(k\)-colorable subgraph problem
• 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

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)