Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries

DOI10.1007/978-3-319-13075-0_11zbMath1412.68169OpenAlexW2182065913MaRDI QIDQ2942621

Ganggui Tang, Meng He, Norbert Zeh

Publication date: 11 September 2015

Published in: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13075-0_11

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Directed graphs (digraphs), tournaments (05C20)

Related Items

Simultaneously load balancing for every p-norm, with reassignments, 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

Cites Work

• Unnamed Item
• Adjacency queries in dynamic sparse graphs
• Matching theory
• Forests, frames, and games: Algorithms for matroid sums and applications
• Fast 3-coloring triangle-free planar graphs
• Oracles for bounded-length shortest paths in planar graphs
• Tight(er) worst-case bounds on dynamic searching and priority queues
• Edge-Disjoint Spanning Trees of Finite Graphs
• Implicat Representation of Graphs
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
• Decomposition of Finite Graphs Into Forests