Fully dynamic arboricity maintenance

DOI10.1016/j.tcs.2020.04.010zbMath1452.68130OpenAlexW2963057705MaRDI QIDQ5918831

Niranka Banerjee, Venkatesh Raman, Saket Saurabh

Publication date: 23 May 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2020.04.010

zbMATH Keywords

lower boundsarboricityincrementalaugmenting pathsfully dynamicdecremental

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Adjacency queries in dynamic sparse graphs
• Planar graphs and poset dimension
• Arboricity and bipartite subgraph listing algorithms
• Simple planar graph partition into three forests
• A data structure for dynamic trees
• Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• A Constructive Arboricity Approximation Scheme
• A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
• Algorithms for Graphic Polymatroids and Parametrics-Sets
• Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
• Logarithmic Lower Bounds in the Cell-Probe Model
• Minimum partition of a matroid into independent subsets
• Lehmans switching game and a theorem of Tutte and Nash-Williams
• Decomposition of Finite Graphs Into Forests
• Fully dynamic arboricity maintenance