Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints

  • Finding connected subgraphs of maximum weight subject to additional constraints on the subgraphs is a common (sub)problem in many applications. In this paper, we study the Maximum Weight Connected Subgraph Problem with a given root node and a lower and upper capacity constraint on the chosen subgraph. In addition, the nodes of the input graph are colored blue and red, and the chosen subgraph is required to be balanced regarding its cumulated blue and red weight. This problem arises as an essential subproblem in district planning applications. We show that the problem is NP-hard and give an integer programming formulation. By exploiting the capacity and balancing condition, we develop a powerful reduction technique that is able to significantly shrink the problem size. In addition, we propose a method to strengthen the LP relaxation of our formulation by identifying conflict pairs, i.e., nodes that cannot be both part of a chosen subgraph. Our computational study confirms the positive impact of the new preprocessing technique and of the proposed conflict cuts.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Ralf BorndörferORCiD, Stephan SchwartzORCiD, William SurauORCiD
Document Type:In Proceedings
Parent Title (English):Proceedings of the 10th International Network Optimization Conference (INOC), Aachen, Germany, June 7–10, 2022
First Page:63
Last Page:68
Year of first publication:2022
Preprint:urn:nbn:de:0297-zib-84427
DOI:https://doi.org/10.48786/inoc.2022.12
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.