Orienting Fully Dynamic Graphs with Worst-Case Time Bounds

DOI10.1007/978-3-662-43951-7_45zbMath1411.68084arXiv1312.1382OpenAlexW1501843896MaRDI QIDQ5167867

Robert Krauthgamer, Shay Solomon, Ely Porat, Tsvi Kopelowitz

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1312.1382

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (10)

Fully Dynamic Matching in Bipartite Graphs ⋮ Simultaneously load balancing for every p-norm, with reassignments ⋮ Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries ⋮ On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition ⋮ Local Algorithms for Bounded Degree Sparsifiers in Sparse Graphs ⋮ Fully dynamic MIS in uniformly sparse graphs ⋮ A simple greedy algorithm for dynamic graph orientation ⋮ Fully dynamic arboricity maintenance ⋮ Unnamed Item ⋮ Improved Dynamic Graph Coloring

This page was built for publication: Orienting Fully Dynamic Graphs with Worst-Case Time Bounds