A simple greedy algorithm for dynamic graph orientation

DOI10.1007/s00453-018-0528-0zbMath1433.68278OpenAlexW2900862090WikidataQ128908560 ScholiaQ128908560MaRDI QIDQ1986959

Gerth Stølting Brodal, Edvin Berglin

Publication date: 9 April 2020

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8263/

zbMATH Keywords

dynamic graph algorithmsedge orientationsgraph arboricity

Mathematics Subject Classification ID

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

Related Items

On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition

Cites Work

• Unnamed Item
• Adjacency queries in dynamic sparse graphs
• A balanced search tree O(1) worst-case update time
• Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries
• Fully Dynamic Matching in Bipartite Graphs
• Implicat Representation of Graphs
• Faster Fully Dynamic Matchings with Small Approximation Ratios
• Dynamic (1 + ∊)-Approximate Matchings: A Density-Sensitive Approach
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Orienting Fully Dynamic Graphs with Worst-Case Time Bounds