Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem

Markus Leitner*

*Corresponding author for this work

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

Abstract This paper studies the generalized hop-constrained minimum spanning tree problem (GHMSTP) which has applications in backbone network design subject to quality-of-service constraints that restrict the maximum number of intermediate routers along each communication path. Different possibilities to model the GHMSTP as an integer linear program and strengthening valid inequalities are studied. The obtained formulations are compared theoretically, i.e., by means of their linear programming relaxation. In addition, branch-and-cut approaches based on these formulations are developed and compared in a computational study.

Original languageEnglish
Article number3812
Pages (from-to)1-18
Number of pages18
JournalComputers and Operations Research
Volume65
DOIs
Publication statusPublished - 18 Jul 2016
Externally publishedYes

Keywords

  • Branch-and-cut
  • Generalized network design
  • Hop-constraints
  • Integer programming
  • Layered graph

Fingerprint

Dive into the research topics of 'Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem'. Together they form a unique fingerprint.

Cite this