Essec\Faculty\Model\Contribution {#2233 ▼
#_index: "academ_contributions"
#_id: "12094"
#_source: array:26 [
"id" => "12094"
"slug" => "12094-a-polyhedral-study-of-the-diameter-constrained-minimum-spanning-tree-problem"
"yearMonth" => "2020-10"
"year" => "2020"
"title" => "A polyhedral study of the diameter constrained minimum spanning tree problem"
"description" => "GOUVEIA, L., LEITNER, M. et LJUBIC, I. (2020). A polyhedral study of the diameter constrained minimum spanning tree problem. <i>Discrete Applied Mathematics</i>, 285, pp. 364-379. 
GOUVEIA, L., LEITNER, M. et LJUBIC, I. (2020). A polyhedral study of the diameter constrained minimu "
"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" => array:1 [
0 => "Integer programming, Diameter constrained trees, Facet"
]
"updatedAt" => "2021-09-24 10:33:27"
"publicationUrl" => "https://doi.org/10.1016/j.dam.2020.05.020"
"publicationInfo" => array:3 [
"pages" => "364-379"
"volume" => "285"
"number" => null
]
"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" => "This paper provides a first polyhedral study of the diameter constrained minimum spanning tree problem (DMSTP). We introduce a new set of inequalities, the circular-jump inequalities which strengthen the well-known jump inequalities. These inequalities are further generalized in two ways: either by increasing the number of partitions defining a jump, or by combining jumps with cutsets. Most of the proposed new inequalities are shown to define facets of the DMSTP polytope under very mild conditions. Currently best known lower bounds for the DMSTP are obtained from an extended formulation on a layered graph using the concept of central nodes/edges. A subset of the new families of inequalities is shown to be not implied by this layered graph formulation. This paper provides a first polyhedral study of the diameter constrained minimum spanning tree probl "
"en" => "This paper provides a first polyhedral study of the diameter constrained minimum spanning tree problem (DMSTP). We introduce a new set of inequalities, the circular-jump inequalities which strengthen the well-known jump inequalities. These inequalities are further generalized in two ways: either by increasing the number of partitions defining a jump, or by combining jumps with cutsets. Most of the proposed new inequalities are shown to define facets of the DMSTP polytope under very mild conditions. Currently best known lower bounds for the DMSTP are obtained from an extended formulation on a layered graph using the concept of central nodes/edges. A subset of the new families of inequalities is shown to be not implied by this layered graph formulation. This paper provides a first polyhedral study of the diameter constrained minimum spanning tree probl "
]
"authors_fields" => array:2 [
"fr" => "Systèmes d'Information, Data Analytics et Opérations"
"en" => "Information Systems, Data Analytics and Operations"
]
"indexedAt" => "2025-04-02T11:21:48.000Z"
"docTitle" => "A polyhedral study of the diameter constrained minimum 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">2020</span> <span class="document-property-authors">LJUBIC Ivana, GOUVEIA Luis, LEITNER Markus</span><br><span c "
"keywordList" => "<a href="#">Integer programming, Diameter constrained trees, Facet</a>"
"docPreview" => "<b>A polyhedral study of the diameter constrained minimum spanning tree problem</b><br><span>2020-10 | Articles </span> <b>A polyhedral study of the diameter constrained minimum spanning tree problem</b><br><span>2020-10 "
"docType" => "research"
"publicationLink" => "<a href="https://doi.org/10.1016/j.dam.2020.05.020" target="_blank">A polyhedral study of the diameter constrained minimum spanning tree problem</a> <a href="https://doi.org/10.1016/j.dam.2020.05.020" target="_blank">A polyhedral study of the diamet "
]
+lang: "fr"
+"_type": "_doc"
+"_score": 8.813438
+"parent": null
}
