| 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.
