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

数学与统计学院

科研成果: 期刊稿件 › 文章 › 同行评审

1 引用（Scopus）

摘要

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.

源语言	英语
页（从-至）	143-154
页数	12
期刊	Discrete Applied Mathematics
卷	347
DOI	https://doi.org/10.1016/j.dam.2024.01.005
出版状态	已出版 - 15 4月 2024

访问文件

10.1016/j.dam.2024.01.005

其它文件与链接

链接到 Scopus 的出版物

引用此

@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

摘要

访问文件

其它文件与链接

指纹

引用此