Simple streaming algorithms for edge coloring

DOI10.4230/LIPICS.ESA.2022.8MaRDI QIDQ6969681zbMATH OpenFDO

Authors Mohammad Saneian, Hamid Zarrabi-Zadeh, Mohammad Ansari

Publication date 19 June 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2022.8

zbMATH Keywords

adversarial orderedge coloringstreaming model

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A constructive proof of Vizing's theorem
• An Efficient Algorithm for Colouring the Edges of a Graph With Δ + 1 Colours
• Automata, Languages and Programming
• scientific article; zbMATH DE number 7788506 (Why is no real title available?)
• Improved algorithms for edge colouring in the W-streaming model
• Online graph edge-coloring in the random-order arrival model
• Streaming and massively parallel algorithms for edge coloring
• The greedy algorithm is optimal for on-line edge coloring
• The NP-Completeness of Edge-Coloring
• Tight bounds for online edge coloring
• Trading off space for passes in graph streaming problems

Cited in

(5)

• Streaming edge coloring with asymptotically optimal colors
• Low-memory algorithms for online edge coloring
• Streaming edge coloring with subquadratic palette size
• Streaming algorithms for conflict-free coloring
• Improved streaming edge coloring

This page was built for publication: Simple streaming algorithms for edge coloring

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