Essec\Faculty\Model\Contribution {#2233 ▼
#_index: "academ_contributions"
#_id: "10619"
#_source: array:26 [
"id" => "10619"
"slug" => "10619-the-two-level-diameter-constrained-spanning-tree-problem"
"yearMonth" => "2015-04"
"year" => "2015"
"title" => "The Two-Level Diameter Constrained Spanning Tree Problem"
"description" => "GOUVEIA, L., LEITNER, M. et LJUBIC, I. (2015). The Two-Level Diameter Constrained Spanning Tree Problem. <i>Mathematical Programming</i>, 150(1), pp. 49-78. 
GOUVEIA, L., LEITNER, M. et LJUBIC, I. (2015). The Two-Level Diameter Constrained Spanning Tree Prob "
"authors" => array:3 [
0 => array:3 [
"name" => "LJUBIC Ivana"
"bid" => "B00683004"
"slug" => "ljubic-ivana"
]
1 => array:1 [
"name" => "GOUVEIA Luis"
]
2 => array:1 [
"name" => "LEITNER Markus"
]
]
"ouvrage" => ""
"keywords" => []
"updatedAt" => "2021-07-13 14:31:39"
"publicationUrl" => "https://www.semanticscholar.org/paper/The-two-level-diameter-constrained-spanning-tree-Gouveia-Leitner/f5d267d43a2b0d4dce0226713ccbd3e3b2b5fb22 https://www.semanticscholar.org/paper/The-two-level-diameter-constrained-spanning-tree-Gouveia-Leitn "
"publicationInfo" => array:3 [
"pages" => "49-78"
"volume" => "150"
"number" => "1"
]
"type" => array:2 [
"fr" => "Articles"
"en" => "Journal articles"
]
"support_type" => array:2 [
"fr" => "Revue scientifique"
"en" => "Scientific journal"
]
"countries" => array:2 [
"fr" => null
"en" => null
]
"abstract" => array:2 [
"fr" => "In this article, we introduce the two-level diameter constrained spanning tree problem (2-DMSTP), which generalizes the classical DMSTP by considering two sets of nodes with different latency requirements. We first observe that any feasible solution to the 2-DMSTP can be viewed as a DMST that contains a diameter constrained Steiner tree. This observation allows us to prove graph theoretical properties related to the centers of each tree which are then exploited to develop mixed integer programming formulations, valid inequalities, and symmetry breaking constraints. In particular, we propose a novel modeling approach based on a three-dimensional layered graph. In an extensive computational study we show that a branch-and-cut algorithm based on the latter model is highly effective in practice. In this article, we introduce the two-level diameter constrained spanning tree problem (2-DMSTP), wh "
"en" => "In this article, we introduce the two-level diameter constrained spanning tree problem (2-DMSTP), which generalizes the classical DMSTP by considering two sets of nodes with different latency requirements. We first observe that any feasible solution to the 2-DMSTP can be viewed as a DMST that contains a diameter constrained Steiner tree. This observation allows us to prove graph theoretical properties related to the centers of each tree which are then exploited to develop mixed integer programming formulations, valid inequalities, and symmetry breaking constraints. In particular, we propose a novel modeling approach based on a three-dimensional layered graph. In an extensive computational study we show that a branch-and-cut algorithm based on the latter model is highly effective in practice. In this article, we introduce the two-level diameter constrained spanning tree problem (2-DMSTP), wh "
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2025-04-02T10:21:47.000Z"
"docTitle" => "The Two-Level Diameter Constrained Spanning Tree Problem"
"docSurtitle" => "Articles"
"authorNames" => "<a href="/cv/ljubic-ivana">LJUBIC Ivana</a>, GOUVEIA Luis, LEITNER Markus"
"docDescription" => "<span class="document-property-authors">LJUBIC Ivana, GOUVEIA Luis, LEITNER Markus</span><br><span class="document-property-authors_fields">Systèmes d'Information, Data Analytics et Opérations</span> | <span class="document-property-year">2015</span> <span class="document-property-authors">LJUBIC Ivana, GOUVEIA Luis, LEITNER Markus</span><br><span c "
"keywordList" => ""
"docPreview" => "<b>The Two-Level Diameter Constrained Spanning Tree Problem</b><br><span>2015-04 | Articles </span>"
"docType" => "research"
"publicationLink" => "<a href="https://www.semanticscholar.org/paper/The-two-level-diameter-constrained-spanning-tree-Gouveia-Leitner/f5d267d43a2b0d4dce0226713ccbd3e3b2b5fb22" target="_blank">The Two-Level Diameter Constrained Spanning Tree Problem</a> <a href="https://www.semanticscholar.org/paper/The-two-level-diameter-constrained-spanning-tree-Gouv "
]
+lang: "fr"
+"_type": "_doc"
+"_score": 8.856291
+"parent": null
}
