Clique transversal and clique independence on comparability graphs

被引：42
|
作者：
Balachandran, V
Nagavamsi, P
Rangan, CP
机构：
[1] Indian Institute of Technology
[2] Theor. Computer Science Laboratory, Dept. of Comp. Sci. and Engineering, Indian Institute of Technology
来源：
INFORMATION PROCESSING LETTERS | 1996年 / 58卷 / 04期
关键词：
algorithms; clique transversal; clique independence;
D O I：
10.1016/0020-0190(96)00054-3
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We present O(m root n + M(n)) algorithms for finding the clique transversal number and the clique independence number for a comparability graph of n nodes, where M(n) is the complexity of multiplying two n x n matrices.
引用
收藏
页码：181 / 184
页数：4
相关论文
共 50 条
  • [41] Algorithms for clique-independent sets on subclasses of circular-arc graphs
    Duran, Guillermo
    Lin, Min Chih
    Mera, Sergio
    Szwarcfiter, Jayme Luiz
    DISCRETE APPLIED MATHEMATICS, 2006, 154 (13) : 1783 - 1790
  • [42] Treewidth versus clique number. II. Tree-independence number
    Dallard, Clement
    Milanic, Martin
    Storgel, Kenny
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2024, 164 : 404 - 442
  • [43] Graph reconstruction in the congested clique
    Montealegre, R.
    Perez-Salazar, S.
    Rapaport, I
    Todinca, I
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2020, 113 (113) : 1 - 17
  • [44] REVISITING DECOMPOSITION BY CLIQUE SEPARATORS
    Coudert, David
    Ducoffe, Guillaume
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2018, 32 (01) : 682 - 694
  • [45] On maximum ratio clique relaxations
    Blokhin, Yehor
    Butenko, Sergiy
    Momcilovic, Petar
    Prokopyev, Oleg A.
    NETWORKS, 2022, 80 (04) : 440 - 465
  • [46] A NOTE ON MAXIMUM INDEPENDENT SETS AND MINIMUM CLIQUE PARTITIONS IN UNIT DISK GRAPHS AND PENNY GRAPHS: COMPLEXITY AND APPROXIMATION
    Cerioli, Marcia R.
    Faria, Luerbio
    Ferreira, Talita O.
    Protti, Fabio
    RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS, 2011, 45 (03): : 331 - 346
  • [47] Efficient algorithms for clique problems
    Vassilevska, Virginia
    INFORMATION PROCESSING LETTERS, 2009, 109 (04) : 254 - 257
  • [48] Clique Is Hard on Average for Regular Resolution
    Atserias, Albert
    Bonacina, Ilario
    de Rezende, Susanna F.
    Lauria, Massimo
    Nordstrom, Jakob
    Razborov, Alexander
    STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 866 - 877
  • [49] MINIMUM AVERAGE DISTANCE CLIQUE TREES
    Xu, Shou-Jun
    Gysel, Rob
    Gusfield, Dan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (03) : 1706 - 1734
  • [50] EFFICIENT ALGORITHMS FOR THE MAXIMUM WEIGHT CLIQUE AND MAXIMUM WEIGHT INDEPENDENT SET PROBLEMS ON PERMUTATION GRAPHS
    CHANG, MS
    WANG, FH
    INFORMATION PROCESSING LETTERS, 1992, 43 (06) : 293 - 295
12345