Published February 1, 2006
| Version v1
Publication
Open
Computational aspects of the Helly property: a survey
- 1. Universidade Federal do Rio de Janeiro
Description
Abstract In 1923, Eduard Helly published his celebrated theorem, which originated the well known Helly property. Say that a family of subsets has the Helly property when every subfamily of it, formed by pairwise intersecting subsets, contains a common element. There are many generalizations of this property which are relevant to some parts of mathematics and several applications in computer science. In this work, we survey computational aspects of the Helly property. The main focus is algorithmic. That is, we describe algorithms for solving different problems arising from the basic Helly property. We also discuss the complexity of these problems, some of them leading to NP-hardness results.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
ملخص في عام 1923، نشر إدوارد هيلي نظريته الشهيرة، والتي نشأت عن خاصية هيلي المعروفة. لنفترض أن عائلة من المجموعات الفرعية لها خاصية هيلي عندما تحتوي كل عائلة فرعية منها، تتكون من مجموعات فرعية متقاطعة ثنائية، على عنصر مشترك. هناك العديد من التعميمات لهذه الخاصية ذات الصلة ببعض أجزاء الرياضيات والعديد من التطبيقات في علوم الكمبيوتر. في هذا العمل، نقوم بمسح الجوانب الحسابية لخاصية هيلي. التركيز الرئيسي هو الخوارزمية. أي أننا نصف خوارزميات لحل المشكلات المختلفة الناشئة عن خاصية هيلي الأساسية. نناقش أيضًا مدى تعقيد هذه المشكلات، وبعضها يؤدي إلى نتائج صلابة NP.Translated Description (French)
Résumé En 1923, Eduard Helly publie son célèbre théorème, à l'origine de la propriété bien connue Helly. Supposons qu'une famille de sous-ensembles possède la propriété Helly lorsque chaque sous-famille de celle-ci, formée par des sous-ensembles se croisant par paires, contient un élément commun. Il existe de nombreuses généralisations de cette propriété qui sont pertinentes pour certaines parties des mathématiques et plusieurs applications en informatique. Dans ce travail, nous étudions les aspects informatiques de la propriété Helly. L'objectif principal est algorithmique. C'est-à-dire que nous décrivons des algorithmes pour résoudre différents problèmes découlant de la propriété Helly de base. Nous discutons également de la complexité de ces problèmes, certains d'entre eux conduisant à des résultats de dureté NP.Translated Description (Spanish)
Resumen En 1923, Eduard Helly publicó su célebre teorema, que originó la conocida propiedad de Helly. Digamos que una familia de subconjuntos tiene la propiedad Helly cuando cada subfamilia de la misma, formada por subconjuntos que se cruzan por pares, contiene un elemento común. Hay muchas generalizaciones de esta propiedad que son relevantes para algunas partes de las matemáticas y varias aplicaciones en informática. En este trabajo, examinamos los aspectos computacionales de la propiedad Helly. El enfoque principal es algorítmico. Es decir, describimos algoritmos para resolver diferentes problemas derivados de la propiedad básica de Helly. También discutimos la complejidad de estos problemas, algunos de los cuales conducen a resultados de dureza NP.Files
BF03192385.pdf
Files
(474.9 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:43617abeab6be00241b56d246b86d6d2
|
474.9 kB | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- الجوانب الحسابية لخاصية هيلي: مسح
- Translated title (French)
- Aspects informatiques de la propriété Helly : une enquête
- Translated title (Spanish)
- Aspectos computacionales de la propiedad Helly: una encuesta
Identifiers
- Other
- https://openalex.org/W2118179018
- DOI
- 10.1007/bf03192385
References
- https://openalex.org/W112656029
- https://openalex.org/W112858196
- https://openalex.org/W12159974
- https://openalex.org/W136694183
- https://openalex.org/W1482143660
- https://openalex.org/W1495591881
- https://openalex.org/W1549989156
- https://openalex.org/W1550662968
- https://openalex.org/W1579049696
- https://openalex.org/W1608639859
- https://openalex.org/W165014760
- https://openalex.org/W170832643
- https://openalex.org/W1976081476
- https://openalex.org/W1981103638
- https://openalex.org/W1984482290
- https://openalex.org/W1984702732
- https://openalex.org/W1986648759
- https://openalex.org/W1987058044
- https://openalex.org/W1990664809
- https://openalex.org/W1992276678
- https://openalex.org/W1992786398
- https://openalex.org/W1996303391
- https://openalex.org/W1997998268
- https://openalex.org/W2009545408
- https://openalex.org/W2013215731
- https://openalex.org/W2013568176
- https://openalex.org/W2015294925
- https://openalex.org/W2016785496
- https://openalex.org/W2017793597
- https://openalex.org/W2018115778
- https://openalex.org/W2024020828
- https://openalex.org/W2027383911
- https://openalex.org/W2029095423
- https://openalex.org/W2029597239
- https://openalex.org/W2036265926
- https://openalex.org/W2039686598
- https://openalex.org/W2048095411
- https://openalex.org/W2048237851
- https://openalex.org/W2050020552
- https://openalex.org/W2056671893
- https://openalex.org/W2058552824
- https://openalex.org/W2062210818
- https://openalex.org/W2062716045
- https://openalex.org/W2073071752
- https://openalex.org/W2074764134
- https://openalex.org/W2076481866
- https://openalex.org/W2076678027
- https://openalex.org/W2078305609
- https://openalex.org/W2080213234
- https://openalex.org/W2080459726
- https://openalex.org/W2089417393
- https://openalex.org/W2098381534
- https://openalex.org/W2098467469
- https://openalex.org/W2098652111
- https://openalex.org/W2104498537
- https://openalex.org/W2108922196
- https://openalex.org/W2111859416
- https://openalex.org/W2139340493
- https://openalex.org/W2309179828
- https://openalex.org/W2320632901
- https://openalex.org/W2604724570
- https://openalex.org/W4212835401
- https://openalex.org/W4229774746
- https://openalex.org/W4235730211
- https://openalex.org/W4242336842
- https://openalex.org/W4298414065
- https://openalex.org/W4385397173
- https://openalex.org/W47791626