The influence of preprocessing on steiner tree approximations

Autor(en): Beyer, S.
Chimani, M. 
Herausgeber: Kim, D.
Wu, W.
Du, D.-Z.
Lu, Z.
Li, W.
Stichwörter: Algorithms; Combinatorial optimization; Computational complexity; Graph theory; Optimization; Trees (mathematics), Edge-weighted graph; Minimum weight; Spanning tree; Steiner tree problem; Steiner trees, Approximation algorithms
Erscheinungsdatum: 2015
Herausgeber: Springer Verlag
Enthalten in: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Band: 9486
Startseite: 601
Seitenende: 616
Given an edge-weighted graph G and a node subset R, the Steiner tree problem asks for an R-spanning tree of minimum weight. There are several strong approximation algorithms for this NP-hard problem, but research on their practicality is still in its early stages. In this study, we investigate how the behavior of approximation algorithms changes when applying preprocessing routines first. In particular, the shrunken instances allow us to consider algorithm parameterizations that have been impractical before, shedding new light on the algorithms' respective drawbacks and benefits. © Springer International Publishing Switzerland 2015.
Conference of 9th International Conference on Combinatorial Optimization and Applications, COCOA 2015 ; Conference Date: 18 December 2015 Through 20 December 2015; Conference Code:158749
ISBN: 9783319266251
ISSN: 03029743
DOI: 10.1007/978-3-319-26626-8_44
Externe URL:

Show full item record

Page view(s)

Last Week
Last month
checked on Jun 15, 2024

Google ScholarTM