The node-weighted steiner tree problem
From MaRDI portal
Publication:3789370
DOI10.1002/net.3230170102zbMath0645.90092OpenAlexW2140951480MaRDI QIDQ3789370
Publication date: 1987
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.3230170102
Lagrangian relaxationbranch and boundsubgradient optimizationheuristic proceduresNP- completetight lower boundsnode-associated weightsnode-weighted Steiner triple tree problem
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Integer programming (90C10) Combinatorial optimization (90C27)
Related Items
Arborescence polytopes for series-parallel graphs, Optimal relay node placement in delay constrained wireless sensor network design, Exact algorithms for budgeted prize-collecting covering subgraph problems, Node-weighted Steiner tree approximation in unit disk graphs, Branch-and-price approaches for the network design problem with relays, Approximation schemes for node-weighted geometric Steiner tree problems, An exact algorithm to extend lifetime through roles allocation in sensor networks with connectivity constraints, Node connectivity augmentation via iterative randomized rounding, Solving Steiner trees: Recent advances, challenges, and perspectives, The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches, Swap-vertex based neighborhood for Steiner tree problems, Algorithmic expedients for the prize collecting Steiner tree problem, A RELAX-AND-CUT ALGORITHM FOR THE KNAPSACK NODE WEIGHTED STEINER TREE PROBLEM, Facets of two Steiner arborescence polyhedra, An SST-based algorithm for the steiner problem in graphs, The Bursty Steiner Tree Problem, Local search with perturbations for the prize-collecting Steiner tree problem in graphs, Steiner trees and polyhedra, Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, Generalized network design problems., Weighted connected domination and Steiner trees in distance-hereditary graphs, A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs, Combinatorial optimization in system configuration design, Strong lower bounds for the prize collecting Steiner problem in graphs, Approximation algorithms for constructing required subgraphs using stock pieces of fixed length, Two Constant Approximation Algorithms for Node-Weighted Steiner Tree in Unit Disk Graphs, An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem, The Steiner tree polytope and related polyhedra, Exact approaches for solving robust prize-collecting Steiner tree problems
Cites Work
