Skip to Main content Skip to Navigation
Journal articles

The Geodetic Hull Number is Hard for Chordal Graphs

Stéphane Bessy 1 Mitre Dourado Lucia Penso Dieter Rautenbach 2 
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Kanté and Nourine [SIAM J. Discrete Math., 30 (2016), pp. 311--326] present a polynomial time algorithm for the computation of the hull number of chordal graphs. We point out a gap in the correctness proof of their algorithm for chordal graphs and show that computing the hull number of a chordal graph is NP-hard, which most likely rules out the existence of a polynomial time algorithm.
Document type :
Journal articles
Complete list of metadata
Contributor : Stéphane Bessy Connect in order to contact the contributor
Submitted on : Tuesday, January 29, 2019 - 8:23:43 AM
Last modification on : Friday, August 5, 2022 - 3:02:53 PM

Links full text




Stéphane Bessy, Mitre Dourado, Lucia Penso, Dieter Rautenbach. The Geodetic Hull Number is Hard for Chordal Graphs. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2018, 32 (1), pp.543-547. ⟨10.1137/17M1131726⟩. ⟨lirmm-01997429⟩



Record views