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

共 13 条

[1] NEW CLIQUE AND INDEPENDENT SET ALGORITHMS FOR CIRCLE GRAPHS [J].

APOSTOLICO, A ;

ATALLAH, MJ ;

HAMBRUSCH, SE .

DISCRETE APPLIED MATHEMATICS, 1992, 36 (01) :1-24

[2]

Even S., 1971, THEORY MACHINES COMP, P71, DOI DOI 10.1016/B978-0-12-417750-5.50011-7

[3]

Gavril F, 1973, NETWORKS, V3, P261, DOI DOI 10.1002/NET.3230030305

[4]

Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs

[5] THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE [J].

JOHNSON, DS .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1985, 6 (03) :434-451

[6] POLYNOMIAL-TIME ALGORITHMS ON CIRCULAR-ARC OVERLAP GRAPHS [J].

KASHIWABARA, T ;

MASUDA, S ;

NAKAJIMA, K .

NETWORKS, 1991, 21 (02) :195-203

[7] THE COMPLEXITY OF DOMINATION PROBLEMS IN CIRCLE GRAPHS [J].

KEIL, JM .

DISCRETE APPLIED MATHEMATICS, 1993, 42 (01) :51-63

[8]

KOEBE M, 1990, TOPICS COMBINATORICS, P435

[9] FAST ALGORITHMS FOR GENERATING ALL MAXIMAL INDEPENDENT SETS OF INTERVAL, CIRCULAR-ARC AND CHORDAL GRAPHS [J].

LEUNG, JYT .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1984, 5 (01) :22-35

[10]

Liang Y. D., 1991, 1991 Symposium on Applied Computing (Cat. No.91TH0355-8), P465, DOI 10.1109/SOAC.1991.143921

← 1 2 →