Verlagslink DOI: 10.1016/j.endm.2015.07.013
Titel: Approximating Minimum k-Section in Trees with Linear Diameter
Sprache: Englisch
Autor/Autorin: Fernandes, Cristina G. 
Schmidt, Tina Janne 
Taraz, Anusch 
Schlagwörter: Approximation algorithm; Minimum k-Section; Tree
Erscheinungs­datum: 1-Dez-2015
Quellenangabe: Electronic Notes in Discrete Mathematics (50): 71-76 (2015-12-01)
Zusammenfassung (englisch): 
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.
URI: http://hdl.handle.net/11420/8687
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

55
Letzte Woche
0
Letzten Monat
2
checked on 01.10.2022

SCOPUSTM   
Zitate

2
Letzte Woche
0
Letzten Monat
0
checked on 11.07.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.