Parameterized analysis of the online priority and node-weighted Steiner tree problems

DOI10.1007/S00224-019-09922-2MaRDI QIDQ2322716zbMATH OpenOpenAlexWikidataFDO

Authors Spyros Angelopoulos

Publication date 5 September 2019

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-019-09922-2

zbMATH Keywords

online algorithmscompetitive analysisSteiner tree problemsmulticastingmodels of communication networks

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Online Priority Steiner Tree Problems
• The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights
• Online node-weighted Steiner tree and related problems
• Near-optimal online algorithms for prize-collecting Steiner problems
• scientific article; zbMATH DE number 1559550

Cites work

• scientific article; zbMATH DE number 6381651 (Why is no real title available?)
• scientific article; zbMATH DE number 5764797 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 1559550 (Why is no real title available?)
• scientific article; zbMATH DE number 1559563 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A General Approximation Technique for Constrained Forest Problems
• A Near-Tight Bound for the Online Steiner Tree Problem in Graphs of Bounded Asymmetry
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• A general approach to online network optimization problems
• A survey of combinatorial optimization problems in multicast routing
• A threshold of ln n for approximating set cover
• Approximation Algorithms for Directed Steiner Problems
• Dynamic Steiner Tree Problem
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• Linear bounds for on-line Steiner problems
• Non-approximability results for optimization problems on bounded degree instances
• On the approximability of some network design problems
• On the approximability of the Steiner tree problem.
• On the competitiveness of the online asymmetric and Euclidean Steiner tree problems
• On-line Steiner trees in the Euclidean plane
• On-line generalized Steiner problem
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• Online Steiner tree with deletions
• Online node-weighted Steiner tree and related problems
• Reducibility among combinatorial problems
• Steiner tree approximation via iterative randomized rounding
• THE EFFECT OF ASYMMETRY ON THE ON-LINE MULTICAST ROUTING PROBLEM
• The Performance of greedy algorithms for the on-line steiner tree and related problems
• The Steiner problem with edge lengths 1 and 2
• The power of deferral: maintaining a constant-competitive Steiner tree online
• The power of deferral: maintaining a constant-competitive Steiner tree online
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(4)

• The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights
• Online node-weighted Steiner tree and related problems
• Online Priority Steiner Tree Problems
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings

This page was built for publication: Parameterized analysis of the online priority and node-weighted Steiner tree problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2322716)