Name
Abstract | ||
|---|---|---|
In the geodetic convexity of a graph G, we define the interval of a set S⊆V(G) as the set formed by S and all vertices in all shortest paths with endpoints in S. We say S is convex if it is equal to its interval. The convex hull of S can be obtained by repeatedly applying the interval function until obtaining a convex set. Here we consider the problem of determining the maximum k such that there is a set of vertices S, whose convex hull is V (G), such that it is necessary at least k applications of the interval function to obtain V (G). We show that this problem is NP-complete for bipartite graphs and give a polynomial time algorithm for distance-hereditary graphs. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.endm.2015.07.067 | Electronic Notes in Discrete Mathematics |
Keywords | Field | DocType |
Geodetic Convexity,maximum infection time,NP-completeness | Discrete mathematics,Absolutely convex set,Convexity,Combinatorics,Vertex (geometry),Bipartite graph,Convex set,Convex hull,Subderivative,Convex polytope,Mathematics | Journal |
Volume | ISSN | Citations |
50 | 1571-0653 | 0 |
PageRank | References | Authors |
0.34 | 10 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabrício Benevides | 1 | 49 | 7.53 |
| Victor Campos | 2 | 60 | 5.75 |
| Mitre Dourado | 3 | 90 | 18.43 |
| Ana Silva | 4 | 25 | 9.56 |