Back to Search Start Over

Complexity of spanning tree problems with leaf-dependent objectives

Authors :
Mauro Dell'Amico
Francesco Maffioli
Martine Labbé
Graphes et Optimisation Mathématique [Bruxelles] (GOM)
Université libre de Bruxelles (ULB)
Fortz, Bernard
Source :
Networks, Networks, Wiley, 1996, 27, pp.175-181
Publication Year :
1996
Publisher :
HAL CCSD, 1996.

Abstract

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.

Subjects

Subjects :
Mathematical optimization
Spanning tree
[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]
Computational complexity theory
Computer Networks and Communications
Graph theory
Maximization
[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]
Tree (graph theory)
Hardware and Architecture
Minification
Software
Decision tree model
ComputingMilieux_MISCELLANEOUS
Information Systems
Mathematics

Details

Language :
English
ISSN :
00283045 and 10970037
Database :
OpenAIRE
Journal :
Networks, Networks, Wiley, 1996, 27, pp.175-181
Accession number :
edsair.doi.dedup.....914d03f5ece97b057db2b6f76b3a7735

Tools

Authors Abstract Subjects Details