A simple greedy algorithm for dynamic graph orientation
From MaRDI portal
Publication:5136228
DOI10.4230/LIPICS.ISAAC.2017.12zbMATH Open1457.68203MaRDI QIDQ5136228FDOQ5136228
Authors: Edvin Berglin, Brodal Gerth Stølting 
Publication date: 25 November 2020
Recommendations
- A simple greedy algorithm for dynamic graph orientation
- Orienting fully dynamic graphs with worst-case time bounds
- Orienting dynamic graphs, with applications to maximal matchings and adjacency queries
- Fully dynamic arboricity maintenance
- Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)
Cites Work
- Adjacency queries in dynamic sparse graphs
- Implicat Representation of Graphs
- A balanced search tree O(1) worst-case update time
- Title not available (Why is that?)
- Fully dynamic matching in bipartite graphs
- Orienting dynamic graphs, with applications to maximal matchings and adjacency queries
- Faster fully dynamic matchings with small approximation ratios
- Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach
- Orienting fully dynamic graphs with worst-case time bounds
Cited In (7)
- A simple greedy algorithm for dynamic graph orientation
- Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
- Fully dynamic MIS in uniformly sparse graphs
- Improved dynamic colouring of sparse graphs
- Fully dynamic arboricity maintenance
- Improved dynamic graph coloring
- Orienting fully dynamic graphs with worst-case time bounds
This page was built for publication: A simple greedy algorithm for dynamic graph orientation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136228)
