Optimal connected subgraphs: Integer programming formulations and polyhedra
From MaRDI portal
Publication:6064164
DOI10.1002/net.22101OpenAlexW4281397280MaRDI QIDQ6064164
Thorsten Koch, Daniel Rehfeldt, Unnamed Author
Publication date: 12 December 2023
Published in: Networks (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/net.22101
exact solutionSteiner tree problemintegralityconnected subgraphsconnected subgraph polytopemaximum-weight connected subgraph probleminduced connectivity
Cites Work
- Polyhedral study of the connected subgraph problem
- Integer linear programming models for topology optimization in sheet metal design
- The Steiner tree problem
- Arborescence polytopes for series-parallel graphs
- On imposing connectivity constraints in integer programs
- Thinning out Steiner trees: a node-based model for uniform edge costs
- An Integer Programming Approach for Fault-Tolerant Connected Dominating Sets
- A dual ascent approach for steiner tree problems on a directed graph
- Faster Steiner Tree Computation in Polynomial-Space
- Solving Connected Subgraph Problems in Wildlife Conservation
- Connections in Networks: Hardness of Feasibility Versus Optimality
- 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
- 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
- Imposing Connectivity Constraints in Forest Planning Models
- The Maximum Weight Connected Subgraph Problem
- A catalog of steiner tree formulations
- Optimal Political Districting by Implicit Enumeration Techniques
- A lower bound for the steiner tree problem in directed graphs
- The NP-completeness column: An ongoing guide
- A comparison of Steiner tree relaxations
- Stronger path‐based extended formulation for the Steiner tree problem
- Solving Steiner trees: Recent advances, challenges, and perspectives
