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 metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01997429
Contributor : Stéphane Bessy <>
Submitted on : Tuesday, January 29, 2019 - 8:23:43 AM
Last modification on : Friday, December 13, 2019 - 9:32:04 AM

Links full text

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

62