Maximum weight independent set in trees

DOI10.1007/BF01934182zbMath0642.68128MaRDI QIDQ1101239

Shaunak R. Pawagi

Publication date: 1987

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

classificationpattern recognitioncategorical shape theorycomparison functormaximum 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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

An optimal time algorithm for finding a maximum weight independent set in a tree

Cites Work

• Unnamed Item
• Efficient bounds for the stable set, vertex cover and set packing problems
• Solving NP-hard problems in 'almost trees': vertex cover
• Depth-first search and the vertex cover problem
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• Minimums-tCut of a Planar Undirected Network in $O(n\log ^2 (n))$ Time
• Vertex packings: Structural properties and algorithms

This page was built for publication: Maximum weight independent set in trees