Name
Title | ||
|---|---|---|
Approximating the Minimum k-Section Width in Bounded-Degree Trees with Linear Diameter. |
Abstract | ||
|---|---|---|
Minimum $k$-Section denotes the NP-hard problem to partition the vertex set of a graph into $k$ sets of sizes as equal as possible while minimizing the cut width, which is the number of edges between these sets. When $k$ is an input parameter and $n$ denotes the number of vertices, it is NP-hard to approximate the width of a minimum $k$-section within a factor of $n^c$ for any $cu003c1$, even when restricted to trees with constant diameter. Here, we show that every tree $T$ allows a $k$-section of width at most $(k-1) (2 + 16n / diam(T) ) Delta(T)$. This implies a polynomial-time constant-factor approximation for the Minimum $k$-Section Problem when restricted to trees with linear diameter and constant maximum degree. Moreover, we extend our results from trees to arbitrary graphs with a given tree decomposition. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Combinatorics | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Tree decomposition,Degree (graph theory),Partition (number theory),Mathematics,Bounded function |
DocType | Volume | Citations |
Journal | abs/1708.06431 | 0 |
PageRank | References | Authors |
0.34 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Cristina G. Fernandes | 1 | 260 | 29.98 |
| Tina Janne Schmidt | 2 | 0 | 0.34 |
| Anusch Taraz | 3 | 168 | 37.71 |