A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
From MaRDI portal
Publication:4840221
DOI10.1006/jagm.1995.1029zbMath0836.68046OpenAlexW1963899113MaRDI QIDQ4840221
Publication date: 11 April 1996
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/00533a82a4aaf0e19ef5245b5a151980208c5c6d
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items
Hardness and approximation results for packing Steiner trees, Optimal relay node placement in delay constrained wireless sensor network design, Approximation algorithms for the covering Steiner problem, Trees, paths, stars, caterpillars and spiders, Approximating Steiner Trees and Forests with Minimum Number of Steiner Points, Approximating \(k\)-connected \(m\)-dominating sets, Approximation algorithms for requirement cut on graphs, Node-weighted Steiner tree approximation in unit disk graphs, Trees, Paths, Stars, Caterpillars and Spiders, Approximation schemes for node-weighted geometric Steiner tree problems, Sharing the cost of multicast transmissions in wireless networks, Approximating activation edge-cover and facility location problems, Improved Approximation Algorithms for (Budgeted) Node-weighted Steiner Problems, Exact and Approximation Algorithms for the Expanding Search Problem, On the Exact Solution of Prize-Collecting Steiner Tree Problems, Extending the kernel for planar Steiner tree to the number of Steiner vertices, Lower and upper bounds for the spanning tree with minimum branch vertices, Secluded connectivity problems, Survivable network activation problems, Unnamed Item, Competitive and deterministic embeddings of virtual networks, Node connectivity augmentation via iterative randomized rounding, Minimum shared‐power edge cut, Spider covers and their applications, Speedup the optimization of maximal closure of a node-weighted directed acyclic graph, PTAS for minimum weighted connected vertex cover problem with \(c\)-local condition in unit disk graphs, Improved approximation algorithms for directed Steiner forest, Breaching the 2-Approximation Barrier for Connectivity Augmentation: A Reduction to Steiner Tree, A vertex-separator-based integer linear programming formulation for the partitioned Steiner tree problem, Bicriteria Approximation Tradeoff for the Node-Cost Budget Problem, Bounded-degree spanning tree problems: models and new algorithms, Approximation algorithms for priority Steiner tree problems, Distributed reformation of core-based group-shared multicast trees in mobile ad hoc networks, Approximating some network design problems with node costs, Combination algorithms for Steiner tree variants, A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM, Approximations for node-weighted Steiner tree in unit disk graphs, Solving SAT (and MaxSAT) with a quantum annealer: foundations, encodings, and preliminary results, Approximating k-Connected m-Dominating Sets, On the hardness of full Steiner tree problems, Line-of-Sight Networks, Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs, Polylogarithmic Approximation Algorithm for k-Connected Directed Steiner Tree on Quasi-Bipartite Graphs, Covering problems in edge- and node-weighted graphs, Approximation algorithms for highly connected multi-dominating sets in unit disk graphs, FLOODING COUNTRIES AND DESTROYING DAMS, Upgrading bottleneck constrained forests, Online Node-weighted Steiner Forest and Extensions via Disk Paintings, Approximating minimum power covers of intersecting families and directed edge-connectivity problems, Bounded-hops power assignment in ad hoc wireless networks, 2-node-connectivity network design, On rooted \(k\)-connectivity problems in quasi-bipartite digraphs, Wireless network design via 3-decompositions, Spider Covering Algorithms for Network Design Problems, Parameterized Complexity of Directed Steiner Tree on Sparse Graphs, Approximating Steiner trees and forests with minimum number of Steiner points, Approximation algorithms for the connected sensor cover problem, Approximating Steiner Networks with Node Weights, Algorithms for connected set cover problem and fault-tolerant connected set cover problem, Approximating Survivable Networks with Minimum Number of Steiner Points, An approximation algorithm for vehicle routing with compatibility constraints, Approximation algorithms for replenishment problems with fixed turnover times, Generalized network design problems., Two-level hub Steiner trees, Combinatorial optimization in system configuration design, Approximating fault-tolerant group-Steiner problems, Parameterized analysis of the online priority and node-weighted Steiner tree problems, Approximating the weight of shallow Steiner trees, Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs, The General Steiner Tree-Star problem., Improved methods for approximating node weighted Steiner trees and connected dominating sets., On approximability of the independent/connected edge dominating set problems, A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points, On rooted \(k\)-connectivity problems in quasi-bipartite digraphs, 2-node-connectivity network design
