Algorithmic and structural aspects of the P
            3‐Radon number

Algorithmic and structural aspects of the P 3‐Radon number

0.00 Avg rating0 Votes
Article ID: iaor20133936
Volume: 206
Issue: 1
Start Page Number: 75
End Page Number: 91
Publication Date: Jul 2013
Journal: Annals of Operations Research
Authors: , , , , ,
Keywords: convexity index, trees
Abstract:

The generalization of classical results about convex sets in ℝ n to abstract convexity spaces, defined by sets of paths in graphs, leads to many challenging structural and algorithmic problems. Here we study the Radon number for the P 3‐convexity on graphs. P 3‐convexity has been proposed in connection with rumour and disease spreading processes in networks and the Radon number allows generalizations of Radon’s classical convexity result. We establish hardness results and describe efficient algorithms for trees.

Reviews

Required fields are marked *. Your email address will not be published.