Lexicographic breadth-first search, or Lex-BFS, is a linear time algorithm for ordering the vertices of a graph, differing from standard breadth-first search but generating an ordering consistent with it. The method was first developed by Donald J. Rose, Robert E. Tarjan and George S. Lueker in 1976 and uses partition refinement principles; it serves as a component in other graph algorithms, particularly for recognizing chordal graphs and for optimal coloring of distance hereditary graphs.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.