Please use this identifier to cite or link to this item:
http://hdl.handle.net/10397/99112
| Title: | End vertices of graph searches on bipartite graphs | Authors: | Zou, M Wang, Z Wang, J Cao, Y |
Issue Date: | Jan-2022 | Source: | Information processing letters, Jan. 2022, v. 173, 106176 | 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 |
Publisher: | Elsevier | Journal: | Information processing letters | ISSN: | 0020-0190 | DOI: | 10.1016/j.ipl.2021.106176 | Rights: | © 2021 Elsevier B.V. All rights reserved. © 2021. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/. The following publication Zou, M., Wang, Z., Wang, J., & Cao, Y. (2022). End vertices of graph searches on bipartite graphs. Information Processing Letters, 173, 106176 is available at https://dx.doi.org/10.1016/j.ipl.2021.106176. |
| Appears in Collections: | Journal/Magazine Article |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Zou_End_Vertices_Graph.pdf | Pre-Published version | 768.75 kB | Adobe PDF | View/Open |
Access
View full-text via PolyU eLinks 
Page views
119
Last Week
4
4
Last month
Citations as of Nov 9, 2025
Downloads
105
Citations as of Nov 9, 2025
SCOPUSTM
Citations
3
Citations as of Jun 21, 2024
WEB OF SCIENCETM
Citations
2
Citations as of Dec 18, 2025
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.