(Quasi-)linear time algorithm to compute LexDFS, LexUP and LexDown orderings

Arthur Milchior

We consider the three graph search algorithm LexDFS, LexUP and LexDOWN. We show that LexUP orderings can be computed in linear time by an algorithm similar to the one which compute…