Name
Abstract | ||
|---|---|---|
Kante and Nourine [SIAM T. 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1137/17M1131726 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
geodesic convexity,shortest path,hull number,chordal graphs | Journal | 32 |
Issue | ISSN | Citations |
1 | 0895-4801 | 2 |
PageRank | References | Authors |
0.38 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Mitre Dourado | 2 | 90 | 18.43 |
| Lucia Draque Penso | 3 | 196 | 20.46 |
| Dieter Rautenbach | 4 | 946 | 138.87 |