Improved Dynamic Graph Coloring
From MaRDI portal
Publication:5009642
DOI10.4230/LIPIcs.ESA.2018.72zbMath1484.68173arXiv1904.12427OpenAlexW2885600600MaRDI QIDQ5009642
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1904.12427
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Dynamic data structures for interval coloring ⋮ Trade-offs in dynamic coloring for bipartite and general graphs ⋮ Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Arboricity, \(h\)-index, and dynamic algorithms
- Adjacency queries in dynamic sparse graphs
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- A balanced search tree O(1) worst-case update time
- Removing randomness in parallel computation without a processor penalty
- A constant update time finger search tree
- Efficient computation of implicit representations of sparse graphs
- A Dynamic Data Structure for Counting Subgraphs in Sparse Graphs
- Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs
- Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries
- Oracles for bounded-length shortest paths in planar graphs
- Property testing and its connection to learning and approximation
- Fully Dynamic Matching in Bipartite Graphs
- Dynamic ordered sets with exponential search trees
- Worst-case update times for fully-dynamic all-pairs shortest paths
- Better Inapproximability Results for MaxClique, Chromatic Number and Min-3Lin-Deletion
- Deterministic coin tossing with applications to optimal parallel list ranking
- Parallel Symmetry-Breaking in Sparse Graphs
- Locality in Distributed Graph Algorithms
- Local-on-Average Distributed Tasks
- Faster Fully Dynamic Matchings with Small Approximation Ratios
- Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
- Fully dynamic all-pairs shortest paths with worst-case update-time revisited
- Testing Bounded Arboricity
- Fully dynamic shortest paths in digraphs with arbitrary arc weights
- Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
- Fully-dynamic minimum spanning forest with improved worst-case update time
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs
- Fully dynamic MIS in uniformly sparse graphs
- Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
- Algorithms – ESA 2004
- Fully Dynamic Orthogonal Range Reporting on RAM
- Decomposition of Finite Graphs Into Forests
- Algorithms and Computation
- Dynamic graph coloring
