Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem
From MaRDI portal
Publication:4620424
DOI10.1137/17M1145963zbMath1410.90130MaRDI QIDQ4620424
Daniel Rehfeldt, Thorsten Koch
Publication date: 8 February 2019
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)
Related Items
Imposing Contiguity Constraints in Political Districting Models, On the Exact Solution of Prize-Collecting Steiner Tree Problems, New formulations and branch-and-cut procedures for the longest induced path problem, Optimal connected subgraphs: Integer programming formulations and polyhedra, Maximum weighted induced forests and trees: new formulations and a computational comparative review, Solving Steiner trees: Recent advances, challenges, and perspectives, Vertex covering with capacitated trees, Mixed-integer programming techniques for the connected max-\(k\)-cut problem
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polyhedral study of the connected subgraph problem
- A robust and scalable algorithm for the Steiner problem in graphs
- On imposing connectivity constraints in integer programs
- Thinning out Steiner trees: a node-based model for uniform edge costs
- SCIP-Jack -- a solver for STP and variants with parallelization extensions
- Solving generalized maximum-weight connected subgraph problem for network enrichment analysis
- A data structure for dynamic trees
- Reduction tests for the prize-collecting Steiner problem
- Conflict analysis in mixed integer programming
- Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem
- A dual ascent approach for steiner tree problems on a directed graph
- Solving Connected Subgraph Problems in Wildlife Conservation
- Solving Steiner tree problems in graphs to optimality
- Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP
- The Rooted Maximum Node-Weight Connected Subgraph Problem
- A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems
- The Maximum Weight Connected Subgraph Problem
- Efficient Greedy Heuristics For Steiner Tree Problems Using Reolptimization And Super Modularity
- The NP-completeness column: An ongoing guide
- Improved algorithms for the Steiner problem in networks
