Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419573 | Discrete Applied Mathematics | 2010 | 10 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Derek G. Corneil, Ekkehard Köhler, Jean-Marc Lanlignel,