Paper Info
Title
Maximum Independent Set for Intervals by Divide-Prune-and-Conquer
Abstract
As an easy example of divide, prune, and conquer, we give an output-sensitive O(n log k)-time algorithm to compute, for n intervals, a maximum independent set of size k.
Year
Venue
Keywords
2005
CCCG
maximum independent set
Field
DocType
Citations 
Discrete mathematics,Combinatorics,Computer science,Independent set
Conference
0
PageRank 
References 
Authors
0.34
4
1
Name
Order
Citations
PageRank
Jack Snoeyink12842231.68