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

^*Corresponding author for this work

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

1 Citation (Scopus)

63 Downloads (Pure)

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
Early online date	19 Jan 2024
DOIs	https://doi.org/10.1016/j.dam.2024.01.005
Publication status	Published - 15 Apr 2024

Keywords

UT-Hybrid-D
Graphical function-index
NP-complete
Spanning tree
APX-complete

Access to Document

10.1016/j.dam.2024.01.005Licence: CC BY

ArticleFinal published version, 429 KBLicence: CC BY

Cite this

@article{ef150e6e3ea94e339908f1724a1c3584,

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 = "UT-Hybrid-D, Graphical function-index, NP-complete, Spanning tree, APX-complete",

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 = "English",

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 - UT-Hybrid-D

KW - Graphical function-index

KW - NP-complete

KW - Spanning tree

KW - APX-complete

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 - Article

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