# End vertices of graph searches on bipartite graphs

2022

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.

Keywords:

- Correction
- Source
- Cite
- Save

12

References

0

Citations

NaN

KQI