Premium
Complexity of spanning tree problems with leaf‐dependent objectives
Author(s) -
Dell'Amico Mauro,
Labbé Martine,
Maffioli Francesco
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199605)27:3<175::aid-net2>3.0.co;2-f
Subject(s) - spanning tree , tree (set theory) , minimum spanning tree , computational complexity theory , computer science , mathematics , set (abstract data type) , mathematical optimization , combinatorics , algorithm , programming language
We consider the problem of finding an optimal spanning tree with respect to objective functions which depend on the set of leaves of the tree. We address 18 different such problems and determine their computational complexity. Only a few of the problems examined have been given attention in the existing literature. © 1996 John Wiley & Sons, Inc.