Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419224 | Discrete Applied Mathematics | 2016 | 7 Pages |
Abstract
The Radon number of a graph is the minimum integer rr such that all sets of at least rr of its vertices can be partitioned into two subsets whose convex hulls intersect. Determining the Radon number of general graphs in the geodetic convexity is NP-hard. In this paper, we show the problem is polynomial for dd-dimensional grids, for all d≥1d≥1. The proposed algorithm runs in near-linear O(d(logd)1/2) time for grids of arbitrary sizes, and in sub-linear O(logd)O(logd) time when all grid dimensions have the same size.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mitre Costa Dourado, Vinícius Gusmão Pereira de Sá, Dieter Rautenbach, Jayme Luiz Szwarcfiter,