On the Carath茅odory number of interval and graph convexities

详细信息    查看全文

• 作者：Mitre C. Dourado ; Dieter Rautenbach ; Vin铆cius Fern ; es dos Santos ; Philipp M. Sch盲fer ; Jayme L. Szwarcfiter
• 关键词：Convexity space ; Carath&eacute ; odory number ; Interval convexity ; Geodetic convexity ; Monophonic convexity ; P3P3-convexity
• 刊名：Theoretical Computer Science
• 出版年：28 October, 2013
• 年：2013
• 卷：510
• 期：Complete
• 页码：127-135
• 全文大小：300 K

文摘

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.