Approximating Steiner Networks with Node Weights

DOI10.1007/978-3-540-78773-0_36zbMath1136.68336OpenAlexW2171109283MaRDI 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

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Related Items (5)

Approximating some network design problems with node costs ⋮ On minimum power connectivity problems ⋮ Approximating minimum power covers of intersecting families and directed edge-connectivity problems ⋮ Approximating fault-tolerant group-Steiner problems ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs

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

This page was built for publication: Approximating Steiner Networks with Node Weights