On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
DOI10.1137/21m1434441zbMath1516.05027arXiv2009.10761MaRDI QIDQ6098462
David G. Harris, Hsin-Hao Su, Hoa T. Vu
Publication date: 14 June 2023
Published in: SIAM Journal on Discrete Mathematics, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2009.10761
graph algorithmsarboricitylocal algorithmsforest decompositionstar-arboricityforest decompositionsLOCAL algorithm
Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed systems (68M14) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fast distributed network decompositions and covers
- Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition
- Forests, frames, and games: Algorithms for matroid sums and applications
- Star arboricity
- Near-optimal, distributed edge colouring via the nibble method
- Low diameter graph decompositions
- A note on list arboricity
- The star-arboricity of the complete regular multipartite graphs
- The star arboricity of graphs
- A simple greedy algorithm for dynamic graph orientation
- On the degrees of the vertices of a directed graph
- A fast distributed algorithm for \((\Delta+1)\)-edge-coloring
- Distributed strong diameter network decomposition
- Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
- Efficient Primal-Dual Graph Algorithms for MapReduce
- Densest Subgraph in Dynamic Graph Streams
- NETWORK-FLOW ALGORITHMS FOR LOWER-TRUNCATED TRANSVERSAL POLYMATROIDS
- On Finding Dense Subgraphs
- A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees
- Deterministic coin tossing with applications to optimal parallel list ranking
- A network flow solution to some nonlinear 0-1 programming problems, with applications to graph theory
- Locality in Distributed Graph Algorithms
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
- Distributed Degree Splitting, Edge Coloring, and Orientations
- A Fast Parametric Maximum Flow Algorithm and Applications
- Dense Subgraphs on Dynamic Networks
- On the complexity of local distributed graph problems
- Distributed Graph Coloring: Fundamentals and Recent Developments
- Distributed Local Approximation Algorithms for Maximum Matching in Graphs and Hypergraphs
- Near-optimal fully dynamic densest subgraph
- Polylogarithmic-time deterministic network decomposition and distributed derandomization
- Massively Parallel Computation of Matching and MIS in Sparse Graphs
- Faster Deterministic Distributed Coloring Through Recursive List Coloring
- Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
- Improved Distributed Delta-Coloring
- Towards the locality of Vizing’s theorem
- Deterministic distributed edge-coloring with fewer colors
- (2Δ — l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting
- Maintaining Assignments Online: Matching, Scheduling, and Flows
- Deterministic Distributed Vertex Coloring in Polylogarithmic Time
- Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures
- Decomposition of Finite Graphs Into Forests
- Distributed algorithms for the Lovász local lemma and graph coloring
This page was built for publication: On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
