Maximum weight independent set in trees
type: Item
instance of: scholarly article
title: Maximum weight independent set in trees
zbMATH Open document ID: 0642.68128
DOI: 10.1007/BF01934182
published in: BIT
publication date: 1987-01-01T00:00:00Z
review text: Computing a maximum independent set, weighted or unweighted, is NP-hard for general as well as planar graphs. However, polynomial time algorithms do exist for solving this problem on special classes of graphs. In this paper we present an efficient algorithm for computing a maximum wehe extent to which, given two categories A and B and a functor K from A to B, the functor K can be used to gain information on the objects of B via approximations by K-images of objects in A. In the shape geometric theory of Borsuk the category A is the homotopy category of polyhedra, B the homotopy category of compact metric spaces and K is the inclusion. In this note the authors set out to interpret the simpler parts of categorical shape theory in terms of the basic theoretical problems of pattern recognition, namely the classification and recognition problems. In this interpretation A is a category of archetypes or models whilst B is a category of objects of interest, K being a ``comparison functor''. The consequences of such a basic recognition system are explored and certain problems that naturally occur in this theory are discussed with reference to pattern recognition. The authors intend to write further notes of this form in the expectation that the ideas, suitably modified, may prove to be of use within the theory of pattern recognition. The authors would like to point out that reference 2 is to be published under the title ``Shape theory: Categorical approximation methods'' by Ellis Horwood Ltd. (expected publication date Spring 1989).
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4047156
zbMATH Keywords: maximum wehe extent to which, given two categories A and B and a functor K from A to B, the functor K can be used to gain information on the objects of B via approximations by K-images of objects in A. In the shape geometric theory
zbMATH Keywords: categorical shape theory
zbMATH Keywords: pattern recognition
zbMATH Keywords: classification
zbMATH Keywords: comparison functor
author: Shaunak R. Pawagi
reviewed by: Timothy Porter
MaRDI profile type: Publication
cites work: Solving NP-hard problems in 'almost trees': vertex cover
cites work: Q4198056
cites work: Efficient bounds for the stable set, vertex cover and set packing problems
cites work: An Algorithmic Approach to Network Location Problems. I: Thep-Centers
cites work: Vertex packings: Structural properties and algorithms
cites work: Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
cites work: Depth-first search and the vertex cover problem
Recommended article: The structure and maximum number of maximum independent sets in trees
Recommended article: Q3565954
Recommended article: On maximal independent sets of nodes in trees
Recommended article: The Number of Maximal Independent Sets in a Tree
Recommended article: Q3004826
Recommended article: Q5500115
Recommended article: An optimal time algorithm for finding a maximum weight independent set in a tree
Recommended article: Trees with a unique maximum independent set and their linear properties
Recommended article: Trees with extremal numbers of maximal independent sets including the set of leaves
Recommended article: Trees with a given number of leaves and the maximal number of maximum independent sets
description: scientific article; zbMATH DE number 4047156