NEW CLIQUE AND INDEPENDENT SET ALGORITHMS FOR CIRCLE GRAPHS

被引：28

作者：

APOSTOLICO, A

ATALLAH, MJ

HAMBRUSCH, SE

机构：

[1] Department of Computer Sciences, Purdue University, West Lafayette

来源：

DISCRETE APPLIED MATHEMATICS | 1992年 / 36卷 / 01期

关键词：

D O I：

10.1016/0166-218X(92)90200-T

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Given the interval model of an n-vertex, e-edge circle graph G, it is shown how to find a clique of G of maximum size l (respectively, maximum weight) in O(n log n + min[e, nl log(2n/l)]) (respectively, O(n log n + min[n2,e log log n])) time. The best previous algorithms required, respectively, THETA(n2) and O(n2 + e log log n) time. An O(n log n + dn) time and space algorithm that finds an independent set of maximum weight for the interval model of G is also presented. Here d is the maximum number of intervals crossing any position of the line in the interval model of G. The best previous solution for this problem took time O(n3).

引用

页码：1 / 24

页数：24

共 20 条

[1]

Aggarwal A., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P497, DOI 10.1109/SFCS.1988.21966

[2]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[3] IMPROVING THE WORST-CASE PERFORMANCE OF THE HUNT-SZYMANSKI STRATEGY FOR THE LONGEST COMMON SUBSEQUENCE OF 2 STRINGS [J].