Graph searches and their end vertices

Yixin Cao, Zhifeng Wang, Guozhen Rong, Jianxin Wang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

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 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.

Original languageEnglish
Title of host publication30th International Symposium on Algorithms and Computation, ISAAC 2019
EditorsPinyan Lu, Guochuan Zhang
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages1-18
ISBN (Electronic)9783959771306
DOIs
Publication statusPublished - Dec 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume149
ISSN (Print)1868-8969

Keywords

  • (Lexicographic) breadth-first search
  • (Lexicographic) depth-first search
  • Chordal graph
  • End vertex
  • Maximum cardinality search
  • Weighted clique graph

ASJC Scopus subject areas

  • Software

Cite this