Parameterized Analysis of the Online Priority and Node-Weighted Steiner Tree Problems

摘要: In this paper we study the online variant of two well-known Steiner tree problems. setting, input consists a sequence terminals; upon arrival terminal, algorithm must irrevocably buy subset edges and vertices graph so as to guarantee connectivity currently revealed part input. More precisely, first node-weighted problem, in which both are weighted, objective is minimize total cost solution. We then address priority each edge request associated with value, corresponds their bandwidth support requirement, respectively. Both problems have applications domain multicast network communications been studied from point view approximation algorithms. Motivated by observation that competitive analysis gives very pessimistic unsatisfactory results when only relevant parameter number terminals, introduce an approach based on parameterized particular, base additional parameters help reveal true complexity underlying allow much finer classification algorithms performance. specifically, for show tight bound Θ(max{min{α,k},log k}) ratio, where α ratio maximum node weight minimum k terminals. For corresponding bounds \({\Theta }(b\log \frac {k}{b})\), > b Θ(k), ≤ b, levels Our main apply deterministic randomized algorithms, well generalized versions (i.e., forest variants).