Publisher DOI: 10.1016/j.endm.2015.06.067
Title: On minimum bisection and related partition problems in graphs with bounded tree width
Language: English
Authors: Fernandes, Cristina G. 
Schmidt, Tina Janne 
Taraz, Anusch 
Keywords: Minimum Bisection; Minimum k-Section; Tree decomposition
Issue Date: 12-Nov-2015
Source: Electronic Notes in Discrete Mathematics 49 (): 481-488 (2015)
Abstract (english): 
Minimum Bisection denotes the NP-hard problem to partition the vertex set of a graph into two sets of equal sizes while minimizing the number of edges between these two sets. We consider this problem in bounded degree graphs with a given tree decomposition (T, X) and prove an upper bound for their minimum bisection width in terms of the structure and width of (T, X). When (T, X) is provided as input, a bisection satisfying our bound can be computed in time proportional to the encoding length of (T, X). Furthermore, our result can be generalized to k-section, which is known to be APX-hard even when restricted to trees with bounded degree.
ISSN: 1571-0653
Journal: Electronic notes in discrete mathematics 
Institute: Mathematik E-10 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jul 5, 2022


Last Week
Last month
checked on Jun 30, 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.