On end-vertices of Lexicographic Breadth First Searches
Recently Lexicographic Breadth First Search (LBFS) has received considerable attention and has often been employed in a multi-sweep fashion. One variant of LBFS called LBFS+breaks ties by choosing the last vertex of the tied set in a previous LBFS. This has motivated the study of vertices that may appear last in an LBFS (called end-vertices). In this paper, we present various theoretical and algorithmic results concerning end-vertices.
lexicographic breadth first search graph algorithm complexity simplicial vertex graph classes chordal graphs interval graphs at-free graphs cocomparability graphs