Lexicographic breadth-first search
Encyclopedia
In computer science
, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph, that is used as part of other graph algorithms such as the recognition of chordal graph
s and optimal coloring
of distance-hereditary graph
s. The algorithm for constructing Lex-BFS orderings is different from a standard breadth-first search
; every Lex-BFS ordering is a possible BFS ordering but not vice versa. The lexicographic breadth-first search algorithm is based on the idea of partition refinement
and was first developed by . A more detailed survey of the topic is presented by .
, 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, like simpler graph search algorithms such as breadth-first search and depth first search, this algorithm takes linear time.
The algorithm is called lexicographic breadth-first search because the lexicographic order it produces is an ordering that could also have been produced by a breadth-first search, and because if the ordering is used to index the rows and columns of an adjacency matrix
of a graph then the algorithm sorts
the rows and columns into Lexicographical order
.
if its vertices have a perfect elimination ordering, an ordering such that for any vertex v the neighbors that occur later in the ordering form a clique. In a chordal graph, the reverse of a lexicographic ordering is always a perfect elimination ordering. Therefore, as Rose, Tarjan, and Lueker show, one can test whether a graph is chordal in linear time by the following algorithm:
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 graph
s: 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.
of the input graph. As they show, this can be used to recognize cograph
s in linear time. describe additional applications of lexicographic breadth-first search including the recognition of comparability graph
s and interval graph
s.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph, that is used as part of other graph algorithms such as the recognition of chordal graph
Chordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
s and optimal coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
of distance-hereditary graph
Distance-hereditary graph
In graph-theoretic mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph...
s. The algorithm for constructing Lex-BFS orderings is different from a standard breadth-first search
Breadth-first search
In graph theory, breadth-first search is a graph search algorithm that begins at the root node and explores all the neighboring nodes...
; every Lex-BFS ordering is a possible BFS ordering but not vice versa. The lexicographic breadth-first search algorithm is based on the idea of partition refinement
Partition refinement
In the design of algorithms, partition refinement is a technique for representing a partition of a set as a data structure that allows the partition to be refined by splitting its sets into a larger number of smaller sets. In that sense it is dual to the union-find data structure, which also...
and was first developed by . A more detailed survey of the topic is presented by .
The algorithm
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. At each step, a vertex v from the first set in the sequence is removed from that set, and if that removal causes the set to become empty then the set is removed from the sequence. Then, each set in the sequence is replaced by two subsets: the neighbors of v and the non-neighbors of v. The subset of neighbors is placed earlier in the sequence than the subset of non-neighbors. In pseudocodePseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
, the algorithm can be expressed as follows:
- Initialize a sequence Σ of sets, to contain a single set containing all vertices.
- Initialize the output sequence of vertices to be empty.
- While Σ is non-empty:
- Find and remove a vertex v from the first set in Σ
- If the first set in Σ is now empty, remove it from Σ
- Add v to the end of the output sequence.
- For each edge v-w such that w still belongs to a set S in Σ:
- If the set S containing w has not yet been replaced while processing v, create a new empty replacement set T and place it prior to S in the sequence; otherwise, let T be the set prior to S.
- Move w from S to T, and if this causes S to become empty remove S from the sequence.
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, like simpler graph search algorithms such as breadth-first search and depth first search, this algorithm takes linear time.
The algorithm is called lexicographic breadth-first search because the lexicographic order it produces is an ordering that could also have been produced by a breadth-first search, and because if the ordering is used to index the rows and columns of an adjacency matrix
Adjacency matrix
In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...
of a graph then the algorithm sorts
Sorting algorithm
In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...
the rows and columns into Lexicographical order
Lexicographical order
In mathematics, the lexicographic or lexicographical order, , is a generalization of the way the alphabetical order of words is based on the alphabetical order of letters.-Definition:Given two partially ordered sets A and B, the lexicographical order on...
.
Chordal graphs
A graph G is defined to be chordalChordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
if its vertices have a perfect elimination ordering, an ordering such that for any vertex v the neighbors that occur later in the ordering form a clique. In a chordal graph, the reverse of a lexicographic ordering is always a perfect elimination ordering. Therefore, as Rose, Tarjan, and Lueker show, one can test whether a graph is chordal in linear time by the following algorithm:
- Use lexicographic breadth-first search to find a lexicographic ordering of G
- Reverse this ordering
- For each vertex v:
- Let w be the neighbor of v occurring prior to v in the reversed sequence, as close to v in the sequence as possible
- (Continue to the next vertex v if there is no such w)
- If the set of earlier neighbors of v (excluding w itself) is not a subset of the set of earlier neighbors of w, the graph is not chordal
- Let w be the neighbor of v occurring prior to v in the reversed sequence, as close to v in the sequence as possible
- If the loop terminates without showing that the graph is not chordal, then it is chordal.
Graph coloring
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 coloringGreedy coloring
In the study of graph coloring problems in mathematics and computer science, a greedy coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color...
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 graph
Distance-hereditary graph
In graph-theoretic mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph...
s: 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.
Other applications
describe an extension of lexicographic breadth-first search that breaks any additional ties using the complement graphComplement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
of the input graph. As they show, this can be used to recognize cograph
Cograph
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
s in linear time. describe additional applications of lexicographic breadth-first search including the recognition of comparability graph
Comparability graph
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order...
s and interval graph
Interval graph
In graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
s.