The Geodetic Hull Number is Hard for Chordal Graphs - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue SIAM Journal on Discrete Mathematics Année : 2018

The Geodetic Hull Number is Hard for Chordal Graphs

Stéphane Bessy
Mitre Dourado
  • Fonction : Auteur
Lucia Penso
  • Fonction : Auteur

Résumé

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.

Dates et versions

lirmm-01997429 , version 1 (29-01-2019)

Identifiants

Citer

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

Altmetric

Partager

More