In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph.
The lexicographic breadth-first search algorithm is based on the idea of partition refinement and was first developed by Donald J.
The breadth-first search algorithm is commonly defined by the following process: However, rather than defining the vertex to choose at each step in an imperative way as the one produced by the dequeue operation of a queue, one can define the same sequence of vertices declaratively by the properties of these vertices.
That is, a standard breadth-first search is just the result of repeatedly applying this rule: In some cases, this ordering of vertices by the output positions of their predecessors may have ties — two different vertices have the same earliest predecessor.
In this case, the order in which those two vertices are chosen may be arbitrary.
The output of lexicographic breadth-first search differs from a standard breadth-first search in having a consistent rule for breaking such ties.
In lexicographic breadth-first search, the output ordering is the order that would be produced by the rule: So, when two vertices v and w have the same earliest predecessor, earlier than any other unchosen vertices, the standard breadth-first search algorithm will order them arbitrarily.
Instead, in this case, the LexBFS algorithm would choose between v and w by the output ordering of their second-earliest predecessors.
Instead, the lexicographic breadth-first search uses a set partitioning data structure in order to produce the same ordering more efficiently, just as a standard breadth-first search uses a queue data structure to produce its ordering efficiently.
The lexicographic breadth-first search algorithm replaces the queue of vertices of a standard breadth-first search with an ordered sequence of sets of vertices.
The sets in the sequence form a partition of the remaining vertices.
In pseudocode, the algorithm can be expressed as follows: Each vertex is processed once, each edge is examined only when its two endpoints are processed, and (with an appropriate representation for the sets in Σ that allows items to be moved from one set to another in constant time) each iteration of the inner loop takes only constant time.
Therefore, one can test whether a graph is chordal in linear time by the following algorithm: This application was the original motivation that led Rose, Tarjan & Lueker (1976) to develop the lexicographic breadth first search algorithm.
[1] A graph G is said to be perfectly orderable if there is a sequence of its vertices with the property that, for any induced subgraph of G, a greedy coloring algorithm that colors the vertices in the induced sequence ordering is guaranteed to produce an optimal coloring.
For a chordal graph, a perfect elimination ordering is a perfect ordering: the number of the color used for any vertex is the size of the clique formed by it and its earlier neighbors, so the maximum number of colors used is equal to the size of the largest clique in the graph, and no coloring can use fewer colors.
An induced subgraph of a chordal graph is chordal and the induced subsequence of its perfect elimination ordering is a perfect elimination ordering on the subgraph, so chordal graphs are perfectly orderable, and lexicographic breadth-first search can be used to optimally color them.
The same property is true for a larger class of graphs, the distance-hereditary graphs: distance-hereditary graphs are perfectly orderable, with a perfect ordering given by the reverse of a lexicographic ordering, so lexicographic breadth-first search can be used in conjunction with greedy coloring algorithms to color them optimally in linear time.
[2] Bretscher et al. (2008) describe an extension of lexicographic breadth-first search that breaks any additional ties using the complement graph of the input graph.
As they show, this can be used to recognize cographs in linear time.
Habib et al. (2000) describe additional applications of lexicographic breadth-first search including the recognition of comparability graphs and interval graphs.