Premium
Maximum independent set for intervals by divide and conquer with pruning
Author(s) -
Snoeyink Jack
Publication year - 2007
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20150
Subject(s) - divide and conquer algorithms , disjoint sets , pruning , set (abstract data type) , combinatorics , mathematics , algorithm , computer science , discrete mathematics , agronomy , biology , programming language
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