Improved dynamic graph coloring

DOI10.1145/3392724MaRDI QIDQ4987463zbMATH OpenOpenAlexFDO

Authors Shay Solomon, Nicole Wein

Publication date 3 May 2021

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/9535/

zbMATH Keywords

dynamic graph algorithmsedge orientationsgraph arboricitygraph coloring

Mathematics Subject Classification ID

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

Recommendations

• Improved dynamic graph coloring
• Dynamic graph coloring
• Dynamic graph coloring
• scientific article; zbMATH DE number 6850309
• Dynamic Edge Coloring with Improved Approximation

Cited in

(16)

• Trade-offs in dynamic coloring for bipartite and general graphs
• Dynamic coloring of graphs
• scientific article; zbMATH DE number 6850309 (Why is no real title available?)
• Improved dynamic graph coloring
• Dynamic Edge Coloring with Improved Approximation
• A new color change to improve the coloring of a graph
• Dynamic graph coloring
• Dynamic graph coloring
• Competitive vertex recoloring. (Online disengagement)
• Improved dynamic colouring of sparse graphs
• Experimental analysis of algorithms for the dynamic graph coloring problem
• Caching connections in matchings
• Locally computing edge orientations
• Competitive capacitated online recoloring
• Colorful vertex recoloring of bipartite graphs
• Near-optimal differentially private graph algorithms via the multidimensional abovethreshold mechanism

This page was built for publication: Improved dynamic graph coloring

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