Publisher DOI: 10.1016/j.endm.2015.07.013
Title: Approximating Minimum k-Section in Trees with Linear Diameter
Language: English
Authors: Fernandes, Cristina G. 
Schmidt, Tina Janne 
Taraz, Anusch 
Keywords: Approximation algorithm;Minimum k-Section;Tree
Issue Date: 1-Dec-2015
Source: Electronic Notes in Discrete Mathematics (50): 71-76 (2015-12-01)
Abstract (english): 
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.
ISSN: 1571-0653
Institute: Mathematik E-10 
Document Type: Article
Journal: Electronic notes in discrete mathematics 
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jun 27, 2022


Last Week
Last month
checked on Jun 18, 2022

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.