Md-MST is NP-hard for d = 3

De Almeida, A.M. , Martins, P. , Souza, M.C.

ISLA — Instituto Politécnico de Gestão e Tecnologia

Electronic Notes in Discrete Mathematics, Volume 36, Issue C, 2010, pp. 9–15

DOI: 10.1016/j.endm.2010.05.002

Resume

Abstract

Abstract not provided by the author or the indexing source.

Keywords

#NP-hardness #spanning trees #weighted undirected graphs #combinatorial optimization #computational complexity #Combinatorics #Mathematics #Spanning tree #Minimum degree spanning tree #Minimum spanning tree #Connected dominating set #Gomory–Hu tree #Shortest-path tree #Degree (music) #Tree (set theory) #Graph #Node (physics)

Bibliographic Details

Publication Type Journal article

Publication Year 2010

Journal / Conference / Work Electronic Notes in Discrete Mathematics

Volume / Issue Vol. 36 (C)

Pagination pp. 9–15

Quartile (SCImago) Q4

Scopus Indexing Indexed source (via SCImago)

ISLA Authors & Affiliations

Pedro João Coimbra Martins

pmartins@iscac.pt ID: 1113-BC3A-435F

Profile