Abstract
For a graph search algorithm, the end vertex problem is concerned with which vertices of a graph can be the last visited by this algorithm. We show that for both lexicographic depth-first search and maximum cardinality search, the end vertex problem is NP-complete on bipartite graphs, even if the maximum degree of the graph is bounded.
Original language | English |
---|---|
Article number | 106176 |
Pages (from-to) | 1-7 |
Journal | Information Processing Letters |
Volume | 173 |
DOIs | |
Publication status | Published - Jan 2022 |
Keywords
- Graph algorithms
- Lexicographic depth-first search
- Maximum cardinality search
ASJC Scopus subject areas
- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications