End vertices of graph searches on bipartite graphs

Meibiao Zou, Zhifeng Wang, Jianxin Wang, Yixin Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

For a graph search algorithm, the end vertex problem is concerned with which vertices of a graph can be the last visited by this algorithm. We show that for both lexicographic depth-first search and maximum cardinality search, the end vertex problem is NP-complete on bipartite graphs, even if the maximum degree of the graph is bounded.

Original languageEnglish
Article number106176
Pages (from-to)1-7
JournalInformation Processing Letters
Volume173
DOIs
Publication statusPublished - Jan 2022

Keywords

  • Graph algorithms
  • Lexicographic depth-first search
  • Maximum cardinality search

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this