For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Algorithms for Generating Maximum Weight Independent Sets in Circle Graphs, Circular-Arc Overlap Graphs, and Spider Graphs
Masakuni TAKI Hirotaka HATAKENAKA Toshinobu KASHIWABARA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1999/08/25
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
circle graph, independent set, generation algorithm, intersection graph, interval graph, overlap graph, spider graph, circular-arc overlap graph,
Full Text: PDF(421.1KB)>>
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.