A simple linear time algorithm for finding a maximum independent set of circular arcs using intervals alone | Zendy

Manacher Glenn K. | Zendy; Mankus Terrance A. | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

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.

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research