Name
Abstract | ||
|---|---|---|
Recent papers investigated the maximum infection time tP3(G) of the P3-convexity (also called maximum time of 2-neighbor bootstrap percolation) and the maximum infection time tmo(G) of the monophonic convexity. In 2014, it was proved that, for bipartite graphs, deciding whether tP3(G)≥k is polynomial time solvable for k≤4, but is NP-complete for k≥5 [23]. In 2015, it was proved that deciding whether tmo(G)≥2 is NP-complete even for bipartite graphs [12]. In this paper, we investigate the maximum infection time tgd(G) of the geodesic convexity. We prove that deciding whether tgd(G)≥k is polynomial time solvable for k=1, but is NP-complete for k≥2 even for bipartite graphs. We also present an O(n3m)-time algorithm to determine tgd(G) and tmo(G) in distance-hereditary graphs. For this, we characterize all minimal hull sets of a general graph in the monophonic convexity. Moreover, we improve the complexity of the fastest known algorithm for finding a minimum hull set of a general graph in the monophonic convexity. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2015.10.009 | Theoretical Computer Science |
Keywords | Field | DocType |
Geodesic convexity,Maximum infection time,Monophonic hull number,Monophonic convexity | Discrete mathematics,Graph,Combinatorics,Convexity,Geodesic convexity,Bootstrap percolation,Bipartite graph,Time complexity,Mathematics,Geodesic | Journal |
Volume | Issue | ISSN |
609 | P2 | 0304-3975 |
Citations | PageRank | References |
3 | 0.44 | 18 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Fabrício Benevides | 1 | 49 | 7.53 |
| Victor Campos | 2 | 60 | 5.75 |
| Mitre Dourado | 3 | 90 | 18.43 |
| Rudini Menezes Sampaio | 4 | 48 | 11.44 |
| Ana Silva | 5 | 25 | 9.56 |