A. Berry, J. Blair, P. Heggernes, and B. Peyton, Maximum Cardinality Search for Computing Minimal Triangulations of Graphs, Algorithmica, vol.39, issue.4, pp.287-298, 2004.
DOI : 10.1007/s00453-004-1084-3

A. Berry and J. Bordat, Separability generalizes Dirac's theorem, Discrete Applied Mathematics, vol.84, issue.1-3, pp.43-53, 1998.
DOI : 10.1016/S0166-218X(98)00005-5
URL : http://doi.org/10.1016/s0166-218x(98)00005-5

A. Berry and J. Bordat, Moplex elimination orderings, Proceedings of First Cologne-Twente Workshop on Graphs and Combinatorial Optimization, 2001.
DOI : 10.1016/S1571-0653(05)80065-4
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.8266

A. Berry, R. Krueger, and G. Simonet, Ultimate Generalizations of LexBFS and LEX M, Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science 2005 (WG 2005), pp.199-213, 2005.
DOI : 10.1007/11604686_18

J. R. Blair, P. Heggernes, and J. A. Telle, A practical algorithm for making filled graphs minimal, Theoretical Computer Science, vol.250, issue.1-2, pp.250-251, 2001.
DOI : 10.1016/S0304-3975(99)00126-7

H. L. Bodlaender and A. M. Koster, On the Maximum Cardinality Search Lower Bound for Treewidth, Proceedings, pp.81-92, 2004.

H. L. Bodlaender and A. M. Koster, On the maximum cardinality search lower bound for treewidth, Discrete Applied Mathematics, vol.155, issue.11, pp.1348-1372, 2007.
DOI : 10.1016/j.dam.2007.02.004

D. G. Corneil and R. Krueger, A Unified View of Graph Searching, SIAM Journal on Discrete Mathematics, vol.22, issue.4
DOI : 10.1137/050623498

D. G. Corneil, S. Olariu, and L. Stewart, Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs, SIAM Journal on Computing, vol.28, issue.4, pp.1284-1297, 1999.
DOI : 10.1137/S0097539795282377

E. Dahlhaus, P. L. Hammer, F. Maffray, and S. Olariu, On Domination Elimination Orderings and Domination Graphs, Proceedings of WG 1994, pp.81-92, 1994.

D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacific Journal of Mathematics, vol.15, issue.3, pp.835-855, 1965.
DOI : 10.2140/pjm.1965.15.835
URL : http://projecteuclid.org/download/pdf_1/euclid.pjm/1102995572

T. Ohtsuki, A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph, SIAM Journal on Computing, vol.5, issue.1, pp.133-145, 1976.
DOI : 10.1137/0205012

T. Ohtsuki, L. K. Cheung, and T. Fujisawa, Minimal triangulation of a graph and optimal pivoting order in a sparse matrix, Journal of Mathematical Analysis and Applications, vol.54, issue.3, pp.622-633, 1976.
DOI : 10.1016/0022-247X(76)90182-7

D. Rose, R. E. Tarjan, and G. Lueker, Algorithmic Aspects of Vertex Elimination on Graphs, SIAM Journal on Computing, vol.5, issue.2, pp.146-160, 1976.
DOI : 10.1137/0205021

D. R. Shier, Some aspects of perfect elimination orderings in chordal graphs, Discrete Applied Mathematics, vol.7, issue.3, pp.325-331, 1984.
DOI : 10.1016/0166-218X(84)90008-8

R. E. Tarjan and M. Yannakakis, Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs, SIAM Journal on Computing, vol.13, issue.3, pp.566-579, 1984.
DOI : 10.1137/0213035

P. Van-emde and . Boas, Preserving order in a forest in less than logarithmic time and linear space, Information Processing Letters, vol.6, issue.3, pp.80-82, 1977.
DOI : 10.1016/0020-0190(77)90031-X

P. Van-emde-boas, R. Kaas, and E. Zijlstra, Design and implementation of an efficient priority queue, Mathematical Systems Theory, vol.22, issue.1, pp.99-127, 1977.
DOI : 10.1007/BF01683268

Y. Villanger, M. Lex, and M. , Lex M versus MCS-M, Discrete Mathematics, vol.306, issue.3, pp.393-400, 2004.
DOI : 10.1016/j.disc.2005.12.005
URL : http://doi.org/10.1016/j.disc.2005.12.005

=. Let-k, By a) and Lemma 6.1, ?t ? µ\{y}, label k (t) ? label k (y) So ?(k) = y, which completes the proof. c) We assume for contradiction that ?t ? µ \ {y}, ? ?1 (t) < ? ?1 (y) and ?t ? µ \ {y} | N um i (t) ? N um i (y) By Lemma 6.2 ?t 1 ? µ \ {y} | ?t ? µ[t 1 , y] \ {t 1 }, N um i (t) ? N um i (t 1 ), pp.1-1