Local search with perturbations for the prize-collecting Steiner tree problem in graphs

DOI10.1002/net.1023zbMath1014.90078OpenAlexW1991107961MaRDI QIDQ2747806

S. A. Canuto, Mauricio G. C. Resende, Celso Carneiro Ribeiro

Publication date: 14 October 2001

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.1023

zbMATH Keywords

Steiner problemvariable neighborhood searchnetwork designpath-relinking

Mathematics Subject Classification ID

Trees (05C05) Search theory (90B40) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27)

Related Items

Optimal relay node placement in delay constrained wireless sensor network design, A divide and conquer matheuristic algorithm for the prize-collecting Steiner tree problem, Stabilizing branch‐and‐price for constrained tree problems, On the Exact Solution of Prize-Collecting Steiner Tree Problems, The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches, Swap-vertex based neighborhood for Steiner tree problems, Mathematical formulations and solution methods for the uncapacitated \(r\)-allocation \(p\)-hub maximal covering problem, Bayesian stopping rules for greedy randomized procedures, Algorithmic expedients for the prize collecting Steiner tree problem, Reduction tests for the prize-collecting Steiner problem, Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms, Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints, Variable neighbourhood search: methods and applications, A fast prize-collecting Steiner forest algorithm for functional analyses in biological networks, Noising methods for a clique partitioning problem, Randomized heuristics for the Max-Cut problem, A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem, Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, The noising methods: A generalization of some metaheuristics, An efficient algorithm for the Steiner tree problem with revenue, bottleneck and hop objective functions, Hybridizations of GRASP with path relinking for the far from most string problem, A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs, Combinatorial optimization in system configuration design, Variable neighbourhood search: Methods and applications, Variations of the prize‐collecting Steiner tree problem, Strong lower bounds for the prize collecting Steiner problem in graphs, Exploring the constrained maximum edge-weight connected graph problem, Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree, An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem, Exact approaches for solving robust prize-collecting Steiner tree problems

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• The noising method: A new method for combinatorial optimization
• Variable neighborhood search
• Greedy randomized adaptive search procedures
• The node-weighted steiner tree problem
• A More Portable Fortran Random Number Generator
• A strong lower bound for the Node Weighted Steiner Tree Problem
• GRASP and Path Relinking for 2-Layer Straight Line Crossing Minimization