1-1hit |
Olivier GOLDSCHMIDT Alexan TAKVORIAN
We present an O(nN) time and O(n2) space algorithm for finding a maximum weight independent set of a circle (or overlap) graph of n chords (or intervals) on N endpoints, based on an alternative definition of such graphs. The results improve on the best previously known algorithms for this case.