Approximating Minimum k-Section in Trees with Linear Diameter

Publikationstyp
Journal Article
Date Issued
2015-12-01
Sprache
English
Author(s)
Fernandes, Cristina G.  
Schmidt, Tina Janne  
Taraz, Anusch  
Institut
Mathematik E-10  
TORE-URI
http://hdl.handle.net/11420/8687
Journal
Electronic notes in discrete mathematics  
Volume
50
Start Page
71
End Page
76
Citation
Electronic Notes in Discrete Mathematics (50): 71-76 (2015-12-01)
Publisher DOI
10.1016/j.endm.2015.07.013
Scopus ID
2-s2.0-84947749418
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 nc 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+16n/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.
Subjects
Approximation algorithm
Minimum k-Section
Tree