Approximating spanning tree congestion on graphs with polylog degree

DOI10.1007/978-3-031-63021-7_38MaRDI QIDQ7021069zbMATH OpenFDO

Authors Petr Kolman

Publication date 28 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-63021-7_38

zbMATH Keywords

bisectioncongestiongraph sparsificationspanning tree

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A polylogarithmic approximation of the minimum bisection
• A Survey on Spanning Tree Congestion
• A variation on the min cut linear arrangement problem
• Better hardness results for the minimum spanning tree congestion problem
• Complexity results for the spanning tree congestion problem
• Expander flows, geometric embeddings and graph partitioning
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem
• scientific article; zbMATH DE number 5485537 (Why is no real title available?)
• Minimal congestion trees
• On minimum bisection and related cut problems in trees and tree-like graphs
• Parameterized complexity of the spanning tree congestion problem
• Über ein Minimalproblem.

Cited in

(3)

• Approximation of spanning tree congestion using hereditary bisection
• Parameterized spanning tree congestion
• Approximation of spanning tree congestion using hereditary bisection

This page was built for publication: Approximating spanning tree congestion on graphs with polylog degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7021069)