Auteurs, références | Complexité | Commentaires |
---|---|---|
James, Stanton, Cowan [JSC72] | O(n4) | premier algorithme polynomial |
Maurer [Mau77] | O(n4) | graphes orientés |
Blass [Bla78] | O(n3) | |
Habib, Maurer [HM79] | O(n3) | |
Habib [Hab81] | O(n3) | graphes orientés |
Cunningham [Cun82] | O(n3) | graphes orientés |
Steiner [Ste82] | O(n3) | |
Spinrad [Spi82] | O(n2) | |
Buer, Möhring [BM83] | O(n3) | |
Corneil, Perl, Stewart [CPS85] | O(n+m) | cographes |
McCreary [McCreary87] | O(n3) | |
Muller, Spinrad [MS89] | O(n2) | incrémental |
Adhar, Peng [AP90] | O(log2 n), O(mn) proc. | parallèle, cographes, CRCW-PRAM |
Lin, Olariu [LO91] | O(log n), O(mn) proc. | parallèle, cographes, EREW-PRAM |
Spinrad [Spi92] | O(n+mα(m,n)) | |
Cournier, Habib [CH93] | O(n+mα(m,n)) | |
McConnell, Spinrad [MS94,MS97,MS99] | O(n+m) | |
Cournier, Habib [CH94] | O(n+m) | |
Ehrenfeucht, Gabow, McConnell, Sullivan [EGMS94] | O(n2) | 2-structures |
Ehrenfeucht, Harju, Rozenberg [EHR94] | O(n2) | 2-structures, incrémental |
Habib, Huchard, Spinrad [HHS95] | O(n+m) | graphes d'héritage |
McConnell [McC95] | O(n2) | 2-structures, incrémental |
Bonizzoni, Della Vedova [BV95,BV99] | O(n3k-5) | hypergraphes de dimension k |
Morvan, Viennot [MV96] | parallèle | |
Capelle, Habib [CH97] | O(n+m) | connaissant une permutation factorisante |
Dahlhaus, Gustedt, McConnell [DGM97,DGM01] | O(n+m) | |
Habib, Paul, Viennot [HPV99] | O(n+m log n) | calcule une permutation factorisante |
Uno, Yagiura [UY00] | O(n) | graphes de permutation, connaissant une permutation factorisante |
McConnell, Spinrad [MS00] | O(n+m log n) | |
Habib, Paul [HP01,HP05] | O(n+m log n) | cographes |
Capelle, Habib, Montgolfier [CHdM02] | O(n+m) | graphes orientés, connaissant une permutation factorisante |
Dahlhaus, Gustedt, McConnell [DGM02] | O(n+m) | graphes orientés |
Habib, Montgolfier, Paul [HdMP04] | O(n+m) | calcule une permutation factorisante |
Shamir, Sharan [SS04] | O(n+m) | cographes, dynamique |
McConnell, Montgolfier [MdM05] | O(n+m) | graphes orientés |
Bergeron, Chauve, Montgolfier, Raffinot [BCMR05] | O(kn) | graphes de comparabilité de dimension k |
Tedder, Corneil, Habib, Paul [TCHP2008] | O(n+m) | simple en temps linéaire |
La liste des articles citées dans ce document a été compilée par
Fabien de Montgolfier.
Merci à Don Cowan de
m'avoir transmis l'article fondateur sur le sujet ainsi que des précisions
sur ses coauteurs (leur prénom).
Ce document a été généré en partie en utilisant le traducteur automatique
LaTeX2HTML Version 2002-2-1 (1.70).
Il a été mis à jour le 1er avril 2009.
Copyright © 1993, 1994, 1995, 1996,
Nikos Drakos,
Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999,
Ross Moore,
Mathematics Department, Macquarie University, Sydney.