A New Simple Algorithm for the Maximum-Weight Independent Set Problem on Circle Graphs

摘要

The problem of finding an independent set of maximum weight for the chord model of a circle graph is solved in O(l) time and O(n) space, where n is the number of vertices and l is the total chord length of the circle graph. The best previous algorithm required O(dn) time and space, where d is the maximum number of intervals crossing any position on the line in the interval model of the graph. The algorithm is practical, requires only simple data structures to be implemented within the stated time and space bounds, and has small hidden constants.