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

Masakuni TAKI  Hirotaka HATAKENAKA  Toshinobu KASHIWABARA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.8   pp.1636-1640
Publication Date: 1999/08/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 
circle graph,  independent set,  generation algorithm,  intersection graph,  interval graph,  overlap graph,  spider graph,  circular-arc overlap graph,  

Full Text: PDF(421.1KB)>>
Buy this Article




Summary: 
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.