The complexity of restricted spanning tree problems

Publisher Website
Google Scholar
Abstract
The complexity of the foUowmg class of problems Is investigated: Given a distance matrix, fred the shortest spanning tree that is isomorphic to a given prototype. Several classical combinatorial problems, both easy and hard, fall into this category for an appropriate choice of the family of prototypes, for example, taking the family to be the set of all paths gives the traveling salesman problem or taking the family to be the set of all 2-stars gives the weighted matching problem It is shown that the complexity of these problems depends explicitly on the rate of growth of a sLmple parameter of the family of prototypes. Categories and Subject Descriptors. F.I.3 (Computation by Abstract Devices): Complexity Classes-- reduclbihty and completeness; G.2 2 (Discrete Mathematics): Graph Theory--network problems; trees General Terms. Algorithms, Theory Additional Keywords and Phrases: Spanning tree, NP-complete, polynomial algorithm, matching
Keywords

This publication has 7 references indexed in Scilit: