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
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom