An output sensitive algorithm for computing a maximum independent set of a circle graph

被引：5

作者：

Nash, Nicholas ^{[1
]}

Gregg, David ^{[1
]}

机构：

[1] Trinity Coll Dublin, Dept Comp Sci, Dublin, Ireland

来源：

INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 16期

关键词：

Design of algorithms; Graph algorithms; Circle graph; Maximum independent set; Maximum stable set;

D O I：

10.1016/j.ipl.2010.05.016

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present an output sensitive algorithm for computing a maximum independent set of an unweighted circle graph. Our algorithm requires O(n min{d,alpha}) time at worst, for an n vertex circle graph where a is the independence number of the circle graph and d is its density. Previous algorithms for this problem required Theta(nd) time at worst. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：630 / 634

页数：5

共 11 条

[1]

APOSTOLICO A, 1993, DISCRETE APPL MATH, V41, P179, DOI 10.1016/0166-218X(93)90038-P

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

APOSTOLICO, A ;

ATALLAH, MJ ;

HAMBRUSCH, SE .

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

[3]

ASANO T, 1991, IEICE TRANS COMMUN, V74, P681

[4]

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

[5]

GOLDSCHMIDT O, 1994, IEICE T FUND ELECTR, VE77A, P1672

[6]

Golumbic M.C., 2004, ANN DISCRETE MATH, V57

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

KEIL, JM .

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

[8]

NASH N, 2009, J EXP ALGORITHMICS, V13, P1

[9] FINDING A MAXIMUM PLANAR SUBSET OF A SET OF NETS IN A CHANNEL [J].

SUPOWIT, KJ .

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS, 1987, 6 (01) :93-94

[10]

TISKIN A, 2009, ABS07073619 CORR

← 1 2 →