Approximating node-weighted \(k\)-MST on planar graphs

DOI10.1007/s00224-020-09965-wzbMath1444.90097OpenAlexW3021381916MaRDI QIDQ5918856

Jaroslaw Byrka, Mateusz Lewandowski, Joachim Spoerhase

Publication date: 2 June 2020

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

Full work available at URL: https://doi.org/10.1007/s00224-020-09965-w

zbMATH Keywords

Lagrangian relaxationplanar graphsapproximation algorithmsLMPnode-weighted \(k\)-MST

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• A unified approach to approximating partial covering problems
• Approximate \(k\)-MSTs and \(k\)-Steiner trees via the primal-dual method and Lagrangean relaxation
• Primal-dual approximation algorithms for node-weighted Steiner forest on planar graphs
• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
• Node-Weighted Network Design in Planar and Minor-Closed Families of Graphs
• Primal-Dual Approximation Algorithms for Node-Weighted Network Design in Planar Graphs
• Prize-Collecting Survivable Network Design in Node-Weighted Graphs
• Saving an epsilon
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• A General Approximation Technique for Constrained Forest Problems
• Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs
• Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems
• Approximation Algorithms for Node-Weighted Prize-Collecting Steiner Tree Problems on Planar Graphs
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems

This page was built for publication: Approximating node-weighted \(k\)-MST on planar graphs