1786. On the NP-hardness of the degree-constrained network design problem
Invited abstract in session WB-20: Complexity and Approximation, stream Combinatorial Optimization.
Wednesday, 10:30-12:00Room: Esther Simpson 2.11
Authors (first author is the speaker)
| 1. | Brieuc Pierre
|
| CORE, UCLouvain-LIDAM | |
| 2. | Francesco Pisanu
|
| LIPN, Université Sorbonne Paris Nord | |
| 3. | Daniele Catanzaro
|
| Center for Operations Research and Econometrics, Université Catholique de Louvain |
Abstract
Given a connected weighted graph G=(V,E), the k-Network Design Problem (k-NDP) consists of deciding whether there exists a spanning tree in G, whose internal vertices have degree k and such that the shortest path between each pair of leaves is smaller than or equal to a given constant. This problem finds applications both in epidemiology and in the modeling of the evolutionary relationships among species. Here we show that the k-NDP is NP-complete for every every natural k greater or equal to 3.
Keywords
- Network Design
- Complexity and Approximation
- Graphs and Networks
Status: accepted
Back to the list of papers