The influence of preprocessing on steiner tree approximations

DC FieldValueLanguage
dc.contributor.authorBeyer, S.
dc.contributor.authorChimani, M.
dc.contributor.editorKim, D.
dc.contributor.editorWu, W.
dc.contributor.editorDu, D.-Z.
dc.contributor.editorLu, Z.
dc.contributor.editorLi, W.
dc.date.accessioned2021-12-23T16:32:30Z-
dc.date.available2021-12-23T16:32:30Z-
dc.date.issued2015
dc.identifier.isbn9783319266251
dc.identifier.issn03029743
dc.identifier.urihttps://osnascholar.ub.uni-osnabrueck.de/handle/unios/17383-
dc.descriptionConference of 9th International Conference on Combinatorial Optimization and Applications, COCOA 2015 ; Conference Date: 18 December 2015 Through 20 December 2015; Conference Code:158749
dc.description.abstractGiven 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.
dc.description.sponsorshipDeutsche ForschungsgemeinschaftDeutsche Forschungsgemeinschaft,DFG,1,4; Funded by project CH 897/1-1 of the German Research Foundation (DFG). 1 Article [2] is an extended version of both [1,4], with several implementation improvements; when referring to these studies in the following, we will only cite [2].;
dc.language.isoen
dc.publisherSpringer Verlag
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.subjectAlgorithms
dc.subjectCombinatorial optimization
dc.subjectComputational complexity
dc.subjectGraph theory
dc.subjectOptimization
dc.subjectTrees (mathematics), Edge-weighted graph
dc.subjectMinimum weight
dc.subjectSpanning tree
dc.subjectSteiner tree problem
dc.subjectSteiner trees, Approximation algorithms
dc.titleThe influence of preprocessing on steiner tree approximations
dc.typeconference paper
dc.identifier.doi10.1007/978-3-319-26626-8_44
dc.identifier.scopus2-s2.0-84952053738
dc.identifier.urlhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84952053738&doi=10.1007%2f978-3-319-26626-8_44&partnerID=40&md5=0e50957a80646a3bc1747296da19b6b2
dc.description.volume9486
dc.description.startpage601
dc.description.endpage616
dcterms.isPartOf.abbreviationLect. Notes Comput. Sci.
crisitem.author.orcid0000-0002-4681-5550-
crisitem.author.netidChMa572-
Show simple item record

Page view(s)

4
Last Week
0
Last month
0
checked on May 23, 2024

Google ScholarTM

Check

Altmetric