Premium
A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone
Author(s) -
Manacher Glenn K.,
Mankus Terrance A.
Publication year - 2002
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.10014
Subject(s) - set (abstract data type) , simple (philosophy) , algorithm , mathematics , independent set , interval (graph theory) , simple algorithm , time complexity , combinatorics , mathematical optimization , computer science , graph , philosophy , physics , epistemology , thermodynamics , programming language
We exhibit an algorithm for finding a maximum independent set (MIS) for n presorted, unweighted circular arcs in time 0( n ). Unlike previous algorithms, this is achieved by means of trivial postprocessing of the output of a straightforward algorithm for finding an MIS for a set of unweighted intervals. © 2002 Wiley Periodicals, Inc.