Improved methods for approximating node weighted Steiner trees and connected dominating sets.
From MaRDI portal
Publication:1854264
DOI10.1006/inco.1998.2754zbMath1045.68594OpenAlexW2047723482MaRDI QIDQ1854264
Publication date: 14 January 2003
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1903/924
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)
Related Items (37)
The \(k\)-hop connected dominating set problem: hardness and polyhedra ⋮ Sharing the cost of multicast transmissions in wireless networks ⋮ Parameterized and exact algorithms for class domination coloring ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Revisiting connected dominating sets: an almost optimal local information algorithm ⋮ Connecting guards with minimum Steiner points inside simple polygons ⋮ New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs ⋮ The online broadcast range-assignment problem ⋮ Navigational guidance -- a deep learning approach ⋮ Approximation algorithms for priority Steiner tree problems ⋮ Combination algorithms for Steiner tree variants ⋮ Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set ⋮ Approximating k-Connected m-Dominating Sets ⋮ On the hardness of full Steiner tree problems ⋮ The Online Broadcast Range-Assignment Problem ⋮ Approximation algorithms for highly connected multi-dominating sets in unit disk graphs ⋮ FLOODING COUNTRIES AND DESTROYING DAMS ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings ⋮ 2-node-connectivity network design ⋮ Unnamed Item ⋮ Efficient \(k\)-shot broadcasting in radio networks ⋮ A greedy algorithm for the minimum \(2\)-connected \(m\)-fold dominating set problem ⋮ Approximation algorithms for the connected sensor cover problem ⋮ Some results for the two disjoint connected dominating sets problem ⋮ Approximating Steiner Networks with Node Weights ⋮ Construction of strongly connected dominating sets in asymmetric multihop wireless networks ⋮ A \(5+\varepsilon\)-approximation algorithm for minimum weighted dominating set in unit disk graph ⋮ Algorithms for connected set cover problem and fault-tolerant connected set cover problem ⋮ A logarithmic approximation algorithm for the minimum energy consumption broadcast subgraph problem ⋮ Combinatorial optimization in system configuration design ⋮ Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks ⋮ Parameterized analysis of the online priority and node-weighted Steiner tree problems ⋮ Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs ⋮ More Applications of the $d$-Neighbor Equivalence: Acyclicity and Connectivity Constraints ⋮ The General Steiner Tree-Star problem. ⋮ A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points ⋮ 2-node-connectivity network design
Cites Work
- Unnamed Item
- Unnamed Item
- The Steiner problem with edge lengths 1 and 2
- A fast algorithm for Steiner trees
- The Steiner tree problem
- New approximation algorithms for the Steiner tree problems
- Approximation algorithms for connected dominating sets
- An 11/6-approximation algorithm for the network Steiner problem
- Improved Approximations for the Steiner Tree Problem
- On the hardness of approximating minimization problems
- The computation of nearly minimal Steiner trees in graphs
- A General Approximation Technique for Constrained Forest Problems
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
This page was built for publication: Improved methods for approximating node weighted Steiner trees and connected dominating sets.
