2019/05/23 by Yixin Cao, Guozhen Rong, Cao, Yixin +5
Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #Constraint Satisfaction and Optimization #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1905.09505
openalex publication_date 2019/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Graph search, the process of visiting vertices in a graph in a specific order, has demonstrated magical powers in many important algorithms. But a systematic study was only initiated by Corneil et al.~a decade ago, and only by then we started to realize how little we understand it. Even the apparently naïve question "which vertex can be the last visited by a graph search algorithm," known as the end vertex problem, turns out to be quite elusive. We give a full picture of all maximum cardinality searches on chordal graphs, which implies a polynomial-time algorithm for the end vertex problem of maximum cardinality search. It is complemented by a proof of NP-completeness of the same problem on weakly chordal graphs. We also show linear-time algorithms for deciding end vertices of breadth-first searches on interval graphs, and end vertices of lexicographic depth-first searches on chordal graphs. Finally, we present 2n⋅ nO(1)-time algorithms for deciding the end vertices of breadth-first searches, depth-first searches, maximum cardinality searches, and maximum neighborhood searches on general graphs.