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

作     者：Taki, M Hatakenaka, H Kashiwabara, T 

作者机构：Nara Natl Coll Technol Dept Informat Engn Yamatokohriyama 6391080 Japan Osaka Univ Dept Informat & Comp Sci Toyonaka Osaka 5608531 Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (电子信息通信学会汇刊：电子学、通信及计算机科学基础)

年 卷 期：1999年第E82A卷第8期

页      面：1636-1640页

核心收录：

学科分类：0808[工学-电气工程] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：circle graph independent set generation algorithm intersection graph interval graph overlap graph spider graph circular-arc overlap graph 

摘      要：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.