An exact algorithm for the Steiner Tree Problem with Delays

Valeria Leggieri*, Mohamed Haouari, Chefi Triki

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


The Steiner Tree Problem with Delays (STPD) is a variant of the well-known Steiner Tree Problem in which the delay on each path between a source node and a terminal node is limited by a given maximum value. We propose a Branch-and-Cut algorithm for solving this problem using a formulation based on lifted Miller-Tucker-Zemlin subtour elimination constraints. The effectiveness of the proposed algorithm is assessed through computational experiments carried out on dense benchmark instances.

Original languageEnglish
Pages (from-to)223-230
Number of pages8
JournalElectronic Notes in Discrete Mathematics
Issue numberC
Publication statusPublished - Aug 2010


  • Branch-and-Cut
  • MTZ subtour elimination constraints
  • Steiner Tree Problem

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'An exact algorithm for the Steiner Tree Problem with Delays'. Together they form a unique fingerprint.

Cite this