Thumbnail

Complexity and algorithms for constant diameter augmentation problems

Kim, Eun Jung; Milanic, Martin; Monnot, Jérôme; Picouleau, Christophe (2022), Complexity and algorithms for constant diameter augmentation problems, Theoretical Computer Science, 904, p. 15-26. 10.1016/j.tcs.2021.05.020

View/Open
Type
Article accepté pour publication ou publié
Date
2022
Journal name
Theoretical Computer Science
Volume
904
Publisher
Elsevier
Pages
15-26
Publication identifier
Metadata
Show full item record
Author(s)
Kim, Eun Jung
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Milanic, Martin
Monnot, Jérôme
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Picouleau, Christophe
Abstract (EN)
We study the following problem: for given integers d,k and graph G, can we obtain a graph with diameter d via at most k edge deletions? We determine the computational complexity of this and related problems for different values of d.
Subjects / Keywords
Graph diameter; Blocker problem; Polynomial algorithm; NP-complete