On the Exact Solution of Prize-Collecting Steiner Tree Problems
From MaRDI portal
Publication:5085996
DOI10.1287/ijoc.2021.1087OpenAlexW3201760816MaRDI QIDQ5085996
Thorsten Koch, Daniel Rehfeldt
Publication date: 30 June 2022
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.09068
complexityexact solutionnode-weighted Steiner treeprize-collecting Steiner treemaximum-weight connected subgraph problem
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- A note on the prize collecting traveling salesman problem
- A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs
- A divide and conquer matheuristic algorithm for the prize-collecting Steiner tree problem
- Thinning out Steiner trees: a node-based model for uniform edge costs
- SCIP-Jack -- a solver for STP and variants with parallelization extensions
- Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
- Reduction tests for the prize-collecting Steiner problem
- An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
- Local search with perturbations for the prize-collecting Steiner tree problem in graphs
- Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
- Reduction techniques for the prize collecting Steiner tree problem and the maximum-weight connected subgraph problem
- A dual ascent approach for steiner tree problems on a directed graph
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- Solving Steiner tree problems in graphs to optimality
- Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem
- Algorithms for node‐weighted Steiner tree and maximum‐weight connected subgraph
- Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP
- A General Approximation Technique for Constrained Forest Problems
- A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees
- Reducibility among Combinatorial Problems
- A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems
- The Maximum Weight Connected Subgraph Problem
- A catalog of steiner tree formulations
- The steiner problem in graphs
- Improved algorithms for the Steiner problem in networks
