A simple greedy algorithm for dynamic graph orientation

DOI10.4230/LIPICS.ISAAC.2017.12MaRDI QIDQ5136228zbMATH OpenFDO

Authors Edvin Berglin, Brodal Gerth Stølting

Publication date 25 November 2020

zbMATH Keywords

dynamic graph algorithmsedge orientationsgraph arboricity

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 2185626 (Why is no real title available?)
• A balanced search tree O(1) worst-case update time
• Adjacency queries in dynamic sparse graphs
• Dynamic \((1 + \epsilon)\)-approximate matchings: a density-sensitive approach
• Faster fully dynamic matchings with small approximation ratios
• Fully dynamic matching in bipartite graphs
• Implicat Representation of Graphs
• Orienting dynamic graphs, with applications to maximal matchings and adjacency queries
• Orienting fully dynamic graphs with worst-case time bounds

Cited in

(7)

• Orienting fully dynamic graphs with worst-case time bounds
• 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

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)