Approximating Steiner Networks with Node-Weights

DOI10.1137/080729645zbMath1217.68248OpenAlexW2056152695MaRDI QIDQ5390585

Zeev Nutov

Publication date: 4 April 2011

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/080729645

zbMATH Keywords

approximation algorithmsSteiner networknode-weightsuncrossable families

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40)

Related Items (13)

The Densest $k$-Subhypergraph Problem ⋮ Survivable network activation problems ⋮ Improved approximation algorithms for directed Steiner forest ⋮ An \(O(\sqrt{k})\)-approximation algorithm for minimum power \(k\) edge disjoint \(st\)-paths ⋮ An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem ⋮ Covering problems in edge- and node-weighted graphs ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings ⋮ Approximation algorithm for the partial set multi-cover problem ⋮ On rooted \(k\)-connectivity problems in quasi-bipartite digraphs ⋮ Spider Covering Algorithms for Network Design Problems ⋮ A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem ⋮ Approximating Survivable Networks with Minimum Number of Steiner Points ⋮ Breaking ther_maxBarrier: Enhanced Approximation Algorithms for Partial Set Multicover Problem

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