| Auteurs | date de publication | Complexité | Commentaire |
| Cowan, James, Stanton | 1972 | O(n4) | |
| Maurer | 1977 | O(n4) | graphes orientés |
| Blass | 1978 | O(n3) | |
| Habib, Maurer | 1979 | O(n3) | |
| Habib | 1981 | O(n3) | graphes orientés |
| Cunningham | 1982 | O(n3) | graphes orientés |
| Buer, Möhring | 1983 | O(n3) | |
| McConnell | 1987 | O(n3) | |
| McConnell, Spinrad | 1989 | O(n2) | incrémental |
| Adhar, Peng | 1990 | O(log2n), O(nm) proc. | parallèle, cographes, CRCW-PRAM |
| Lin, Olariu | 1991 | O(log n), O(nm) proc. | parallèle, cographes, EREW-PRAM |
| Spinrad | 1992 | O(n+m alpha(m,n)) | |
| Cournier, Habib | 1993 | O(n+m alpha(m,n)) | |
| Ehrenfeucht, Gabow, McConnell, Spinrad | 1994 | O(n3) | 2-structures |
| Ehrenfeucht, Harju, Rozenberg | 1994 | O(n2) | 2-structures, incrémental |
| McConnell, Spinrad | 1994 | O(n+m) | |
| Cournier, Habib | 1994 | O(n+m) | |
| Bonizzoni, Della Vedova | 1995 | O(n3k-5) | décomposition en comités des hypergraphes |
| Dahlhaus | 1995 | O(log2n), O(n+m) proc. | parallèle, cographes, CRCW-PRAM |
| Dahlhaus | 1995 | O(log2n), O(n+m) proc. | parallèle, CRCW-PRAM |
| Habib, Huchard, Sprinrad | 1995 | O(n+m) | graphes d'heritage |
| McConnell | 1995 | O(n2) | 2-structures, incrémental |
| Morvan, Viennot | 1995 | parallele | |
| Capelle, Habib | 1997 | O(n+m) | si permutation factorisante fournie |
| Dahlhaus, Gustedt, McConnell | 1997 | O(n+m) | |
| Dahlhaus, Gustedt, McConnell | 1999 | O(n+m) | graphes orientés |
| Habib, Paul, Viennot | 1999 | O(n+m log n) | calcule une permutation factorisante |
| McConnell, Spinrad | 2000 | O(n+m log n) | |
| Habib, Paul | 2001 | O(n+m log n) | cographes |
| Capelle, Habib, Montgolfier | 2002 | O(n+m) | graphes orientés, si permutation factorisante fournie |
| Shamir, Sharan | 2003 | O(n+m) | cographes, fully-dynamic |
| Bretscher, Corneil, Habib, Paul | 2003 | O(d)/sommet, O(1)/arête | cographes |
| McConnell, Montgolfier | 2003 | O(n+m) | graphes orientés |
| Habib, Montgolfier, Paul | 2003 | O(n+m) | calcule une permutation factorisante |
| McConnell, Montgolfier | 2003 | O(n+m) | graphes d'intervalles et ordres de dimension k |