2026-07-20T05:10:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2121 2024-03-06T11:08:44Z ddc:004 open_access

Parameterized Analysis of Online Steiner Tree Problems Angelopoulos, Spyros Online algorithms Steiner tree problems adaptive and parameteried analysis Steiner tree problems occupy a central place in both areas of approximation and on-line algorithms. Many variants have been studied from the point of view of competitive analysis, and for several of these variants tight bounds are known. However, in several cases, worst-case analysis is overly pessimistic, which fails to explain the relative performance of algorithms. We show how adaptive analysis can help resolve this problem. As case studies, we consider the Steiner tree problem in directed graphs, and the Priority Steiner tree problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Spyros Angelopoulos 2009 Is Part Of Dagstuhl Seminar Proceedings, Volume 9171, Adaptive, Output Sensitive, Online and Parameterized Algorithms (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.09171.3 urn:nbn:de:0030-drops-21210 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09171.3 eng https://creativecommons.org/licenses/by/4.0/legalcode