LexBFS

LexBFS, short for lexicographic breadth-first search, is a graph traversal algorithm that produces a linear ordering of the vertices by repeatedly selecting the unvisited vertex with the largest label in lexicographic order. Each vertex maintains a label, a sequence of integers, initially empty. When a vertex is visited, each unvisited neighbor has its label extended by the position index of the visited vertex; ties during selection are resolved arbitrarily. The process yields a vertex order that reflects the lexicographic history of the search as it unfolds along the graph's adjacency structure.

Use and significance: The ordering produced by LexBFS is especially useful in recognition and decomposition tasks. A central result is that chordal graphs can be recognized via LexBFS by producing a perfect elimination ordering, where each vertex's neighbors later in the order form a clique. In particular, a graph is chordal if a LexBFS ordering is a perfect elimination ordering, and linear-time chordal recognition algorithms are built on this principle. LexBFS, often together with other lexicographic variants, also plays a role in recognizing interval graphs and related classes, and is used to compute structures such as clique trees in chordal graphs.

Complexity: With optimized data structures, LexBFS can be implemented in O(n + m) time and O(n + m) space, linear in the size of the graph. Naive implementations may be slower, typically O(nm).

History: LexBFS was introduced in the study of chordal graph recognition, with foundational work by Rose, Tarjan, and Lueker in 1976.