Back to Search
Start Over
Approximating Minimum k-Section in Trees with Linear Diameter.
- Source :
- Electronic Notes in Discrete Mathematics; Dec2015, Vol. 50, p71-76, 6p
- Publication Year :
- 2015
-
Abstract
- Minimum k -Section denotes the NP-hard problem to partition the vertex set of a graph into k sets of size 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 c < 1 , 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 + 16 n / diam ( T ) ) Δ ( 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 15710653
- Volume :
- 50
- Database :
- Supplemental Index
- Journal :
- Electronic Notes in Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 111827158
- Full Text :
- https://doi.org/10.1016/j.endm.2015.07.013