BibTeX du Cours d'algorithmique des graphes du MPRI de Michel Habib Thanks to Hans Bodlaender, Vincent Limouzy and Fabien de Montgolfier for their BibTeXs used to build this one. @String{CABIOS = {Comput. Appl. Biosci.}} @String{G = {Genomics}} @String{GR = {Genome Research}} @String{ISMB = {Intelligent Systems in Molecular Biology (ISMB)}} @String{JMB = {Journal of Molecular Biology}} @String{MBE = {Molecular Biology and Evolution}} @String{NAR = {Nucleic Acids Research}} @String{NG = {Nature Genetics}} @String{PNAS = {Proceedings of the National Academy of Sciences}} @String{PSB = {Proceedings of the Pacific Symposium on Biocomputing}} @String{RECOMB = {International Conference on Computational Molecular Biology (RECOMB)}} @String{UM = {Unpublished manuscript}} @String{ADM = {Annals of Discrete Mathematics}} @String{C = {Combinatorica}} @String{CN = {Congress Numerantium}} @String{DCG = {Discrete and Computational Geometry}} @String{DM = {Discrete Mathematics}} @String{DAM = {Discrete Applied Mathematics}} @String{IPL = {Information Processing Letters}} @String{JADM = {SIAM Journal on Algebraic and Discrete Methods}} @String{JDM = {SIAM Journal on Discrete Mathematics}} @String{JAM = {SIAM Journal on Applied Mathematics}} @String{JMAA = {SIAM Journal on Matrix Analysis and Applications}} @String{JOC = {SIAM Journal on Computing}} @String{JCTB = {Journal of Combinatorial Theory Series B}} @String{JGT = {Journal of Graph Theory}} @String{TCS = {Theoretical Computer Science}} @String{JACM = {Journal of the ACM (JACM)}} @String{LNCS = {Lecture Notes in Computer Science}} @String{JOA = {Journal of Algorithms}} @String{DMTCS = {Discrete Mathematics and Theoretical Computer Science}} @string{ICOMP = {Information and Computation}} @article{AdharPeng1990, title = {Parallel algorithms for cographs and parity graphs with applications}, author = {Gur Saran Adhar and Shietung Peng}, journal = JOA, volume = 11, publisher = {Springer-Verlag}, pages = {252-284}, year = 1990 } @article{ACP1987, author = {Stefan Arnborg and Derek G. Corneil and Andrzej Proskurowski}, title = {Complexity of Finding Embeddings in a $k$-Tree}, journal = JADM, pages = {277-284}, year = 1987, volume = 8, number = 2, note = {\url{http://dx.doi.org/10.1137/0608024}}, comment = {alt url \url{http://link.aip.org/link/?SML/8/277/1}} } @article{Berge1994, author = {Claude Berge}, title = {Qui a tu{\'e} le duc de {Densmore} ?}, journal = {Biblioth{\`e}que {Oulipienne}}, volume = 67, year = 1994, note = {r{\'e}{\'e}dition Castor Astral, 2000} } @inproceedings{BCHP2003, author = {Anna Bretscher and Derek G. Corneil and Michel Habib and Christophe Paul}, title = {A Simple Linear Time {LexBFS} Cograph Recognition Algorithm}, booktitle = {Proceedings of the 29th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'03)}, series = LNCS, volume = 2880, year = 2003, pages = {119-130}, note = {\url{http://books.google.fr/books?hl=fr&lr=&id=PuHeuUucopEC&oi=fnd&pg=PA119&ots=Y8HsPhrY4M&sig=HjiXf0LLDMbqElF6ByE60JVryiw}, \url{http://dx.doi.org/10.1007/b93953}}, } @article{BCHP2008, author = {Anna Bretscher and Derek G. Corneil and Michel Habib and Christophe Paul}, title = {A Simple Linear Time {LexBFS} Cograph Recognition Algorithm}, journal = JDM, year = 2008, note = {To appear, \url{http://www.liafa.jussieu.fr/\~habib/Documents/cograph.ps}}, comment = {alturl}, } @InProceedings{BCMR2005, author = {Anne Bergeron and C{\'e}dric Chauve and Fabien de Montgolfier and Mathieu Raffinot}, title = {Computing common intervals of K permutations, with applications to modular decomposition of graphs}, booktitle = {Proceedings of the thirteenth Annual European Symposium on Algorithms (ESA'05)}, year = {2005}, note = {\url{http://www-igm.univ-mlv.fr/\~raffinot/ftp/common-interval-12-April-05.pdf.gz}} } @Article{Blass1978, author = {Andreas Blass}, title = {Graphs with unique maximal clumpings}, journal = JGT, year = 1978, volume = 2, number = 1, pages = {19-24} } @InProceedings{Bodlaender2005, author = {Hans L. Bodlaender}, title = {Discovering treewidth}, year = 2005, pages = {1-16}, booktitle = {Proceedings of the 31st Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'05)}, series = LNCS, volume = 3381, note = {\url{http://citeseer.ist.psu.edu/bodlaender05discovering.html}}, comment = {alternative url: \url{http://www.cs.uu.nl/research/techreps/repo/CS-2005/2005-018.pdf}}, bibupdate = {31/10/2006}, publisher = {Springer-Verlag}, } @Article{BTTL1997, author = {Hans L. Bodlaender and Richard Tan and Dimitrios M. Thilikos and Jan van Leeuwen}, title = {On Interval Routing Schemes and Treewidth}, journal = {Information and Computation}, year = 1997, volume = 139, pages = {92-109}, note = {\url{http://citeseer.ist.psu.edu/188284.html}}, bibupdate = 20070628 } @InProceedings{BonizzoniDellavedova1995, title = {Modular Decomposition of Hypergraphs}, author = {Paola Bonizzoni and Gianluca Della Vedova}, booktitle = {Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'95)}, publisher = {Springer-Verlag}, year = 1995, series = LNCS, volume = 1017, pages = {303-317}, note = {\url{http://dx.doi.org/10.1007/3-540-60618-1\_84}} } @article{BonizzoniDellavedova1999, title = {An Algorithm to Compute the Modular Decomposition of Hypergraphs}, author = {Paola Bonizzoni and Gianluca Della Vedova}, journal = JOA, year = 1999, volume = 32, number = 2, pages = {65-86}, note = {\url{http://citeseer.ist.psu.edu/506177.html}}, comment = {alturl \url{http://www.statistica.unimib.it/\~dellavedova/papers/ModularDecompositionHypergraphs.pdf}} } @inproceedings{BoothLueker1975, author = {Kellogg S. Booth and George S. Lueker}, title = {Linear algorithms to recognize interval graphs and test for the consecutive ones property}, booktitle = {Proceedings of the seventh Annual {ACM} Symposium on Theory of Computing (STOC'75)}, year = 1975, pages = {255-265}, note = {\url{http://dx.doi.org/10.1145/800116.803776}}, bibupdate = 20070529, } @article{BoothLueker1976, author = {Kellogg S. Booth and George S. Lueker}, title = {Testing for the consecutive ones property, interval graphs, and graph planarity using {PQ}-tree algorithms}, journal = {Journal of Computer and System Science}, volume = 13, year = 1976, pages = {335-379}, bibupdate = 20070529, } @Article{Brightwell1993, author = {Graham Brightwell}, title = {On the complexity of diagram testing}, journal = {Order}, volume = 10, number = 4, pages = {297-303}, note = {\url{http://dx.doi.org/10.1007/BF01108825}}, year = 1993, bibupdate = 20061122 } @misc{BrightwellTrotter2006, author = {Graham Brightwell and William T. Trotter}, title = {Great Book of Posets}, note = {book in preparation, \url{http://www.math.gatech.edu/\~trotter/math-8823-Fa06/8823-Fa06-TopPage.htm}}, year = 2006, bibupdate = 20061127 } @InProceedings{BrightwellWinkler1991, title = {Counting Linear Extensions is {{\#P}}-Complete}, author = {Graham Brightwell and Peter Winkler}, pages = {175-181}, booktitle = {Proceedings of the 23rd Annual {ACM} Symposium on Theory of Computing (STOC'91)}, year = {1991}, note = {\url{http://www.math.dartmouth.edu/\~pw/papers/sharpstoc.ps}} } @Article{BuerMohring1983, author = {Hermann Buer and Rolf H. M{\"o}hring}, title = {A fast algorithm for the decomposition of graphs and posets}, journal = {Mathematics of Operations Research}, year = 1983, volume = 8, pages = {170-184}, bibupdate = {31/10/2006} } @InProceedings{CapelleHabib1997, author = {Christian Capelle and Michel Habib}, title = {Graph Decompositions and Factorizing Permutations}, booktitle = {Proceedings of the fifth Israeli Symposium on the Theory of Computing and Systems (ISTCS'97)}, year = 1997, note = {\url{http://citeseer.ist.psu.edu/43689.html}}, comment = {alturl \url{http://dx.doi.org/10.1109/ISTCS.1997.595165}} } @Article{CHM2002, author = {Christian Capelle and Michel Habib and Fabien de Montgolfier}, title = {Graph Decomposition and Factorizing Permutations}, journal = DMTCS, volume = 5, number = 1, note = {\url{http://www.liafa.jussieu.fr/~fm/publications/dmtcs.ps}}, year = 2002, bibupdate = {28/10/2006} } @Article{CardonCrochemore1982, author = {Alain Cardon and Maxime Crochemore}, title = {Partitioning a graph in $O(|A|log_2|V|)$}, year = 1982, journal = TCS, volume = 19, number = 1, pages = {85-98}, bibupdate = 20070816, note = {\url{http://dx.doi.org/10.1016/0304-3975(82)90016-0}} } @article{CEFK1998, author = {M{\'a}rcia R. Cerioli and Hazel Everett and Celina M.H. de Figueiredo and Sulamita Klein}, title = {The Homogeneous Set Sandwich Problem}, journal = IPL, volume = 67, number = 1, year = 1998, pages = {31-35}, note = {\url{http://citeseer.ist.psu.edu/190684.html}}, comment = { alternative URL \url{http://www.ime.usp.br/\~cris/gcomb/pronex/ps-dvi-files/celina/ipl.ps.gz} }, bibupdate = {11/10/2006} } @InProceedings{Chan2006, author = {Timothy M. Chan}, title = {All-pairs shortest paths for unweighted undirected graphs in $o(mn)$ time}, booktitle = {Proceedings of the seventeenth annual ACM-SIAM Symposium on Discrete Algorithm (SODA'06)}, year = 2006, note = {\url{http://www.cs.uwaterloo.ca/\~tmchan/omn_soda.ps}}, comment = {alturl \url{http://dx.doi.org/10.1145/1109557.1109614}}, bibupdate = 20070220, } @article{CHM1981, author = {Michel Chein and Michel Habib and Marie-Catherine Maurer}, title = {Partitive hypergraphs}, journal = DM, volume = 37, year = 1981, pages = {35-50}, bibupdate = {11/10/2006} } @Article{CDHP2001, author = {Derek G. Corneil and Feodor F. Dragan and Michel Habib and Christophe Paul}, title = {Diameter determination on restricted graph families}, journal = DAM, volume = 113, number = {2-3}, pages = {143-166}, year = 2001, note = {\url{http://www.lirmm.fr/\~paul/Biblio/Postscript/Diam-new.ps}}, comment = { Use of BFS, not even LexBFS, to determine the diameter on some graph classes. }, bibupdate = {26/10/2006} } @Article{CDK2003, author = {Derek G. Corneil and Feodor F. Dragan and Ekkehard K{\"o}hler}, title = {On the power of {BFS} to determine a graph's diameter}, journal = {Networks}, volume = 42, number = 4, pages = {209-222}, year = 2003, note = {\url{http://www.cs.kent.edu/\~dragan/LBFS-Power.pdf}}, comment = { Use of BFS, not even LexBFS, to determine the diameter on some graph classes. }, bibupdate = 20061026 } @article{CorneilGotlieb1970, author = {Derek G. Corneil and Calvin C. Gotlieb}, title = {An Efficient Algorithm for Graph Isomorphism}, journal = JACM, volume = 17, number = 1, year = 1970, pages = {51-64}, bibupdate = {20070816}, note = {\url{http://dx.doi.org/10.1145/321556.321562}}, } @inproceedings{Corneil2004, author = {Derek G. Corneil}, title = {Lexicographic Breadth First Search - A Survey}, booktitle = {Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'04)}, series = LNCS, volume = 3353, year = 2004, pages = {1-19}, note = {\url{http://books.google.fr/books?hl=fr&lr=&id=ZPDqRTRxITsC&oi=fnd&pg=PA1&ots=OMtnEIG_1y&sig=wuvqtuM50-5bKfYATkZNxHr49gU}, \url{http://dx.doi.org/10.1007/b104584}}, } @inproceedings{COS1998, author = {Derek G. Corneil and Stephan Olariu and Lorna K. Stewart}, title = {The ultimate interval graph recognition algorithm?}, booktitle = {Proceedings of the ninth annual ACM-SIAM Symposium on Discrete algorithms (SODA'98)}, pages = {175-180}, year = 1998, note = {\url{http://citeseer.ist.psu.edu/314904.html}}, bibupdate = 20070529 } @article{CPS1985, author = {Derek G. Corneil and Yehoshua Perl and Lorna K. Stewart}, title = {A Linear Recognition Algorithm for Cographs}, journal = JOC, volume = 14, number = 4, pages = {926-934}, year = 1985, note = {\url{http://dx.doi.org/10.1137/0214065}}, bibupdate = {11/10/2006} } @inproceedings{CMR1998, author = {Bruno Courcelle and Johann A. Makowsky and Udi Rotics}, title = {Linear time solvable optimization problems on graphs of bounded clique width}, booktitle = {Proceedings of the 24th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'98)}, series = LNCS, volume = 1517, year = 1998, pages = {1-16}, note = {\url{http://citeseer.ist.psu.edu/courcelle99linear.html}}, comment = {alturl \url{http://www.cs.technion.ac.il/\~admlogic/TR/1999/tocs-99.ps} } } @inproceedings{CournierHabib1993, author = {Alain Cournier and Michel Habib}, title = {An Efficient Algorithm to Recognize Prime Undirected Graphs}, booktitle = {Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'92)}, series = LNCS, volume = 657, year = 1993, pages = {212-224}, publisher = {Springer-Verlag}, note = {\url{http://dx.doi.org/10.1007/3-540-56402-0_49}}, } @inproceedings{CournierHabib1994, author = {Alain Cournier and Michel Habib}, title = {A New Linear Algorithm for Modular Decomposition}, booktitle = {Proceedings of the 19th International Colloquium on Trees in Algebra and Programming (CAAP'94)}, series = LNCS, volume = 787, year = 1994, pages = {68-84}, publisher = {Springer-Verlag}, note = {\url{http://dx.doi.org/10.1007/BFb0017474}} } @article{CournierIlle1998, author = {Alain Cournier and Pierre Ille}, title = {Minimal indecomposable graphs}, journal = DM, volume = 183, number = {1-3}, pages = {61-80}, year = 1998, note = {\url{http://dx.doi.org/10.1016/S0012-365X(97)00077-0}}, bibupdate = {11/10/2006} } @Article{Cunningham1982, author = {William H. Cunningham}, title = {Decomposition of directed graphs}, journal = JADM, volume = 3, number = 2, pages = {214-228}, year = 1982, note = {\url{http://dx.doi.org/10.1137/0603021}}, comment = {alt url \url{http://link.aip.org/link/?SML/3/214/1}}, } @InProceedings{DGM1997, author = {Elias Dahlhaus and Jens Gustedt and Ross M. McConnell}, title = {Efficient and Practical Modular Decomposition}, booktitle = {Proceedings of the eigth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97)}, year = 1997, pages = {26-35}, note = {\url{http://www.cs.colostate.edu/\~rmm/DGM97.pdf}}, bibupdate = {27/10/2006}, comment = { O(n + ma(m,n)) practical algorithm for modular decomposition with some data structure tricks, O(n+m), proof easier than previous ones } } @InProceedings{DKV2002, title = {Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics}, author = {V{\'i}ctor Dalmau and Phokion G. Kolaitis and Moshe Y. Vardi}, booktitle = {Proceedings of the Eight International Conference on Principles and Practice of Constraint Programming (CP'02)}, series = LNCS, volume = 2470, year = 2002, pages = {310-326}, publisher = {Springer-Verlag}, note = {\url{http://citeseer.ist.psu.edu/525259.html}}, bibupdate = {06/11/2006}, comment = {alturl : \url{http://www.cs.rice.edu/\~vardi/papers/cp02.ps.gz}} } @Article{DGM2001, author = {Elias Dahlhaus and Jens Gustedt and Ross M. McConnell}, title = {Efficient and Practical Algorithms for Sequential Modular Decomposition}, journal = JOA, year = 2001, volume = 41, number = 2, pages = {360-387}, note = {\url{http://www.cs.colostate.edu/\~rmm/linearDecompJournal.ps}}, bibupdate = {11/10/2006}, comment = {Journal version of DGM1997} } @Article{DGM2002, author = {Elias Dahlhaus and Jens Gustedt and Ross M. McConnell}, title = {Partially Complemented Representations of Digraphs}, journal = DMTCS, year = 2002, volume = 5, number = 1, pages = {147-168}, note = {\url{http://www.emis.ams.org/journals/DMTCS/volumes/abstracts/pdfpapers/dm050110.pdf}}, bibupdate = {11/10/2006}, comment = { alternative link: http://dmtcs.loria.fr/volumes/abstracts/pdfpapers/dm050110.pdf http://www.cs.colostate.edu/\~rmm/cstacks.pdf } } @book{Dijkstra1976, author = {Edsger W. Dijkstra}, title = {A Discipline of Programming}, publisher = {Prentice-Hall}, year = {1976}, bibupdate = {11/10/2006} } @TechReport{Dirac1961, author = {Gabriel A. Dirac}, title = {On rigid circuit graphs}, type = {Abhandlungen aus dem Mathematischen Seminar der Universit{\"a}t Hamburg}, institution = {Universit{\"a}t Hamburg}, number = {25}, page = {71-76}, year = {1961} } @article{Dragan2005, author = {Feodor F. Dragan}, title = {Estimating all pairs shortest paths in restricted graph families: a unified approach}, journal = JOA, volume = 57, year = 2005, pages = {1-21}, note = {\url{http://www.cs.kent.edu/\~dragan/APASP-SpGr.pdf}} } @article{DushnikMiller1941, author = {Ben Dushnik and Edwin W. Miller}, title = {Partially ordered sets}, journal = {American Journal of Mathematics}, volume = 63, year = 1941, pages = {600-610}, note = {\url{http://www.jstor.org/view/00029327/di994279/99p0366k/0}} } @Article{EGMS1994, author = {Andrzej Ehrenfeucht and Harold N. Gabow and Ross M. McConnell and Stephen J. Sullivan}, title = {An {$O(n^2)$} Divide-and-Conquer Algorithm for the Prime Tree Decomposition of Two-Structures and Modular Decomposition of Graphs}, journal = JOA, volume = 16, number = 2, pages = {283-294}, year = 1994 } @Article{EHR1994, author = {Andrzej Ehrenfeucht and Tero Harju and Grzegorz Rozenberg}, title = {Incremental construction of 2-structures}, journal = DM, volume = 128, number = 1, pages = {113-141}, year = 1994 } @Article{ErdosRenyi1959, author = {Paul Erd{\"o}s and Alfr{\'e}d R{\'e}nyi}, title = {On Random Graphs {I}}, journal = {Publicationes Mathematicae}, volume = 6, pages = {290-297}, year = 1959, bibupdate = {11/10/2006}, comment = { WDH: Proves that to be connected a random graph needs an average degree of about (1/2 ln N) and that it is a sharp bound. } } @book{Fishburn1985, author = {Peter C. Fishburn}, title = {Interval Orders and Interval Graphs}, publisher = {John Wiley \& Sons}, serie = {Wiley-Interscience Series in Discrete Mathematics}, year = 1985, comment = { 1 Introduction defines partial orders, weak orders, posets, considers graph as posets irreflexive binary relation : not xRx negatively transitive : xRy = > for all z, xRz or zRy partial order : R irreflexive transitive weak order : R asymmetric negatively transitive linear order : R weak complete 2 Interval orders : < such that (a (a (a define an order <_0 on the endpoints (X,-) = x^- and (X,+) = x^+ <_0 is a weak order if < is an interval order } } @inproceedings{Freuder1990, author = {Eugene C. Freuder}, title = {Complexity of $k$-Tree Structured Constraint Satisfaction Problems}, booktitle = {Proceedings of the Eighth National Conference on Artificial Intelligence (AAAI'90)}, pages = {4-9}, year = 1990, } @Article{FrickGrohe2004, title = {The complexity of first-order and monadic second-order logic revisited}, author = {Markus Frick and Martin Grohe}, journal = {Annals of Pure and Applied Logic}, year = 2004, volume = 130, number = {1-3}, pages = {3-31}, note = {\url{http://www2.informatik.hu-berlin.de/\~grohe/pub/mc.ps}} } @article{FulkersonGross1965, author = {Delbert R. Fulkerson and O. A. Gross}, title = {Incidence matrices, interval graphs, and seriation in archaeology}, journal = {Pacific Journal of Mathematics}, volume = 28, year = 1969, pages = {565-570}, note = {\url{http://projecteuclid.org/Dienst/UI/1.0/Summarize/euclid.pjm/1102995572}}, bibupdate = {16/10/2006}, comment ={ Tries to solve the "approximate" consecutive ones problems. Consecutive 1 property = Petrie matrix | Robinson matrix = going left or down from the diagonal, never increase. sigma0 row permutation applied on M gives a Petrie => sigma0 applied to row and columns of M tM gives a Robinson. + proof Idea of using MultiDimensional Scaling to solve approximate consecutive ones problem. Often cited for proving that a graph is chordal iff it has a perfect elimination ordering. } } @article{Gallai1967, author = {Tibor Gallai}, title = {{Transitiv orientierbare Graphen}}, journal = {Acta Mathematica Academiae Scientiarum Hungaricae}, volume = 18, number = {1-2}, pages = {25-66}, year = 1967, bibupdate = {20070606}, note = {\url{http://dx.doi.org/10.1007/BF02020961}}, } @book{GareyJohnson1979, author = {Michael R. Garey and David S. Johnson}, title = {Computers and Intractability, A Guide to the Theory of {NP}-Completeness}, publisher = {W.H. Freeman and Company}, year = 1979, address = {New York} } @article{GJS1976, author = {Michael R. Garey and David S. Johnson and Larry J. Stockmeyer}, title = {Some Simplified {NP}-Complete Graph Problems}, journal = TCS, volume = 1, number = 3, pages = {237-267}, year = 1976, bibupdate = 20061122, url = {\url{http://dx.doi.org/10.1145/800119.803884}} } @article{Gavril1974, author = {F{\u{a}}nic{\u{a}} Gavril}, title = {The intersection graphs of subtrees in trees are exactly the chordal graphs}, journal = JCTB, year = 1974, volume = 16, pages = {47-56}, note = {\url{http://dx.doi.org/10.1016/0095-8956(74)90094-X}}, } @article{GilmoreHoffman1964, author = {Paul C. Gilmore and Alan J. Hoffman}, title = {A characterization of comparability graphs and of interval graphs}, journal = {Canadian Journal of Mathematics}, year = 1964, volume = 16, pages = {539-548}, } @book{Golumbic1980, author = {Martin C. Golumbic}, title = {Algorithmic Graph Theory and Perfect Graphs}, publisher = {Academic Press}, year = 1980, } @article{GKS1994, author = {Martin C. Golumbic and Haim Kaplan and Ron Shamir}, title = {Graph Sandwich Problems}, journal = JOA, volume = 19, number = 3, pages = {449-473}, year = 1995, note = {\url{http://citeseer.ist.psu.edu/golumbic94graph.html}}, comment = { alternative URL : \url{http://www.math.tau.ac.il/\~haimk/papers/sandJ.ps} }, bibupdate = 20070814, } @InProceedings{GLS2001, author = {Georg Gottlob and Nicola Leone and Francesco Scarcello}, title = {Hypertree decompositions: a survey}, booktitle = {Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS'01)}, year = 2001, series = LNCS, volume = 2136, publisher = {Springer-Verlag}, pages = {37-57}, note = {\url{http://www.springerlink.com/index/Y8R9EL5KQ21MU73M.pdf}} } @phdthesis{Habib1981, author = {Michel Habib}, title = {Substitution des structures combinatoires, th{\'e}orie et algorithmes}, school = {Universit{\'e} Pierre et Marie Curie}, year = {1981}, note = {\url{http://catalogue.bnf.fr/ark:/12148/cb34772090v/PUBLIC}}, } @Article{HHS1995, author = {Michel Habib and Marianne Huchard and Jeremy P. Spinrad}, title = {A linear algorithm to decompose inheritance graphs into modules}, journal = {Algorithmica}, year = 1995, volume = 13, pages = {573-591}, note = {\url{http://www.springerlink.com/index/V3384M611187NL12.pdf}}, bibupdate = {30/11/2006} } @Article{HLP2003, author = {Michel Habib and Emmanuelle Lebhar and Christophe Paul}, title = {A note on finding all homogeneous set sandwiches}, journal = IPL, year = 2003, volume = 87, number = 3, pages = {147-151}, note = {\url{http://hal-lirmm.ccsd.cnrs.fr/lirmm-00090365}}, comment = {alturl \url{http://dx.doi.org/10.1016/S0020-0190(03)00265-5}}, bibupdate = 20070814, } @Article{HabibMaurer1979, author = {Michel Habib and Marie-Catherine Maurer}, title = {On the {X}-{J}oin decomposition for undirected graphs}, journal = DAM, year = 1979, volume = 3, pages = {201-207} } @InProceedings{HMP2004, author = {Michel Habib and Fabien de Montgolfier and Christophe Paul}, title = {A simple linear-time modular decomposition algorithm for graphs, using order extension}, booktitle = {Ninth Scandinavian Workshop on Algorithm Theory (SWAT'04)}, year = 2004, bibupdate = {28/10/2006}, note = {\url{http://www.liafa.jussieu.fr/\~fm/publications/swat04.pdf }} } @Article{HMPV2000, author = {Michel Habib and Christophe Paul and Ross M. McConnell and Laurent Viennot}, title = {Lex-{BFS} and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing}, year = 2000, journal = TCS, volume = 234, pages = {59-84}, bibupdate = {29/05/2007}, note = {\url{http://citeseer.ist.psu.edu/179874.html}} } @Article{HabibPaul2005, author = {Michel Habib and Christophe Paul}, title = {A simple linear time algorithm for cograph recognition}, year = 2005, journal = DAM, volume = 145, number = 2, pages = {183-197}, bibupdate = {28/10/2006}, note = {\url{http://dx.doi.org/10.1016/j.dam.2004.01.011}} } @unpublished{HabibPaul2001, author = {Michel Habib and Christophe Paul}, title = {A simple linear time algorithm for cograph recognition}, year = 2001, bibupdate = {28/10/2006}, note = {\url{http://citeseer.ist.psu.edu/habib01simple.html}}, comment = {alternative url \url{http://www.ecp6.jussieu.fr/seminaire/papiers/0102/020117.ps} } } @Article{HPV1999, author = {Michel Habib and Christophe Paul and Laurent Viennot}, title = {Partition refinement techniques: an interesting algorithmic toolkit}, year = 1999, journal = {International Journal of Foundations of Computer Science}, volume = 10, number = 2, pages = {147-170}, note = {\url{http://gyroweb.inria.fr/\~viennot/postscripts/ijfcs00.ps.gz}} } @Article{Hoare1961, author = {Charles A. R. Hoare}, title = {Algorithm 63: Partition, Algorithm 64: Quicksort, Algorithm 65: Find}, year = 1961, journal = {Communications of the ACM}, volume = 4, number = 7, pages = {321-322}, note = {\url{http://dx.doi.org/10.1145/366622.366642}} } @InProceedings{Hopcroft1971, author = {John E. Hopcroft}, title = {An $n \log n$ algorithm for minimizing states in a finite automaton}, booktitle = {Theory of machines and computations, Proceedings of an International Symposium on the Theory of Machines and Computations}, publisher = {Academic Press}, editor = {Z. Kohavi and A. Paz}, year = {1971}, pages = {189-196}, } @InProceedings{Hsu1993, author = {Wen-Lian Hsu}, title = {A simple test for interval graphs}, booktitle = {Proceedings of the 18th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'92)}, volume = 657, series = LNCS, pages = {11-16}, year = {1993}, publisher = {Springer-Verlag}, bibupdate = 20070606, note = {\url{http://dx.doi.org/10.1007/3-540-56402-0_31}}, } @InProceedings{HsuMa1991, author = {Wen-Lian Hsu and Tze-Heng Ma}, title = {Substitution decomposition on chordal graphs and applications}, booktitle = {Proceedings of the second International Symposium on Algorithms (ISA'91)}, volume = 557, series = LNCS, pages = {52-60}, year = {1991}, publisher = {Springer-Verlag}, bibupdate = 20070606, note = {\url{http://dx.doi.org/10.1007/3-540-54945-5_49}}, } @article{HsuMa1999, author = {Wen-Lian Hsu and Tze-Heng Ma}, title = {Fast and Simple Algorithms for Recognizing Chordal Comparability Graphs and Interval Graphs}, journal = JOC, volume = 28, number = 3, pages = {1004-1020}, year = {1999}, note = {\url{http://dx.doi.org/10.1137/S0097539792224814}}, } @Article{Ille1997, author = {Pierre Ille}, title = {Indecomposable graphs}, journal = DM, volume = 173, year = 1997, pages = {71-78}, note = {\url{http://dx.doi.org/10.1016/S0012-365X(96)00097-0}}, bibupdate = {16/10/2006} } @inproceedings{JSC1972, author = {Lee O. James and Ralph G. Stanton and Donald D. Cowan}, title = {Graph decomposition for undirected graphs}, booktitle = {Proceedings of the third Southeastern International Conference on Combinatorics, Graph Theory, and Computing (CGTC'72)}, editor = {F. Hoffman}, publisher = {R. B. Levow eds.}, pages = {281-290}, year = 1972, bibupdate = {16/10/2006}, comment = { First polynomial modular decomposition algorithm Donald, Ralf? } } @article{Jordan1869, author = {Camille Jordan}, title = {Sur les assemblages de lignes}, journal = {Journal für die reine und angewandte Mathematik}, pages = {185-190}, year = 1869, bibupdate = 20061204, note = {\url{http://www.digizeitschriften.de/index.php?id=loader&tx\_jkDigiTools\_pi1[IDDOC]=510097}}, comment = {center of a tree}, } @inproceedings{KashiwabaraFujisawa1979, author = {T. Kashiwabara and T. Fujisawa}, title = {An {NP}-complete problem on interval graphs}, booktitle = {Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS'79)}, year = 1979, pages = {82-83}, comment = { "Toshinobu Kashiwabara" "Toshio Fujisawa" ? } } @inproceedings{KashiwabaraFujisawa1979b, author = {T. Kashiwabara and T. Fujisawa}, title = {{NP}-completeness of the problem of finding a minimum-clique number interval graph containing a given graph as a subgraph}, booktitle = {Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS'79)}, year = 1979, pages = {82-83}, comment = { "Toshinobu Kashiwabara" "Toshio Fujisawa" ? } } @book{KleinbergTardos2006, author = {Jon Kleinberg and {\'E}va Tardos}, title = {Algorithm design}, year = 2006, publisher = {Addison-Wesley} } @phdthesis{Kloks1995, author = {Ton Kloks}, title = {Treewidth}, school = {Utrecht University, Utrecht, The Netherlands}, year = 1993, } @InProceedings{KorteMohring1986, author = {Norbert Korte and Rolf H. M{\"o}hring}, title = {A Simple Linear-Time Algorithm to Recognize Interval Graphs}, booktitle = {Proceedings of the twelfth International Workshop on Graph-Theoretic Concepts in Computer Science (WG'86)}, year = {1986}, series = LNCS, volume = 246, pages = {1-16}, note = {\url{dx.doi.org/10.1007/3-540-17218-1_45}} } @article{KorteMohring1989, author = {Norbert Korte and Rolf H. M{\"o}hring}, title = {An Incremental Linear-Time Algorithm for Recognizing Interval Graphs}, journal = JOC, volume = {18}, number = {1}, year = {1989}, pages = {68-81}, bibupdate = 20070529, note = {\url{http://dx.doi.org/10.1137/0218005}} } @InProceedings{KratschSpinrad2005, author = {Dieter Kratsch and Jeremy P. Spinrad}, title = {Between $O(mn)$ and $O(n^\alpha)$}, booktitle = {Proceedings of the fourteenth annual ACM-SIAM Symposium on Discrete Algorithm (SODA'03)}, year = 2003, note = {\url{http://www.cs.uwaterloo.ca/\~tmchan/omn_soda.ps}}, comment = {alturl \url{http://dx.doi.org/10.1145/1109557.1109614}}, bibupdate = 20070220, } @article{LekkerkerkerBoland1962, author = {Cornelis G. Lekkerkerker and J. Ch. Boland}, title = {Representation of a finite graph by a set of intervals on the real line}, journal = {Fundamenta Mathematicae}, volume = 51, year = 1962, pages = {45-64}, note = {\url{http://matwbn.icm.edu.pl/ksiazki/fm/fm51/fm5115.pdf}}, bibupdate = 20070625, } @article{LinOlariu1991, author = {Rong Lin and Stephan Olariu}, title = {An {NC} recognition algorithm for cographs}, journal = {Journal of Parallel and Distributed Computing}, volume = 13, number = 1, year = 1991, pages = {76-90} } @article{Lovasz2005, author = {L{\'a}szl{\'o} Lov{\'a}sz}, title = {Graph minor theory }, journal = {Bulletin of the American Mathematical Society}, volume = 43, year = 2005, pages = {75-86}, note = {\url{http://www.ams.org/bull/2006-43-01/S0273-0979-05-01088-8/}}, } @InCollection{MaffrayPreissmann2001, author = {Frederic Maffray and Myriam Preissmann}, editor = {J.L. Ramirez-Alfonsin and B.A. Reed}, title = {{A translation of Tibor Gallai's paper: Transitiv orientierbare Graphen}}, booktitle = {Perfect graphs}, publisher = {J. Wiley}, year = 2001, pages = {25-66}, bibupdate = {20070606}, } @article{McconnellMontgolfier2005, author = {Ross M. McConnell and Fabien de Montgolfier}, title = {Linear-time modular decomposition of directed graphs}, journal = DAM, volume = 2, number = 145, pages = {189-209}, note = {\url{http://www.cs.colostate.edu/\~rmm/digraphDecomp.pdf}}, year = 2005 } @InProceedings{McconnellMontgolfier2005b, author = {Ross M. McConnell and Fabien de Montgolfier}, title = {Algebraic Operations on {PQ}-trees and Modular Decomposition Trees}, booktitle = {Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'05)}, year = {2005}, note = {\url{http://www.cs.colostate.edu/\~rmm/MdeFWG05.pdf}} } @Article{Mcconnell1995, author = {Ross M. McConnell}, title = {An {$O(n^2)$} incremental algorithm for modular decomposition of graphs and 2-structures}, journal = {Algorithmica}, year = 1995, volume = 14, pages = {209-227}, note = {\url{http://www.cs.colostate.edu/\~rmm/incralg.pdf}} } @InProceedings{McconnellSpinrad1994, author = {Ross M. McConnell and Jeremy P. Spinrad}, title = {Linear-time modular decomposition and efficient transitive orientation of comparability graphs}, pages = {536-545}, booktitle = {Proceedings of the fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94)}, year = 1994, note = {\url{http://www.cs.colostate.edu/\~rmm/linModDecomp.pdf}} } @InProceedings{McconnellSpinrad1997, author = {Ross M. McConnell and Jeremy P. Spinrad}, title = {Linear-time transitive orientation}, booktitle = {Proceedings of the eigth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'97)}, year = 1997, note = {\url{http://www.cs.colostate.edu/\~rmm/linTOSODA.pdf}} } @Article{McconnellSpinrad1999, author = {Ross M. McConnell and Jeremy P. Spinrad}, title = {Modular decomposition and transitive orientation}, journal = DM, volume = 201, year = 1999, pages = {189-241}, note = {\url{http://www.cs.colostate.edu/\~rmm/linto.pdf}} } @Article{McconnellSpinrad2000, author = {Ross M. McConnell and Jeremy P. Spinrad}, title = {Ordered vertex partitioning}, pages = {45-60}, volume = 4, journal = DMTCS, year = 2000, note = {\url{http://www.cs.colostate.edu/\~rmm/dm040104.pdf}} } @phdthesis{Mccreary1987, author = {Carolyn McCreary}, title = {An algorithm for parsing a graph grammar}, school = {University of Colorado}, year = {1987} } @article{Mcmaster1978, author = {Colin L. McMaster}, title = {An Analysis of Algorithms for the Dutch National Flag Problem}, journal = {Communications of the ACM}, number = {10}, volume = {21}, pages = {842-846}, year = {1978}, note = {\url{http://doi.acm.org/10.1145/359619.359629}}, bibupdate = {11/10/2006}, comment = { cites Dijkstra76 as the origin of the dutch flag problem. } } @PhdThesis{Maurer1977, author = {Marie-Catherine Maurer}, title = {Joints et d{\'e}compositions premi{\`e}res dans les graphes}, school = {Universit{\'e} Pierre et Marie Curie (Paris VI)}, year = {1977} } @article{MoehringRadermacher1984, author = {Rolf H. M{\"o}hring and Franz J. Radermacher}, title = {Substitution decomposition for discrete structures and connections with combinatorial optimization}, journal = ADM, volume = 19, year = 1984, pages = {257-356}, bibupdate = {11/10/2006} } @InProceedings{MorvanViennot1996, title = {Parallel Comparability Graph Recognition and Modular Decomposition}, author = {Michel Morvan and Laurent Viennot}, booktitle = {Proceedings of the thirteenth Annual Symposium on Theoretical Aspects of Computer Science (STACS'96)}, year = 1996, series = LNCS, volume = 1046, publisher = {Springer-Verlag}, pages = {169-180}, note = {\url{http://www.liafa.jussieu.fr/web9/rapportrech/rapportsWeb/1995/stacs96.pdf}}, comment = {alturl \url{http://gyroweb.inria.fr/\~viennot/postscripts/stacs96.ps.gz}} } @article{MullerSpinrad1989, author = {John H. Muller and Jeremy Spinrad}, title = {Incremental modular decomposition}, journal = JACM, volume = 36, number = 1, year = 1989, pages = {1-19}, bibupdate = {20070606}, note = {\url{http://dx.doi.org/10.1145/58562.59300}}, } @article{NesetrilRodl1987, author = {Jaroslav Ne{\v s}et{\v r}il and Vojt{\v e}ch R{\"o}dl}, title = {Complexity of Diagrams}, journal = {Order}, volume = 3, year = 1987, pages = {321-330}, } @article{NesetrilRodl1993, author = {Jaroslav Ne{\v s}et{\v r}il and Vojt{\v e}ch R{\"o}dl}, title = {Complexity of Diagrams, errata}, journal = {Order}, volume = 10, year = 1993, pages = {393}, } @article{NesetrilRodl1995, author = {Jaroslav Ne{\v s}et{\v r}il and Vojt{\v e}ch R{\"o}dl}, title = {More on the complexity of cover graphs}, journal = {Commentationes mathematicae Universitatis Carolinae}, volume = 36, number = 2, year = 1995, pages = {271-280}, note = {\url{http://www.karlin.mff.cuni.cz/cmuc/pdf/cmuc9502/nesetril.pdf}}, } @Article{Olariu1991, author = {Stephan Olariu}, title = {An optimal greedy heuristic to color interval graphs}, journal = IPL, year = 1991, volume = 37, number = 1, pages = {21-25}, note = {\url{http://dx.doi.org/10.1016/0020-0190(91)90245-D}}, bibupdate = 20070822, } @article{PaigeTarjan1987, author = {Robert Paige and Robert E. Tarjan}, title = {Three partition refinement algorithms}, journal = JOC, volume = 16, number = 6, year = 1987, pages = {973-989}, note = {\url{http://dx.doi.org/10.1137/0216062}}, } @booklet{Paul2006, author = {Christophe Paul}, title = {Aspects algorithmiques de la d{\'e}composition modulaire}, year = 2006, note = {Habilitation thesis}, address = {Universit{\'e} Montpellier II} } @article{RamalingamPanduRangan1990, author = {Ganesan Ramalingam and Chandrasekaran Pandu Rangan}, title = {New sequential and parallel algorithms for interval graph recognition}, journal = IPL, volume = 34, number = 4, year = 1990, pages = {215-219}, note = {\url{http://dx.doi.org/10.1016/0020-0190(90)90163-R}}, comment = { }, bibupdate = {20070805} } @article{RobertsonSeymour1983, author = {Neil Robertson and Paul D. Seymour}, title = {Graph Minors. {I}. {E}xcluding a Forest}, journal = JCTB, year = 1983, volume = 35, pages = {39-61} } @article{RobertsonSeymour1986, author = {Neil Robertson and Paul D. Seymour}, title = {Graph Minors. {II}. {A}lgorithmic Aspects of Tree-Width}, journal = JOA, year = 1986, volume = 7, pages = {309-322} } @Article{Rose1974, author = {Donald J. Rose}, title = {On simple characterizations of $k$-trees}, journal = DM, volume = 7, pages = {317-322}, year = 1974 } @Article{RTL1976, author = {Donald J. Rose and R. Endre Tarjan and George S. Lueker}, title = {Algorithmic Aspects of Vertex Elimination on Graphs}, journal = JOC, volume = 5, number = 2, pages = {266-283}, year = 1976, note = {\url{http://dx.doi.org/10.1137/0205021}}, } @Article{ShamirSharan2004, author = {Ron Shamir and Roded Sharan}, title = {A fully-dynamic algorithm for modular decomposition and recognition of cographs}, journal = DAM, volume = 136, pages = {329-340}, number = {2-3}, year = 2004, note = {\url{http://www.math.tau.ac.il/\~rshamir/papers/dcog\_DAM.ps}}, comment = {alturl \url{http://dx.doi.org/10.1016/S0166-218X(03)00448-7}} } @Article{SchmerlTrotter1993, author = {James H. Schmerl and William T. Trotter}, title = {Critically Indecomposable Partially Ordered Sets, Graphs, Tournaments and Other Binary Relational Structures}, journal = DM, volume = 113, year = 1993, pages = {191-205} } @article{SeymourThomas1993, author = {Paul D. Seymour and Robin Thomas}, title = {Graph searching, and a min-max theorem for tree-width}, journal = JCTB, year = 1993, volume = 58, pages = {22-33} } @InProceedings{Simon1991, author = {Klaus Simon}, title = {A new simple linear algorithm to recognize interval graphs}, year = 1992, pages = {289-308}, booktitle = {Proceedings of the International Workshop on Computational Geometry (CG'91)}, series = LNCS, volume = 553, note = {\url{http://dx.doi.org/10.1007/3-540-54891-2_22}}, bibupdate = {20070604}, publisher = {Springer-Verlag}, } @phdthesis{Spinrad1982, author = {Jeremy P. Spinrad}, title = {Two-dimensional partial orders}, year = 1982, school = {Princeton University}, } @Article{Spinrad1992, author = {Jeremy P. Spinrad}, title = {{$P_4$}-trees and substitution decomposition}, journal = DAM, volume = 39, year = 1992, pages = {263-291}, note = {\url{http://dx.doi.org/10.1016/0166-218X(92)90180-I}} } @Article{Szpilrajn1930, author = {Edward Szpilrajn}, title = {Sur l'extension de l'ordre partiel}, pages = {386-389}, volume = 16, journal = {Fundamenta Mathematicae}, year = 1930, note = {\url{http://matwbn.icm.edu.pl/ksiazki/fm/fm16/fm16125.pdf}}, bibupdate = 20070626, } @phdthesis{Steiner1982, author = {George Steiner}, title = {Machine scheduling with precedence constraints}, year = 1982, school = {Department of Combinatorics and Optimization, University of Waterloo}, } @InProceedings{TCHP2007, author = {Marc Tedder and Derek Corneil and Michel Habib and Christophe Paul}, title = {Simple, Linear-time Modular Decomposition}, year = 2007, booktitle = {Third Workshop on Graph Classes, Optimization, and Width Parameters (GROW'07)}, note = {\url{http://arxiv.org/abs/0710.3901}}, bibupdate = {20071105}, } @article{TYW2001, author = {Shyue-Ming Tang, Fu-Long Yeh and Yue-Li Wang}, title = {An efficient algorithm for solving the homogeneous set sandwich problem}, journal = IPL, volume = 77, number = 1, year = 2001, pages = {17-22}, note = {\url{http://dx.doi.org/10.1016/S0020-0190(00)00145-9}}, bibupdate = {20070814} } @article{Thorup1998, author = {Mikkel Thorup}, title = {Structured Programs have Small Tree-Width and Good Register Allocation}, journal = ICOMP, volume = 142, pages = {159-181}, year = 1998, note = {\url{http://www.diku.dk/hjemmesider/ansatte/mthorup/PAPERS/register.ps.gz}} } @Article{UnoYagiura2000, author = {Takeaki Uno and Mutsunori Yagiura}, title = {Fast Algorithms to Enumerate All Common Intervals of Two Permutations}, journal = {Algorithmica}, year = 2000, volume = 14, pages = {209-227}, note = {\url{http://citeseer.ist.psu.edu/uno00fast.html}}, comment = {alternative link : \url{http://www.al.cm.is.nagoya-u.ac.jp/\~yagiura/papers/common95-e_300dpi.ps.gz}}, bibupdate = {30/10/2006} } @article{Yannakakis1981, author = {Mihalis Yannakakis}, title = {Computing the minimum fill-in is {NP}-complete}, journal = JADM, volume = 2, number = 1, year = 1981, pages = {77-79}, note = {\url{http://dx.doi.org/10.1137/0602010}}, comment = {alt url \url{http://link.aip.org/link/?SML/2/77/1}}, } @article{Yannakakis1982, author = {Mihalis Yannakakis}, title = {The complexity of the partial order dimension problem}, journal = JMAA, volume = 3, number = 3, year = 1982, pages = {351-358}, note = {\url{http://dx.doi.org/10.1137/0603036}}, bibupdate = 20061122, }