Cao, Yixin ;
Wang, Zhifeng ;
Rong, Guozhen ;
Wang, Jianxin
Graph Searches and Their End Vertices
Abstract
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 polynomialtime algorithm for the end vertex problem of maximum cardinality search. It is complemented by a proof of NPcompleteness of the same problem on weakly chordal graphs. We also show lineartime algorithms for deciding end vertices of breadthfirst searches on interval graphs, and end vertices of lexicographic depthfirst searches on chordal graphs. Finally, we present 2^n * n^O(1)time algorithms for deciding the end vertices of breadthfirst searches, depthfirst searches, and maximum cardinality searches on general graphs.
BibTeX  Entry
@InProceedings{cao_et_al:LIPIcs:2019:11497,
author = {Yixin Cao and Zhifeng Wang and Guozhen Rong and Jianxin Wang},
title = {{Graph Searches and Their End Vertices}},
booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)},
pages = {1:11:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771306},
ISSN = {18688969},
year = {2019},
volume = {149},
editor = {Pinyan Lu and Guochuan Zhang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11497},
URN = {urn:nbn:de:0030drops114973},
doi = {10.4230/LIPIcs.ISAAC.2019.1},
annote = {Keywords: maximum cardinality search, (lexicographic) breadthfirst search, (lexicographic) depthfirst search, chordal graph, weighted clique graph, end verte}
}
28.11.2019
Keywords: 

maximum cardinality search, (lexicographic) breadthfirst search, (lexicographic) depthfirst search, chordal graph, weighted clique graph, end verte 
Seminar: 

30th International Symposium on Algorithms and Computation (ISAAC 2019)

Issue date: 

2019 
Date of publication: 

28.11.2019 