1987/01/01 by Arie Segev · 2 citations
Computer Science · Engineering · #Formal Methods in Verification #Optimization and Packing Problems #VLSI and FPGA Design Techniques
paper · doi:10.1002/net.3230170102
crossref issued 1987/01/01 · crossref published 1987/01/01 · crossref published-print 1987/01/01 · openalex publication_date 1987/01/01 · crossref published-online 2006/10/11 · crossref created 2007/05/11 · crossref deposited 2023/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/26 · crossref indexed 2026/07/31
Abstract The general Node‐Weighted Steiner Tree problem is an extension of the standard Steiner Tree problem by the addition of node‐associated weights. This article analyzes a special case of that problem, where the set of nodes, which must be included in the solution tree, consists of a single node, and all node weights are negative. The special case is shown to be NP‐Complete, its integer programming formulation is presented, and heuristic procedures are proposed. Using Lagrangian relaxation and subgradient optimization, tight lower bounds were derived and utilized by a branch and bound algorithm. The effectiveness of the developed procedures is demonstrated by a set of computational experiments.