Lexicographic breadth-first search

In computer science, lexicographic breadth-first search or Lex-BFS is a linear time algorithm for ordering the vertices of a graph. The algorithm is different from a breadth-first search, but it produces an ordering that is consistent with breadth-first search.

Graph and tree search algorithms
α–β pruning Backtracking Beam search Best-first search Branch & bound Breadth-First Search (BFS) British Museum Depth-First Search (DFS) Hill climbing Iterative Deepening DFS (IDDFS) Lexicographic BFS
Shortest path
A* B* Bellman–Ford Bidirectional search D* Dijkstra's Floyd–Warshall Fringe search Iterative Deepening (IDA) Johnson's Jump point search Kruskal's Lifelong Planning A (LPA) Pathfinding SMA
Lists
Graph algorithms Search algorithms List of graph algorithms
Related topics
Dynamic programming Graph coloring Graph traversal Minimum spanning tree Search games Threaded binary tree Tree traversal
v t e

The lexicographic breadth-first search algorithm is based on the idea of partition refinement and was first developed by Donald J. Rose, Robert E. Tarjan, and George S. Lueker (1976). A more detailed survey of the topic is presented by Corneil (2004). It has been used as a subroutine in other graph algorithms including the recognition of chordal graphs, and optimal coloring of distance-hereditary graphs.

Share this article:

This article uses material from the Wikipedia article Lexicographic breadth-first search, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.