The Generalized Minimum Branch Vertices Problem: Properties and Polyhedral Analysis

Francesco Carrabs (), Raffaele Cerulli (), Ciriaco D’Ambrosio () and Federica Laureana ()
Additional contact information
Francesco Carrabs: University of Salerno
Raffaele Cerulli: University of Salerno
Ciriaco D’Ambrosio: University of Salerno
Federica Laureana: University of Salerno

Journal of Optimization Theory and Applications, 2021, vol. 188, issue 2, No 3, 356-377

Abstract: Abstract This article introduces the Generalized Minimum Branch Vertices problem. Given an undirected graph, where the set of vertices is partitioned into clusters, the Generalized Minimum Branch Vertices problem consists of finding a tree spanning exactly one vertex for each cluster and having the minimum number of branch vertices, namely vertices with degree greater than two. When each cluster is a singleton, the problem reduces to the well-known Minimum Branch Vertices problem, which is NP-hard. We show some properties that any feasible solution to the problem has to satisfy. Some of these properties can be used to determine useless vertices or edges, which can be removed to reduce the size of the instances. We propose an integer linear programming formulation for the problem, we derive the dimension of the polytope, we study the trivial inequalities and introduce two new classes of valid inequalities, that are proved to be facet-defining.

Keywords: Generalized network design; Spanning tree; Branch vertices; Polyhedral analysis; 90C10; 90C35; 90C57 (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-020-01783-x Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:188:y:2021:i:2:d:10.1007_s10957-020-01783-x

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-020-01783-x

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().