✦ LIBER ✦
Le probleme d'etoiles pour graphes est np-complet
✍ Scribed by François Lalonde
- Publisher
- Elsevier Science
- Year
- 1981
- Tongue
- English
- Weight
- 884 KB
- Volume
- 33
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
Nous appelons problkme de "recoIlement de voisinages" (RV) ("'star prnblem" ou "problk~e d'ktoiles") le probEme qui consiste B savoir, &ant donnee une familje 3r de parties d'un ensemble S, s'il existe un graphe (non orient4 et sans bouclc) dont la famille de voisinages coincide avec 9". L'objectif de cet article est de montrer que le problenre RV est NP-complet. La pteuve s'appuiera sur Equivalence entre RV et le problerre de trouver un automorphisme d'ordre 2 dans un graphe quelconque (AUK!). La NP-completude de AUT2 a et6 demontree par Anna Lubiw [5].