Verlagslink DOI: 10.1016/j.endm.2015.06.067
Titel: On minimum bisection and related partition problems in graphs with bounded tree width
Sprache: Englisch
Autor/Autorin: Fernandes, Cristina G. 
Schmidt, Tina Janne 
Taraz, Anusch 
Schlagwörter: Minimum Bisection; Minimum k-Section; Tree decomposition
Erscheinungs­datum: 12-Nov-2015
Quellenangabe: Electronic Notes in Discrete Mathematics 49 (): 481-488 (2015)
Zusammenfassung (englisch): 
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.
URI: http://hdl.handle.net/11420/11365
ISSN: 1571-0653
Zeitschrift: Electronic notes in discrete mathematics 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

38
Letzte Woche
0
Letzten Monat
checked on 01.10.2022

SCOPUSTM   
Zitate

2
Letzte Woche
0
Letzten Monat
checked on 30.06.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.