On minimum bisection and related partition problems in graphs with bounded tree width

Publikationstyp
Journal Article
Date Issued
2015-11-12
Sprache
English
Author(s)
Fernandes, Cristina G.  
Schmidt, Tina Janne  
Taraz, Anusch  
Institut
Mathematik E-10  
TORE-URI
http://hdl.handle.net/11420/11365
Journal
Electronic notes in discrete mathematics  
Volume
49
Start Page
481
End Page
488
Citation
Electronic Notes in Discrete Mathematics 49 (): 481-488 (2015)
Publisher DOI
10.1016/j.endm.2015.06.067
Scopus ID
2-s2.0-84947737483
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.
Subjects
Minimum Bisection
Minimum k-Section
Tree decomposition
DDC Class
510: Mathematik