Algorithms for Generating Maximum Weight independent Sets in Circle Graphs, Circular-Arc Overlap Graphs, and Spider Graphs

摘要

In this paper we propose an algorithm for gen- erating maximum weight independent sets in a circle graph, that one without duplication. The time complexity is O(n~3 + β), 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.