Discussion:Test de planarité
Autres discussions [liste]
- Admissibilité
- Neutralité
- Droit d'auteur
- Article de qualité
- Bon article
- Lumière sur
- À faire
- Archives
- Commons
Tâches à accomplir pour Test de planarité | aide | |
|
Incohérences sur la complexité ?[modifier le code]
En lisant l'abstract de cet article et l'interview de ses auteurs dans Quanta Magazine j'apprends que l'état de l'art depuis 1996 était un algorithme d'une complexité en √n, améliorée cette année en (log n)^3. Cela n'est absolument pas raccord avec l'article qui, tout comme la version anglaise, parle d'algorithmes au mieux linéaires. Même s'il s'agit ici d'un test à réaliser à chaque ajout direct d'une arête il me semble que ce n'est pas très cohérent. --Gokimines (discuter) 17 septembre 2020 à 12:57 (CEST)
- Bonjour, merci pour ces références bibliographiques. Il me semble qu'il n'y a pas contradiction dans la mesure où ce nouvel algorithme concerne est un test dynamique : le graphe peut évoluer. Il faudrait ajouter ces références à l'article. -- ManiacParisien (discuter) 18 septembre 2020 à 07:09 (CEST)
- J'ai ajouté les références dans la section "Variantes".-- ManiacParisien (discuter) 18 septembre 2020 à 07:50 (CEST)