article
Authors: Massinissa Merabet, Miklos Molnar, Sylvain Durand
Journal of Combinatorial Optimization, Volume 36, Issue 3
Pages 789 - 811
Published: 01 October 2018 Publication History
Metrics
Total Citations0Total Downloads0Last 12 Months0
Last 6 weeks0
New Citation Alert added!
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my Alerts
New Citation Alert!
Please log in to your account
- View Options
- References
- Media
- Tables
- Share
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 hom*omorphism 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.
References
[1]
Ali M, Deogun JS (2000) Power-efficient design ofmulticast wavelength-routed networks. IEEE J Sel Areas Commun 18(10):1852-1862.
Digital Library
[2]
Bauer F, Varma A (1995) Degree-constrained multicasting in point-to-point networks. In: Proceedings of IEEE INFOCOM, pp 369-376.
[3]
Cerulli R, Gentili M, Iossa A (2009) Bounded-degree spanning tree problems: models and new algorithms. Comput Optim Appl 42(3):353-370.
Digital Library
[4]
Christofides N, Mingozzi A, Toth P (1981) Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations. Math Programm 20(1):255-282.
[5]
Cornuéjols G, Fonlupt J, Naddef D (1985) The traveling salesman problem on a graph and some related integer polyhedra. Math Programm 33(1):1-27.
Digital Library
[6]
Deo N, Hakimi L (1968) The shortest generalized hamiltonian tree. In: 6th annual allerton conference, Illinois, pp 879-888.
[7]
Fleischmann B (1985) A cutting plane procedure for the travelling salesman problem on road networks. Eur J Oper Res 21(3):307-317.
[8]
Furer M, Raghavachari B (1992) Approximating the minimum degree spanning tree to within one from the optimal degree. In: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, SODA '92, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, pp 317-324.
[9]
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co, New York.
[10]
Goemans M (2006) Minimum bounded degree spanning trees. In: 47th annual IEEE symposium on foundations of computer science, 2006. FOCS '06, pp 273-282.
[11]
Hell P, Zhu X (1994) hom*omorphisms to oriented paths. Discrete Math 132(1):107-114.
Digital Library
[12]
Klingman D, Napier A, Stutz J (1974) A program for generating large scale capacitated assignment, transportation, and minimum cost flow network problems. Manage Sci 20(5):814-821.
Digital Library
[13]
Krishnamoorthy M, Ernst AT, Sharaiha YM (2001) Comparison of algorithms for the degree constrained minimum spanning tree. J Heuristics 7(6):587-611.
Digital Library
[14]
Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7(1):48-50.
[15]
Makhorin A (2009), GNU Linear Programming Kit (GLPK) v 4.38, gnu project Edition.
[16]
Molnar M (2008a) Hierarchies for constrained partial spanning problems in graphs, Technical report PI-1900.
[17]
Molnar M (2008b) Hierarchies to solve constrained spanning problem, Private communication.
[18]
Molnar M, Durand S, Merabet M (2014) Approximation of the degree-constrained minimum spanning hierarchies. In: Halldorsson MM (ed) Structural information and communication complexity: 21st international colloquium, SIROCCO 2014, Takayama, Japan. Proceedings, Springer International Publishing, pp 96-107.
[19]
Obruca AK (1968) Spanning tree manipulation and the travelling salesman problem. Comput J 10(4):374-377.
[20]
Orloff CS (1974) A fundamental problem in vehicle routing. Networks 4(1):35-64.
[21]
Polzin T, Daneshmand SV (2001) A comparison of Steiner tree relaxations. Discrete Appl Math 112(1):241- 261 (combinatorial optimization symposium, selected papers).
Digital Library
[22]
Ravi R, Marathe MV, Ravi SS, Rosenkrantz DJ, Hunt III HB (1993) Many birds with one stone: multiobjective approximation algorithms. In: Proceedings of the twenty-fifth annual ACM symposium on theory of computing, STOC '93, ACM, New York, pp 438-447.
[23]
Ravi R, Marathe M, Ravi S et al (2001) Approximation algorithms for degree-constrained minimum-cost network-design problems. Algorithmica 31:58.
[24]
Singh M, Lau LC (2007) Approximating minimum bounded degree spanning trees to within one of optimal. In: Proceedings of the thirty-ninth annual ACM symposium on theory of computing, STOC '07, ACM, New York, pp 661-670.
[25]
Singh M, Zenklusen R (2016) k-trails: Recognition, complexity, and approximations. In: Louveaux Q, Skutella M (eds) Integer programming and combinatorial optimization: 18th international conference, IPCO 2016, Liège, Belgium, 1-3 June 2016, Proceedings, Springer International Publishing, Cham, pp 114-125.
[26]
Uchoa E, f*ckasawa R, Lysgaard J, Pessoa A, de Aragão MP, Andrade D (2008) Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation. Math Programm 112(2):443-472.
Digital Library
[27]
Zhou F, Molnar M, Cousin B (2010) Light-hierarchy: the optimal structure for multicast routing in wdm mesh networks. In: ISCC, pp 611-616.
Index Terms
ILP formulation of the degree-constrained minimum spanning hierarchy problem
Mathematics of computing
Discrete mathematics
Graph theory
Graph algorithms
Network flows
Trees
Theory of computation
Design and analysis of algorithms
Graph algorithms analysis
Network flows
Index terms have been assigned to the content through auto-classification.
Recommendations
- Spanning Trees with Many Leaves in Graphs With Minimum Degree Three
We present two lower bounds for the maximum number of leaves over all spanning trees of a graph. For connected, triangle-free graphs on $n$ vertices, with minimum degree at least three, we show that a spanning tree with at least $(n+4)/3$ leaves exists. ...
Read More
- The min-degree constrained minimum spanning tree problem: Formulations and Branch-and-cut algorithm
Given an edge weighted undirected graph G and a positive integer d, the Min-Degree Constrained Minimum Spanning Tree Problem (MDMST) consists of finding a minimum cost spanning tree of G, such that each vertex is either a leaf or else has degree at ...
Read More
- The subdivision-constrained minimum spanning tree problem
Motivated by the constrained minimum spanning tree (CST) problem inHassin and Levin [R. Hassin, A. Levin, An efficient polynomial timeapproximation scheme for the constrained minimum spanning treeproblem using matroid intersection, SIAM Journal on ...
Read More
Comments
Information & Contributors
Information
Published In
Journal of Combinatorial Optimization Volume 36, Issue 3
October 2018
431 pages
ISSN:1382-6905
Issue’s Table of Contents
Copyright © Copyright © 2018 Springer Science+Business Media, LLC, part of Springer Nature.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 October 2018
Author Tags
- DCMSH
- DCMST
- Degree-constrained spanning problem
- ILP
- Integer linear programming
- Spanning hierarchy
- Spanning tree
Qualifiers
- Article
Contributors
Other Metrics
View Article Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
Total Citations
Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 26 Aug 2024
Other Metrics
View Author Metrics
Citations
View Options
View options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in
Full Access
Get this Publication
Media
Figures
Other
Tables
