Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
434424 | Theoretical Computer Science | 2013 | 9 Pages |
Abstract
Inspired by a result of Carathéodory [Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen, Rend. Circ. Mat. Palermo 32 (1911) 193–217], the Carathéodory number of a convexity space is defined as the smallest integer k such that for every subset U of the ground set V and every element u in the convex hull of U, there is a subset F of U with at most k elements such that u in the convex hull of F. We study the Carathéodory number for generalized interval convexities and for convexity spaces derived from finite graphs. We establish structural properties, bounds, and hardness results.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mitre C. Dourado, Dieter Rautenbach, Vinícius Fernandes dos Santos, Philipp M. Schäfer, Jayme L. Szwarcfiter,