Dynamic Edge Coloring with Improved Approximation

DOI10.1137/1.9781611975482.117MaRDI QIDQ5236303zbMATH OpenOpenAlexFDO

Authors Ran Duan, Haoqing He, Tianyi Zhang

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975482.117

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Improved dynamic graph coloring
• Improved dynamic graph coloring
• Improved approximation for maximum edge colouring problem
• Dynamic coloring of graphs
• scientific article; zbMATH DE number 1304053
• scientific article; zbMATH DE number 3889546
• A polyhedral approach to edge coloring
• Very fast parallel algorithms for approximate edge coloring
• Dynamic graph coloring
• Dynamic graph coloring

Cited in

(14)

• Comparing first-fit and next-fit for online edge coloring
• Fast and simple (1 + ) -edge-coloring of dense graphs
• Fully Dynamic (Δ +1)-Coloring in O (1) Update Time
• Deterministic rounding of dynamic fractional matchings
• The greedy algorithm is not optimal for on-line edge coloring
• Dynamic graph coloring
• Dynamic graph coloring
• Improved dynamic graph coloring
• Edge-coloring sparse graphs with Colors in quasilinear time
• Caching connections in matchings
• Sparsity-parameterised dynamic edge colouring
• Arboricity-dependent algorithms for edge coloring
• The power of multi-step Vizing chains
• Improved dynamic graph coloring

This page was built for publication: Dynamic Edge Coloring with Improved Approximation

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