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
- Machine Reading By IdeaReader
12
References
0
Citations
NaN
KQI