Algorithms for generating maximum weight independent sets in circle graphs, circular-arc overlap graphs, and spider graphs

被引：0

作者：

Taki, M ^{[1
]}

Hatakenaka, H

Kashiwabara, T

机构：

[1] Nara Natl Coll Technol, Dept Informat Engn, Yamatokohriyama 6391080, Japan

[2] Osaka Univ, Dept Informat & Comp Sci, Toyonaka, Osaka 5608531, Japan

来源：

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 1999年 / E82A卷 / 08期

关键词：

circle graph; independent set; generation algorithm; intersection graph; interval graph; overlap graph; spider graph; circular-arc overlap graph;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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(n(3) + beta), where n is the number of vertices, beta 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 circuiar-arc overlap graphs.

引用

页码：1636 / 1640

页数：5