2020/07/14 by Adalat Jabrayilov, Jabrayilov, Adalat
Computer Science · Engineering · Mathematics · #90C05 #90C57 #Advanced Graph Theory Research #Binary tree #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.2 #Hop (telecommunications) #Integer programming #K-ary tree #Linear programming #Linear programming relaxation #Mathematical optimization #Mathematics #Minimum spanning tree #Spanning tree #Steiner tree problem #Tree (set theory) #Tree structure #Vehicle Routing Optimization Methods #acm:90C05 #acm:90C57 #cs.DM #cs.DS #k-minimum spanning tree #msc:90C05 #msc:90C57
paper · pdf · doi:10.48550/arxiv.2007.07405
published in arXiv (Cornell University) (Cornell University) · 18 pages, 15 figures, 1 table
openalex publication_date 2020/07/14 · arxiv created 2021/11/14 · arxiv updated 2021/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The hop-constrained Steiner tree problem (HSTP) is a generalization of the classical Steiner tree problem. It asks for a minimum cost subtree that spans some specified nodes of a given graph, such that the number of edges between each node of the tree and its root respects a given hop limit. This NP-hard problem has many variants, often modeled as integer linear programs. Two of the models are so-called assignment and partial-ordering based models, which yield (up to our knowledge) the best two state-of-the-art formulations for the variant Steiner tree problem with revenues, budgets, and hop constraints (STPRBH). The solution of the HSTP and its variants such as the STPRBH and the hop-constrained minimum spanning tree problem (HMSTP) is a hop-constrained tree, a rooted tree whose depth is bounded by a given hop limit. This paper provides some theoretical results that show the polyhedral advantages of the partial-ordering model over the assignment model for this class of problems. Computational results in this paper and the literature for the HSTP, STPRBH, and HMSTP show that the partial-ordering model outperforms the assignment model in practice, too; it has better linear programming relaxation and solves more instances.