ILP formulation of the degree-constrained minimum spanning hierarchy problem

Massinissa Merabet (), Miklos Molnar () and Sylvain Durand ()
Additional contact information
Massinissa Merabet: Nanyang Technological University
Miklos Molnar: University of Montpellier
Sylvain Durand: University Paul Valéry Montpellier 3

Journal of Combinatorial Optimization, 2018, vol. 36, issue 3, No 6, 789-811

Abstract: Abstract Given a connected edge-weighted graph G and a positive integer B, the degree-constrained minimum spanning tree problem (DCMST) consists in finding a minimum cost spanning tree of G such that the degree of each vertex in the tree is less than or equal to B. This problem, which has been extensively studied over the last few decades, has several practical applications, mainly in networks. However, some applications do not especially impose a subgraph as a solution. For this purpose, a more flexible so-called hierarchy structure has been proposed. Hierarchy, which can be seen as a generalization of trees, is defined as a homomorphism of a tree in a graph. In this paper, we discuss the degree-constrained minimum spanning hierarchy (DCMSH) problem which is NP-hard. An integer linear program (ILP) formulation of this new problem is given. Properties of the solution are analysed, which allows us to add valid inequalities to the ILP. To evaluate the difference of cost between trees and hierarchies, the exact solution of DCMST and z problems are compared. It appears that, in sparse random graphs, the average percentage of improvement of the cost varies from 20 to 36% when the maximal authorized degree of vertices B is equal to 2, and from 11 to 31% when B is equal to 3. The improvement increases as the graph size increases.

Keywords: Degree-constrained spanning problem; Spanning hierarchy; Spanning tree; Integer linear programming; ILP; DCMSH; DCMST (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0159-4 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:jcomop:v:36:y:2018:i:3:d:10.1007_s10878-017-0159-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0159-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

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