2026-07-23T20:16:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11497 2024-03-06T10:48:09Z ddc:004 open_access

Graph Searches and Their End Vertices Cao, Yixin Wang, Zhifeng Rong, Guozhen Wang, Jianxin maximum cardinality search (lexicographic) breadth-first search (lexicographic) depth-first search chordal graph weighted clique graph end vertex 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 2^n * n^O(1)-time algorithms for deciding the end vertices of breadth-first searches, depth-first searches, and maximum cardinality searches on general graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yixin Cao and Zhifeng Wang and Guozhen Rong and Jianxin Wang 2019 Is Part Of LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2019.1 urn:nbn:de:0030-drops-114973 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.1 eng https://creativecommons.org/licenses/by/3.0/legalcode