Name
Abstract | ||
|---|---|---|
Let C be a convexity on a set X and denote the convex hull of S⊆X in C by H(S). The Helly number (Radon number) of C is the minimum integer k such that, for every S⊆X with at least k+1 elements, it holds ⋂v∈SH(S∖{v})≠∅ (there is a bipartition of S into sets S1 and S2 with H(S1)∩H(S2)≠∅). In this work, we show that there is no approximation algorithm for the Helly or the Radon number of a graph G of order n in the geodetic convexity to within a factor n1−ε for any ε>0, unless P = NP, even if G is bipartite. Furthermore, we present upper bounds for both parameters in the geodetic convexity of bipartite graphs and characterize the families of graphs achieving the bound for the Helly number. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.dam.2017.07.032 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Bipartite graphs,Geodetic convexity,Helly number,Inapproximability,Radon number,Upper bound | Integer,Approximation algorithm,Discrete mathematics,Geodetic datum,Combinatorics,Convexity,Helly's theorem,Radon,Bipartite graph,Convex hull,Mathematics | Journal |
Volume | Issue | ISSN |
232 | C | 0166-218X |
Citations | PageRank | References |
0 | 0.34 | 4 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mitre Dourado | 1 | 90 | 18.43 |
| Aline R. da Silva | 2 | 0 | 0.34 |