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 -