 |
HAL-LIRMM - Open Archive |  |
Journal articles
The Geodetic Hull Number is Hard for Chordal Graphs
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.
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, June 4, 2021 - 6:30:01 PM
Contributor : Stéphane Bessy <>
Submitted on : Tuesday, January 29, 2019 - 8:23:43 AM
Last modification on : Friday, June 4, 2021 - 6:30:01 PM
Links full text
