Name
Abstract | ||
|---|---|---|
In this paper, we prove several inapproximability results on the P 3 -convexity and the geodesic convexity in graphs. We prove that determining the P 3 -hull number and the geodetic hull number are APX-hard problems. We prove that the Carathéodory number, the Radon number and the convexity number of both convexities are O ( n 1 - ε ) -inapproximable in polynomial time for every ε 0 , unless P = NP . We also prove that the interval numbers of both convexities are W 2 -hard and O ( log ¿ n ) -inapproximable in polynomial time, unless P = NP . Moreover, these results hold for bipartite graphs in the P 3 -convexity. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.tcs.2015.06.059 | Theoretical Computer Science |
Keywords | Field | DocType |
P-3-convexity,geodetic convexity,APX-hardness,inapproximability results,hull number,Caratheodory number,Radon number,convexity number,interval number | Discrete mathematics,Graph,Mathematical optimization,Combinatorics,Convexity,Geodetic datum,Hull number,Bipartite graph,Time complexity,Mathematics | Conference |
Volume | Issue | ISSN |
600 | C | 0304-3975 |
Citations | PageRank | References |
6 | 0.54 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erika M. M. Coelho | 1 | 15 | 5.27 |
| Mitre Dourado | 2 | 90 | 18.43 |
| Rudini Menezes Sampaio | 3 | 26 | 6.52 |