Maximum independent set for intervals by divide and conquer with pruning
Jack Scott Snoeyink · Networks · 2006
Abstract Suppose a given set of n intervals contains a maximum independent set of k disjoint intervals. This brief note demonstrates that “divide and conquer with pruning” produces an easy, output‐sensitive O(n log k)‐time algorithm to compute such a maximum independent set. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 49(2), 158–159 2007