COMPLEXITY OF SPANNING TREE PROBLEMS WITH LEAF-DEPENDENT OBJECTIVES

Authors
DELLAMICO M LABBE M MAFFIOLI F
Citation
M. Dellamico et al., COMPLEXITY OF SPANNING TREE PROBLEMS WITH LEAF-DEPENDENT OBJECTIVES, Networks, 27(3), 1996, pp. 175-181
Citations number
10
Categorie Soggetti
Computer Sciences","Computer Science Hardware & Architecture
Journal title
Networks → ACNP
ISSN journal
00283045
Volume
27
Issue
3
Year of publication
1996
Pages
175 - 181
Database
ISI
SICI code
0028-3045(1996)27:3<175:COSTPW>2.0.ZU;2-2
Abstract
We consider the problem of finding an optimal spanning tree with respe ct to objective functions which depend on the set of leaves of the tre e. We address 18 different such problems and determine their computati onal complexity. Only a few of the problems examined have been given a ttention in the existing literature. (C) 1996 John Wiley & Sons, Inc.