Discussion:Test de planarité

	Tâches à accomplir pour Test de planarité	aide
	Votre aide est la bienvenue pour corriger les arguments inconnus dans les appels de modèle, présents dans l'article : Modèle {{ Ouvrage }} : l'argument «  nature = Ph.D.↵  » ne fait pas partie des arguments gérés par le modèle {{ Ouvrage }} (dans «  Méthode d'addition de chemins  ») Modèle {{ Article }} : l'argument «  collection = Lecture Notes in Computer Science↵  » ne fait pas partie des arguments gérés par le modèle {{ Article }} (dans «  Méthode d'addition d'arêtes  ») Modèle {{ Article }} : l'argument «  numéro dans collection = 4875↵  » ne fait pas partie des arguments gérés par le modèle {{ Article }} (dans «  Méthode d'addition d'arêtes  ») Modèle {{ Article }} : l'argument «  numéro dans collection = 8572↵  » ne fait pas partie des arguments gérés par le modèle {{ Article }} (dans «  Méthode de séquence de construction  ») Modèle {{ Article }} : l'argument «  collection = Lecture Notes in Computer Science↵  » ne fait pas partie des arguments gérés par le modèle {{ Article }} (dans «  Méthode de séquence de construction  ») -- 5 février 2022 à 01:18 (CET)

Incohérences sur la complexité ?

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)