End vertices of graph searches on bipartite graphs

Meibiao Zou; Zhifeng Wang; Jianxin Wang; Yixin Cao

doi:10.1016/j.ipl.2021.106176

End vertices of graph searches on bipartite graphs

Meibiao Zou, Zhifeng Wang, Jianxin Wang, Yixin Cao

Research output: Journal article publication › Journal article › Academic research › peer-review

4 Citations (Scopus)

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 language	English
Article number	106176
Pages (from-to)	1-7
Journal	Information Processing Letters
Volume	173
DOIs	https://doi.org/10.1016/j.ipl.2021.106176
Publication status	Published - 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

More information

10.1016/j.ipl.2021.106176

http://hdl.handle.net/10397/99112

Cite this

@article{4d59a08e44ff4cfb95e86c1f30f80310,

title = "End vertices of graph searches on bipartite graphs",

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

keywords = "Graph algorithms, Lexicographic depth-first search, Maximum cardinality search",

author = "Meibiao Zou and Zhifeng Wang and Jianxin Wang and Yixin Cao",

note = "Funding Information: Supported by the National Natural Science Foundation of China (61828205, 61672536), the Hunan Provincial Key Lab on Bioinformatics, and the Hunan Provincial Science and Technology Program (2018WK4001).Supported in part by the Hong Kong Research Grants Council (RGC) under grants 15201317 and 15226116 and the National Natural Science Foundation of China (NSFC) under grant 61972330. Publisher Copyright: {\textcopyright} 2021 Elsevier B.V.",

year = "2022",

month = jan,

doi = "10.1016/j.ipl.2021.106176",

language = "English",

volume = "173",

pages = "1--7",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - End vertices of graph searches on bipartite graphs

AU - Zou, Meibiao

AU - Wang, Zhifeng

AU - Wang, Jianxin

AU - Cao, Yixin

N1 - Funding Information: Supported by the National Natural Science Foundation of China (61828205, 61672536), the Hunan Provincial Key Lab on Bioinformatics, and the Hunan Provincial Science and Technology Program (2018WK4001).Supported in part by the Hong Kong Research Grants Council (RGC) under grants 15201317 and 15226116 and the National Natural Science Foundation of China (NSFC) under grant 61972330. Publisher Copyright: © 2021 Elsevier B.V.

PY - 2022/1

Y1 - 2022/1

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

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

KW - Graph algorithms

KW - Lexicographic depth-first search

KW - Maximum cardinality search

UR - https://www.scopus.com/pages/publications/85111821288

U2 - 10.1016/j.ipl.2021.106176

DO - 10.1016/j.ipl.2021.106176

M3 - Journal article

AN - SCOPUS:85111821288

SN - 0020-0190

VL - 173

SP - 1

EP - 7

JO - Information Processing Letters

JF - Information Processing Letters

M1 - 106176

ER -

End vertices of graph searches on bipartite graphs

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this