Approximating Steiner Networks with Node Weights

DOI10.1007/978-3-540-78773-0_36zbMath1136.68336MaRDI QIDQ5458547

Zeev Nutov

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_36

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68R10: Graph theory (including graph drawing) in computer science

68W25: Approximation algorithms

Related Items

Approximating some network design problems with node costs, Approximating fault-tolerant group-Steiner problems, On minimum power connectivity problems, Approximating minimum power covers of intersecting families and directed edge-connectivity problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A factor 2 approximation algorithm for the generalized Steiner network problem
• Power optimization for connectivity problems
• Improved methods for approximating node weighted Steiner trees and connected dominating sets.
• A primal-dual approximation algorithm for generalized Steiner network problems
• Design networks with bounded pairwise distance
• A threshold of ln n for approximating set cover
• Approximating Minimum Power Covers of Intersecting Families and Directed Connectivity Problems
• Approximating Some Network Design Problems with Node Costs
• A General Approximation Technique for Constrained Forest Problems
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
• Approximation algorithms for constrained for constrained node weighted steiner tree problems
• The dense \(k\)-subgraph problem