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.
No takes yet. Share an insight, caveat, or question.
Papadimitriou et al. (1982) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: