Authors, references | Complexity | Comments |
---|---|---|
James, Stanton, Cowan [JSC72] | O(n4) | first polynomial algorithm |
Maurer [Mau77] | O(n4) | digraphs |
Blass [Bla78] | O(n3) | |
Habib, Maurer [HM79] | O(n3) | |
Habib [Hab81] | O(n3) | digraphs |
Cunningham [Cun82] | O(n3) | digraphs |
Steiner [Ste82] | O(n3) | |
Spinrad [Spi82] | O(n2) | |
Buer, Möhring [BM83] | O(n3) | |
Corneil, Perl, Stewart [CPS85] | O(n+m) | cographs |
McCreary [McCreary87] | O(n3) | |
Muller, Spinrad [MS89] | O(n2) | incremental |
Adhar, Peng [AP90] | O(log2 n), O(mn) proc. | parallel, cographs, CRCW-PRAM |
Lin, Olariu [LO91] | O(log n), O(mn) proc. | parallel, cographs, 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, incremental |
Habib, Huchard, Spinrad [HHS95] | O(n+m) | inheritance graphs |
McConnell [McC95] | O(n2) | 2-structures, incremental |
Bonizzoni, Della Vedova [BV95,BV99] | O(n3k-5) | hypergraphs of dimension k |
Morvan, Viennot [MV96] | parallel | |
Capelle, Habib [CH97] | O(n+m) | knowing a factoring permutation |
Dahlhaus, Gustedt, McConnell [DGM97,DGM01] | O(n+m) | |
Habib, Paul, Viennot [HPV99] | O(n+m log n) | compute a factoring permutation |
Uno, Yagiura [UY00] | O(n) | permutation graphs, knowing a factoring permutation |
McConnell, Spinrad [MS00] | O(n+m log n) | |
Habib, Paul [HP01,HP05] | O(n+m log n) | cographs |
Capelle, Habib, Montgolfier [CHdM02] | O(n+m) | digraphs, knowing a factoring permutation |
Dahlhaus, Gustedt, McConnell [DGM02] | O(n+m) | digraphs |
Habib, Montgolfier, Paul [HdMP04] | O(n+m) | compute a factoring permutation |
Shamir, Sharan [SS04] | O(n+m) | cographs, dynamic |
McConnell, Montgolfier [MdM05] | O(n+m) | digraphs |
Bergeron, Chauve, Montgolfier, Raffinot [BCMR05] | O(kn) | comparability graphs of dimension k |
Tedder, Corneil, Habib, Paul [TCHP2008] | O(n+m) | simple linear-time |
The list of articles cited in this documents was compiled mostly by
Fabien de Montgolfier.
Thanks to Don Cowan for
sending me the historical article on the subject
as well as information on their coauthors (first names).
This document was partly generated using the
LaTeX2HTML automatic translator Version 2002-2-1 (1.70).
It was updated on April 1st, 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.