Improved streaming edge coloring

DOI10.4230/LIPICS.ICALP.2025.48MaRDI QIDQ7346484zbMATH OpenFDO

Authors Shiri Chechik, Hongyi Chen, Tianyi Zhang

Publication date 10 September 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2025.48

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• (2-1)-edge-coloring is much easier than maximal matching in the distributed setting
• A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
• A Theorem on Coloring the Lines of a Network
• An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
• Deterministic distributed edge-coloring via hypergraph maximal matching
• Deterministic distributed edge-coloring with fewer colors
• Deterministic online bipartite edge coloring
• Distributed edge coloring and a special case of the constructive Lovász local lemma
• Distributed Edge Coloring in Time Polylogarithmic in Δ
• Dynamic Edge Coloring with Improved Approximation
• Edge-coloring bipartite multigraphs in \(O(E \log D)\) time
• Faster \(( \Delta +1)\)-edge coloring: breaking the \(m\sqrt{n}\) time barrier
• Faster Vizing and near-Vizing edge coloring algorithms
• scientific article; zbMATH DE number 6850309 (Why is no real title available?)
• Improved algorithms for edge colouring in the W-streaming model
• Improved distributed algorithms for the Lovász local lemma and edge coloring
• Loss-less condensers, unbalanced expanders, and extractors
• Low-memory algorithms for online edge coloring
• Nibbling at long cycles: dynamic (and static) edge coloring in optimal time
• Online edge coloring via tree recurrences and correlation decay
• Randomized greedy online edge coloring succeeds for dense and randomly-ordered graphs
• Simple streaming algorithms for edge coloring
• Some simple distributed algorithms for sparse networks
• Streaming and massively parallel algorithms for edge coloring
• Streaming edge coloring with asymptotically optimal colors
• Streaming edge coloring with subquadratic palette size
• The greedy algorithm is not optimal for on-line edge coloring
• The power of multi-step Vizing chains
• Tight bounds for online edge coloring
• Trading off space for passes in graph streaming problems
• Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes
• Unbalanced expanders from multiplicity codes

This page was built for publication: Improved streaming edge coloring

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