4 papers · 1 filter
Sublinear Approximations for Spanning Tree Congestion
Sunny Atalig, Marek Chrobak, Petr Kolman +1
The spanning tree congestion of a connected graph \(G\) is the minimum, over all spanning trees \(T\) of \(G\), of the maximum number of edges of \(G\) crossing a cut induced by de…
Two Complexity Results on Spanning-Tree Congestion Problems
Sunny Atalig, Marek Chrobak, Christoph Dürr +4
In the spanning-tree congestion problem (), we are given a graph , and the objective is to compute a spanning tree of that minimizes the maximum edge congestio…
Min-Max Connected Multiway Cut
Hans Raj Tiwary, Petr Kolman
We introduce a variant of the multiway cut that we call the min-max connected multiway cut. Given a graph and a set of terminals, partition into $t…
Approximation of Spanning Tree Congestion using Hereditary Bisection
Petr Kolman
The Spanning Tree Congestion (STC) problem is the following NP-hard problem: given a graph , construct a spanning tree of minimizing its maximum edge congestion where th…