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.
    • Correction
    • Source
    • Cite
    • Save
    12
    References
    0
    Citations
    NaN
    KQI
    []