The Maximum Weight Connected Subgraph Problem

DOI10.1007/978-3-642-38189-8_11zbMath1317.90299OpenAlexW201760388WikidataQ56977047 ScholiaQ56977047MaRDI QIDQ5265172

Petra Mutzel, Eduardo Álvarez-Miranda, Ivana Ljubić

Publication date: 22 July 2015

Published in: Facets of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-38189-8_11

zbMATH Keywords

connected subgraph polytopeinteger linear programming formulation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10)

Related Items (25)

A new branch-and-cut approach for the generalized regenerator location problem ⋮ Exact algorithms for budgeted prize-collecting covering subgraph problems ⋮ Trajectory optimization under kinematical constraints for moving target search ⋮ A relax-and-cut framework for large-scale maximum weight connected subgraph problems ⋮ Imposing Contiguity Constraints in Political Districting Models ⋮ On the Exact Solution of Prize-Collecting Steiner Tree Problems ⋮ Multicriteria saliency detection: a (exact) robust network design approach ⋮ Algorithms for the Maximum Weight Connected $$k$$-Induced Subgraph Problem ⋮ Downstream protection value: detecting critical zones for effective fuel-treatment under wildfire risk ⋮ New formulations and branch-and-cut procedures for the longest induced path problem ⋮ On imposing connectivity constraints in integer programs ⋮ 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 ⋮ New formulations for two location problems with interconnected facilities ⋮ Vertex covering with capacitated trees ⋮ Thinning out Steiner trees: a node-based model for uniform edge costs ⋮ Swap-vertex based neighborhood for Steiner tree problems ⋮ A bi-objective network design approach for discovering functional modules linking Golgi apparatus fragmentation and neuronal death ⋮ Combining NP-Hard Reduction Techniques and Strong Heuristics in an Exact Algorithm for the Maximum-Weight Connected Subgraph Problem ⋮ A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems ⋮ Regenerator location problem: polyhedral study and effective branch-and-cut algorithms ⋮ The generalized reserve set covering problem with connectivity and buffer requirements ⋮ Sequential Monte Carlo for maximum weight subgraphs with application to solving image jigsaw puzzles ⋮ A branch-and-price procedure for clustering data that are graph connected

This page was built for publication: The Maximum Weight Connected Subgraph Problem