Abstract | ||
---|---|---|
In this paper, we introduce a new convexity on graphs similar to the well known P3-convexity, which we will call P3∗-convexity. We show that several P3∗-convexity parameters (hull number, convexity number, Carathéodory number, Radon number, interval number and percolation time) are NP-hard even on bipartite graphs. We prove a strong relationship between this convexity and the well known geodesic convexity, which implies several NP-hardness results for the latter. In order to show that, we prove that the hull number for the P3-convexity is NP-hard even for subgraphs of grids and that the convexity number for the P3-convexity is NP-hard even for bipartite graphs with diameter 3. We also obtain linear time algorithms to determine those parameters for the above mentioned convexities for cographs and P4-sparse graphs. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1016/j.dam.2017.11.007 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Graph convexity,Geodesic convexity,Algorithms,Complexity | Graph,Discrete mathematics,Combinatorics,Convexity,Geodesic convexity,Hull number,Bipartite graph,Time complexity,Percolation,Mathematics | Journal |
Volume | ISSN | Citations |
237 | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 9 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
R. T. Araújo | 1 | 5 | 1.17 |
Rudini Menezes Sampaio | 2 | 48 | 11.44 |
Vinícius Fernandes dos Santos | 3 | 25 | 10.47 |
Jayme Luiz Szwarcfiter | 4 | 618 | 95.79 |