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 条
  • [31] Bounding the Clique-Width of H-Free Chordal Graphs
    Brandstaedt, Andreas
    Dabrowski, Konrad K.
    Huang, Shenwei
    Paulusma, Daniel
    JOURNAL OF GRAPH THEORY, 2017, 86 (01) : 42 - 77
  • [32] Minimum weighted clique cover on claw-free perfect graphs
    Bonomo, Flavia
    Oriolo, Gianpaolo
    Snels, Claudia
    JOURNAL OF GRAPH THEORY, 2021, 96 (02) : 231 - 268
  • [33] Constrained-Path Labellings on Graphs of Bounded Clique-Width
    Bruno Courcelle
    Andrew Twigg
    Theory of Computing Systems, 2010, 47 : 531 - 567
  • [34] Optimal Centrality Computations Within Bounded Clique-Width Graphs
    Ducoffe, Guillaume
    ALGORITHMICA, 2022, 84 (11) : 3192 - 3222
  • [35] Solving Maximum Clique Problem in Stochastic Graphs Using Learning Automata
    Soleimani-Pouri, Mohammad
    Rezvanian, Alireza
    Meybodi, Mohammad Reza
    2012 FOURTH INTERNATIONAL CONFERENCE ON COMPUTATIONAL ASPECTS OF SOCIAL NETWORKS (CASON), 2012, : 115 - 119
  • [36] Computational Challenges with Cliques, Quasi-cliques and Clique Partitions in Graphs
    Pardalos, Panos M.
    Rebennack, Steffen
    EXPERIMENTAL ALGORITHMS, PROCEEDINGS, 2010, 6049 : 13 - 22
  • [37] A Weakly Robust PTAS for Minimum Clique Partition in Unit Disk Graphs
    Pirwani, Imran A.
    Salavatipour, Mohammad R.
    ALGORITHMICA, 2012, 62 (3-4) : 1050 - 1072
  • [38] Finding Maximum Clique in Stochastic Graphs Using Distributed Learning Automata
    Rezvanian, Alireza
    Meybodi, Mohammad Reza
    INTERNATIONAL JOURNAL OF UNCERTAINTY FUZZINESS AND KNOWLEDGE-BASED SYSTEMS, 2015, 23 (01) : 1 - 31
  • [39] Edge Clique Partition of K4-Free and Planar Graphs
    Fleischer, Rudolf
    Wu, Xiaotian
    COMPUTATIONAL GEOMETRY, GRAPHS AND APPLICATIONS, 2011, 7033 : 84 - 95
  • [40] THE MAXIMUM CLIQUE PROBLEM
    PARDALOS, PM
    XUE, J
    JOURNAL OF GLOBAL OPTIMIZATION, 1994, 4 (03) : 301 - 328
12345