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

zbMATH Keywords

graph partitioningspanning tree congestionGyőri-Lovász theoremgraph sparsification\(k\)-vertex-connected graphsMIN-MAX graph partitioning

Mathematics Subject Classification ID

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)

A Survey on Spanning Tree Congestion ⋮ A diameter-revealing proof of the Bondy-Lovász lemma

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