Transformations for the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to sap

DOI10.4208/JCM.1709-M2017-0002MaRDI QIDQ4688185zbMATH OpenOpenAlexWikidataFDO

Authors Daniel Rehfeldt, Thorsten Koch

Publication date 22 October 2018

Published in Journal of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/0b34b0f7f862200015dc83bec12a9a8f0c4edd58

zbMATH Keywords

dual-ascent heuristicsgraph transformationsmaximum-weight connected subgraph problemprize-collecting Steiner tree problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Reduction techniques for the prize collecting Steiner tree problem and the maximum-weight connected subgraph problem
• Variations of the prize‐collecting Steiner tree problem
• scientific article; zbMATH DE number 1982172
• scientific article; zbMATH DE number 1445375
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem

Cited in

(5)

• SCIP-Jack -- a solver for STP and variants with parallelization extensions
• Reduction techniques for the prize collecting Steiner tree problem and the maximum-weight connected subgraph problem
• Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem
• On the Exact Solution of Prize-Collecting Steiner Tree Problems
• A dual ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems

Describes a project that uses

Uses Software

• SCIP-Jack
• SCIP

This page was built for publication: Transformations for the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to sap

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4688185)