T. , A. New, . For, . Graph, and . Proof, Suppose that ? is a generic search ordering Using Lemma 6.3.1 on ?, we know that: ? is a generic ordering ?? for every x, y ? V (G), x < ? y, N ? (x, x) < gen N ? (y, x) ?? for every x, y ? V (G), x < ? y, N ? (y, x) = ? or N ? (x, x) = ? ?? for every x (x, x) = ? ?? for every triple of vertices a

T. , A. New, and . For, for every triple a, b, c ? V (G) such that a < ? b < ? c and a is the leftmost vertex of N (b) N (c) in ?

T. , A. New, A. For, and A. Df-s-b, Let us show that < LexU P (respectively < LexDOW N ) is an extension of < gen . Let A < gen B. By definition we have A = ? and B = ?. As a consequence we have (umax(A) < min, )) implying A < LexDOW N B)

<. We-now-show-that, <. Lbf-s-is-an-extension-of, . S. Bf, and A. <. Let, By definition, we have umin(B) < umin(A) As a consequence

<. Bls, (v)) < GLS ?(l T BLS,i (w)), and l GLS,i (v) < GLS l GLS,i (w) if and only if for all l v ? ? ?1 (l GLS,i (v)) and all l w ? ? ?1 (l GLS,i (w)), l v < T BLS l w . Thus, the set of eligible vertices at step i is the same for both algorithms. GLS can pick any of these vertices, particular the one that would be picked by T BLS(G, < T BLS , ? ), and by setting ? to be equal to GLS(G, S), TBLS would indeed choose the right vertex

T. , A. New, and . For, Computing a TBLS ordering Let P be the partition {V (G)}, where the only part V (G) is ordered with respect to ? ; for i ? 1 to n do Let Eligible be the part of P with the largest label with respect to < and x its first vertex; replace Eligible by Eligible ? {x} in P ; ?(i) ? x

T. , A. New, and . For, 88] Behrendt B. Maximal antichains in partially ordered sets, Ars Combinatoria, vol.25, issue.24, pp.149-157, 1988.

A. Bretscher, D. G. Corneil, M. Habib, and C. Paul, A Simple Linear Time LexBFS Cograph Recognition Algorithm, SIAM Journal on Discrete Mathematics, vol.22, issue.4
DOI : 10.1137/060664690
URL : https://hal.archives-ouvertes.fr/lirmm-00269525

A. Brandstädt, F. F. Dragan, and F. Nicolai, LexBFS-orderings and powers of chordal graphs, Discrete Mathematics, vol.171, issue.1-3, pp.27-42, 1997.
DOI : 10.1016/S0012-365X(96)00070-2

A. Berry, R. Pogorelcnik, and . Simonet, An Introduction to Clique Minimal Separator Decomposition, Algorithms, vol.3, issue.2, pp.197-215, 2010.
DOI : 10.3390/a3020197
URL : https://hal.archives-ouvertes.fr/lirmm-00485851

G. Cdh-+-]-derek, J. Corneil, M. Dusart, and . Habib, Antoine Mamcarz, and Fabien de Mongolfier. A new model for graph search. submitted at, Discrete Applied Mathematics, p.94

D. G. Corneil, B. Dalton, M. Habib, D. G. Corneil, J. Dusart et al., LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs, SIAM Journal on Computing, vol.42, issue.3, pp.792-807, 2011.
DOI : 10.1137/11083856X
URL : https://hal.archives-ouvertes.fr/hal-00936300

G. Derek, E. Corneil, and . Köhler, Unpublished manuscript, p.91

G. Derek, R. Corneil, and . Krueger, A unified view of graph searching, SIAM J. Discrete Math, vol.22, issue.107, pp.1259-1276, 2003.

H. Thomas, C. E. Cormen, R. L. Leiserson, C. Rivest, and . Stein, Introduction to Algorithms, 2001.

D. G. Corneil, Lexicographic Breadth First Search ??? A Survey, proceedings of WG, pp.1-19, 2004.
DOI : 10.1007/978-3-540-30559-0_1

G. Derek and . Corneil, A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs, Discrete Applied Mathematics, vol.138, issue.96, pp.371-379, 2004.

D. G. Corneil, S. Olariu, and L. Stewart, The LBFS Structure and Recognition of Interval Graphs, SIAM Journal on Discrete Mathematics, vol.23, issue.4, pp.1905-1953, 2009.
DOI : 10.1137/S0895480100373455

C. Crespelle and I. Todinca, An o(n 2 )o(n2)-time algorithm for the minimal interval completion problem, Theor. Comput
URL : https://hal.archives-ouvertes.fr/hal-00480750

J. Dusart and M. Habib, A new LBFS-based algorithm for cocomparability graph recognition. submitted at, Discrete Applied Mathematics, vol.3, issue.76, p.93
URL : https://hal.archives-ouvertes.fr/hal-01274023

B. Dushnik and E. W. Miller, Partially ordered sets Maximal chordal subgraphs, American Journal of Mathematics Discrete Applied Mathematics, vol.63, issue.203, pp.600-610181, 1941.

J. Dusart, Parcours de graphes, p.102, 2010.
URL : https://hal.archives-ouvertes.fr/tel-01273352

