The complexity of spanning tree problems involving graphical indices

Yanni Dong; Hajo Broersma; Yuhang Bai; Shenggui Zhang

doi:10.1016/j.dam.2024.01.005

The complexity of spanning tree problems involving graphical indices

Yanni Dong, Hajo Broersma, Yuhang Bai, Shenggui Zhang

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

We consider the computational complexity of spanning tree problems involving the graphical function-index. This index was recently introduced by Li and Peng as a unification of a long list of chemical and topological indices. We present a number of unified approaches to determine the NP-completeness and APX-completeness of maximum and minimum spanning tree problems involving this index. We give many examples of well-studied topological indices for which the associated complexity questions are covered by our results.

Original language	English
Pages (from-to)	143-154
Number of pages	12
Journal	Discrete Applied Mathematics
Volume	347
DOIs	https://doi.org/10.1016/j.dam.2024.01.005
State	Published - 15 Apr 2024

Keywords

APX-complete
Graphical function-index
NP-complete
Spanning tree

Access to Document

10.1016/j.dam.2024.01.005

Cite this

@article{5b75b32002de4f4bb0d80956587868ec,

title = "The complexity of spanning tree problems involving graphical indices",

abstract = "We consider the computational complexity of spanning tree problems involving the graphical function-index. This index was recently introduced by Li and Peng as a unification of a long list of chemical and topological indices. We present a number of unified approaches to determine the NP-completeness and APX-completeness of maximum and minimum spanning tree problems involving this index. We give many examples of well-studied topological indices for which the associated complexity questions are covered by our results.",

keywords = "APX-complete, Graphical function-index, NP-complete, Spanning tree",

author = "Yanni Dong and Hajo Broersma and Yuhang Bai and Shenggui Zhang",

note = "Publisher Copyright: {\textcopyright} 2024 The Authors",

year = "2024",

month = apr,

day = "15",

doi = "10.1016/j.dam.2024.01.005",

language = "英语",

volume = "347",

pages = "143--154",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - The complexity of spanning tree problems involving graphical indices

AU - Dong, Yanni

AU - Broersma, Hajo

AU - Bai, Yuhang

AU - Zhang, Shenggui

PY - 2024/4/15

Y1 - 2024/4/15

N2 - We consider the computational complexity of spanning tree problems involving the graphical function-index. This index was recently introduced by Li and Peng as a unification of a long list of chemical and topological indices. We present a number of unified approaches to determine the NP-completeness and APX-completeness of maximum and minimum spanning tree problems involving this index. We give many examples of well-studied topological indices for which the associated complexity questions are covered by our results.

AB - We consider the computational complexity of spanning tree problems involving the graphical function-index. This index was recently introduced by Li and Peng as a unification of a long list of chemical and topological indices. We present a number of unified approaches to determine the NP-completeness and APX-completeness of maximum and minimum spanning tree problems involving this index. We give many examples of well-studied topological indices for which the associated complexity questions are covered by our results.

KW - APX-complete

KW - Graphical function-index

KW - NP-complete

KW - Spanning tree

UR - http://www.scopus.com/inward/record.url?scp=85182736455&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2024.01.005

DO - 10.1016/j.dam.2024.01.005

M3 - 文章

AN - SCOPUS:85182736455

SN - 0166-218X

VL - 347

SP - 143

EP - 154

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

The complexity of spanning tree problems involving graphical indices

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this