The Generalized Minimum Branch Vertices Problem: Properties and Polyhedral Analysis

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 n...

Full description

Saved in:
Bibliographic Details
Published in:Journal of optimization theory and applications 2021-02, Vol.188 (2), p.356-377
Main Authors: Carrabs, Francesco, Cerulli, Raffaele, D’Ambrosio, Ciriaco, Laureana, Federica
Format: Article
Language:English
Subjects:
Apexes
Applications of Mathematics
Calculus of Variations and Optimal Control
Optimization
Clusters
Engineering
Graph theory
Inequalities
Integer programming
Linear programming
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Properties (attributes)
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0022-3239
1573-2878
DOI:10.1007/s10957-020-01783-x