P. C. Gilmore and A. J. Hoffman, A characterization of comparability graphs and of interval graphs. Canad, J. Math, vol.16, issue.17, pp.539-548, 1964.

M. Charles and G. , Algorithmic Graph Theory and Perfect Graphs The Netherlands, The Netherlands, Annals of Discrete Mathematics, vol.57, issue.10, pp.14-16, 2004.

M. Habib, M. Morvan, M. Pouzet, and J. Rampon, Extensions intervallaires minimales, Compte Rendù a l'Académie des Sciences, présenté en septembre 91, par le Pr. G. Choquet, pp.893-898, 1991.

M. Habib, M. Morvan, M. Pouzet, and J. Rampon, Incidence structures, coding and lattice of maximal antichains, p.36, 1992.

M. Habib, R. M. Mcconnell, C. Paul, and L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, vol.234, issue.1-2, pp.59-84, 2000.
DOI : 10.1016/S0304-3975(97)00241-7

P. Heggernes, K. Suchan, I. Todinca, and Y. Villanger, Minimal Interval Completions, Lecture Notes in Computer Science, vol.3669, pp.403-414, 2005.
DOI : 10.1007/11561071_37
URL : https://hal.archives-ouvertes.fr/hal-00085564

R. Kratsch and L. Stewart, Domination on Cocomparability Graphs, SIAM Journal on Discrete Mathematics, vol.6, issue.3, pp.400-417, 1993.
DOI : 10.1137/0406032

R. Krueger, . Genevì-eve, A. Simonet, and . Berry, A General Label Search to investigate classical graph search algorithms, Discrete Applied Mathematics, vol.159, issue.2-3, pp.128-142, 2011.
DOI : 10.1016/j.dam.2010.02.011
URL : https://hal.archives-ouvertes.fr/lirmm-00371177

J. Boland and C. Lekkeikerker, Representation of a finite graph by a set of intervals on the real line, Fundamenta Mathematicae, vol.51, issue.1, pp.45-64, 1962.

P. Li and Y. Wu, A four-sweep LBFS recognition algorithm for interval graphs, Discrete Mathematics and Theoretical Computer Science, issue.9, 2013.
URL : https://hal.archives-ouvertes.fr/hal-01188908

G. Markowsky, The factorization and representation of lattices. Transactions of the, pp.185-200, 1975.

G. Markowsky, Primes, irreductibles and extremal lattices. Order, pp.265-290, 1992.

B. George, D. G. Mertzios, and . Corneil, A simple polynomial algorithm for the longest path problem on cocomparability graphs, SIAM J. Discrete Math, vol.26, issue.3 2, pp.940-963, 2012.

D. Meister, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Discrete Applied Mathematics, vol.146, issue.3, pp.193-218, 2005.
DOI : 10.1016/j.dam.2004.10.001

M. Ross, K. Mcconnell, S. Mehlhorn, P. Näherc, and . Schweitzerd, Certifying algorithms Modular decomposition and transitive orientation, Computer Science Review Discrete Mathematics, vol.5, issue.51, pp.119-161, 1999.

S. Olariu, An optimal greedy heuristic to color interval graphs, Information Processing Letters, vol.37, issue.1, pp.21-25, 1991.
DOI : 10.1016/0020-0190(91)90245-D

A. Raychaudhuri, On powers of interval and unit interval graphs

F. S. Roberts, On the compatibility between a graph and a simple order, Journal of Combinatorial Theory, Series B, vol.11, issue.1, p.115, 1971.
DOI : 10.1016/0095-8956(71)90010-4

G. Ramalingam and C. Pandu-rangan, A unified approach to domination problems on interval graphs, Information Processing Letters, vol.27, issue.5, pp.271-274, 1988.
DOI : 10.1016/0020-0190(88)90091-9

J. Donald, R. E. Rose, and . Tarjan, Algorithmic aspects of vertex elimination

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

M. Sharir, A strong-connectivity algorithm and its applications in data flow analysis, Computers & Mathematics with Applications, vol.7, issue.1, pp.6772-93, 1981.
DOI : 10.1016/0898-1221(81)90008-0

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

J. Spinrad, Efficient implementation of lexicographic depth first search. submitted for publication, p.12

J. Spinrad, Depth-first search and linear graph algorithms, Efficient Graph Representations. Fields Institute Monographs, vol.19, 2003.

. Robert-endre-tarjan, Decomposition by clique separators, Discrete Mathematics, vol.55, issue.2, pp.221-232, 1985.
DOI : 10.1016/0012-365X(85)90051-2

M. Tedder, D. G. Corneil, M. Habib, and C. Paul, Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations, Lecture Notes in Computer Science, vol.5125, issue.1 9, pp.634-645, 2008.
DOI : 10.1007/978-3-540-70575-8_52

E. Robert, M. Tarjan, and . Yannakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput, vol.13, issue.101, pp.566-579, 1984.

M. Yannakakis, Computing the Minimum Fill-In is NP-Complete, SIAM Journal on Algebraic Discrete Methods, vol.2, issue.1, pp.77-79, 1981.
DOI : 10.1137/0602010