Improved methods for approximating node weighted Steiner trees and connected dominating sets.

DOI10.1006/INCO.1998.2754MaRDI QIDQ1854264zbMATH OpenOpenAlexFDO

Authors Sudipto Guha, Samir Khuller

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

zbMATH Keywords

branch-spidersgreedy algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Analysis of algorithms (68W40)

Recommendations

• scientific article; zbMATH DE number 1302025
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Approximation Algorithms for Constrained Node Weighted Steiner Tree Problems
• Approximation algorithms for constrained node weighted Steiner tree problems
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Approximation schemes for node-weighted geometric Steiner tree problems
• scientific article; zbMATH DE number 1445376

Cites work

• A fast algorithm for Steiner trees
• A General Approximation Technique for Constrained Forest Problems
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• An 11/6-approximation algorithm for the network Steiner problem
• Approximation algorithms for connected dominating sets
• scientific article; zbMATH DE number 3677874 (Why is no real title available?)
• scientific article; zbMATH DE number 1256748 (Why is no real title available?)
• Improved Approximations for the Steiner Tree Problem
• New approximation algorithms for the Steiner tree problems
• On the hardness of approximating minimization problems
• The computation of nearly minimal Steiner trees in graphs
• The Steiner problem with edge lengths 1 and 2
• The Steiner tree problem

Cited in

(46)

• 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
• Weighted connected domination and Steiner trees in distance-hereditary graphs
• A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points
• The k-hop connected dominating set problem: approximation and hardness
• Approximation algorithms for highly connected multi-dominating sets in unit disk graphs
• The General Steiner Tree-Star problem.
• 2-node-connectivity network design
• Parameterized analysis of the online priority and node-weighted Steiner tree problems
• Revisiting connected dominating sets: an almost optimal local information algorithm
• Connecting guards with minimum Steiner points inside simple polygons
• Parameterized and exact algorithms for class domination coloring
• Approximation algorithms for priority Steiner tree problems
• Combination algorithms for Steiner tree variants
• The k-hop connected dominating set problem: hardness and polyhedra
• Energy consumption minimization in ad hoc wireless and multi-interface networks
• Flooding countries and destroying dams
• scientific article; zbMATH DE number 1302025 (Why is no real title available?)
• Spider covering algorithms for network design problems
• A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
• scientific article; zbMATH DE number 913344 (Why is no real title available?)
• On the hardness of full Steiner tree problems
• More applications of the d-neighbor equivalence: acyclicity and connectivity constraints
• Listing induced Steiner subgraphs as a compact way to discover Steiner trees in graphs
• Breaking the O(ln n) Barrier: An Enhanced Approximation Algorithm for Fault-Tolerant Minimum Weight Connected Dominating Set
• Some results for the two disjoint connected dominating sets problem
• Improved approximation algorithms for (budgeted) node-weighted Steiner problems
• Approximating Steiner networks with node-weights
• Approximating Steiner Networks with Node Weights
• Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs
• Online Node-weighted Steiner Forest and Extensions via Disk Paintings
• The Node-Weighted Steiner Problem in Graphs of Restricted Node Weights
• Approximating k-Connected m-Dominating Sets
• Efficient k-shot broadcasting in radio networks
• A greedy algorithm for the minimum 2-connected m-fold dominating set problem
• The Online Broadcast Range-Assignment Problem
• The online broadcast range-assignment problem
• Navigational guidance -- a deep learning approach
• 2-node-connectivity network design
• New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs
• Cluster before you hallucinate: node-capacitated network design and energy efficient routing
• An approximation algorithm for the prize-collecting connected dominating set problem
• Sharing the cost of multicast transmissions in wireless networks

This page was built for publication: Improved methods for approximating node weighted Steiner trees and connected dominating sets.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1854264)