TY - GEN
T1 - Graph searches and their end vertices
AU - Cao, Yixin
AU - Wang, Zhifeng
AU - Rong, Guozhen
AU - Wang, Jianxin
PY - 2019/12
Y1 - 2019/12
N2 - 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, and maximum cardinality searches on general graphs.
AB - 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, and maximum cardinality searches on general graphs.
KW - (Lexicographic) breadth-first search
KW - (Lexicographic) depth-first search
KW - Chordal graph
KW - End vertex
KW - Maximum cardinality search
KW - Weighted clique graph
UR - http://www.scopus.com/inward/record.url?scp=85076354177&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ISAAC.2019.1
DO - 10.4230/LIPIcs.ISAAC.2019.1
M3 - Conference article published in proceeding or book
AN - SCOPUS:85076354177
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 1
EP - 18
BT - 30th International Symposium on Algorithms and Computation, ISAAC 2019
A2 - Lu, Pinyan
A2 - Zhang, Guochuan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ER -