Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition
DOI10.4230/LIPIcs.ICALP.2018.32zbMath1499.68259arXiv1802.07632OpenAlexW3022944478MaRDI QIDQ5002702
Yun Kuen Cheung, L. Sunil Chandran, Davis Issac
Publication date: 28 July 2021
Full work available at URL: https://arxiv.org/abs/1802.07632
graph partitioningspanning tree congestionGyőri-Lovász theoremgraph sparsification\(k\)-vertex-connected graphsMIN-MAX graph partitioning
Analysis of algorithms (68W40) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (2)
Cites Work
- Unnamed Item
- Spanning tree congestion of planar graphs
- Spanning tree congestion of \(k\)-outerplanar graphs
- Minimum congestion spanning trees in bipartite and random graphs
- A linear algorithm for bipartition of biconnected graphs
- Minimum congestion spanning trees in planar graphs
- On spanning tree congestion of graphs
- On spanning tree congestion
- How easy is local search?
- Parameterized complexity of the spanning tree congestion problem
- Minimal congestion trees
- Spanning tree congestion of rook's graphs
- (Almost) Tight bounds and existence theorems for single-commodity confluent flows
- Lower-Stretch Spanning Trees
- A variation on the min cut linear arrangement problem
- A homology theory for spanning tress of a graph
- A Graph-Theoretic Game and Its Application to the k-Server Problem
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Using petal-decompositions to build a low stretch spanning tree
- Min-Max Graph Partitioning and Small Set Expansion
- A Nearly-m log n Time Solver for SDD Linear Systems
- Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
- Min-max-boundary domain decomposition
This page was built for publication: Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition
