1-1hit |
Masakuni TAKI Hirotaka HATAKENAKA Toshinobu KASHIWABARA
In this paper we propose an algorithm for generating maximum weight independent sets in a circle graph, that is, for putting out all maximum weight independent sets one by one without duplication. The time complexity is O(n3 + β ), where n is the number of vertices, β output size, i. e. , the sum of the cardinalities of the output sets. It is shown that the same approach can be applied for spider graphs and for circular-arc overlap graphs.