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 条
  • [1] Approximability of Clique Transversal in Perfect Graphs
    Fiorini, Samuel
    Krithika, R.
    Narayanaswamy, N. S.
    Raman, Venkatesh
    ALGORITHMICA, 2018, 80 (08) : 2221 - 2239
  • [2] The clique-perfectness and clique-coloring of outer-planar graphs
    Liang, Zuosong
    Shan, Erfang
    Kang, Liying
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2019, 38 (03) : 794 - 807
  • [3] CLIQUE GRAPHS OF CHORDAL AND PATH GRAPHS
    SZWARCFITER, JL
    BORNSTEIN, CF
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (02) : 331 - 336
  • [4] Upper Clique Transversals in Graphs
    Milanic, Martin
    Uno, Yushi
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2023, 2023, 14093 : 432 - 446
  • [5] The clique-perfectness and clique-coloring of outer-planar graphs
    Zuosong Liang
    Erfang Shan
    Liying Kang
    Journal of Combinatorial Optimization, 2019, 38 : 794 - 807
  • [6] Faster recognition of clique-Helly and hereditary clique-Helly graphs
    Lin, Min Chih
    Szwarcfiter, Jayrne L.
    INFORMATION PROCESSING LETTERS, 2007, 103 (01) : 40 - 43
  • [7] The clique-transversal set problem in {claw, K4}-free planar graphs
    Liang, Zuosong
    Shan, Erfang
    Kang, Liying
    INFORMATION PROCESSING LETTERS, 2017, 118 : 64 - 68
  • [8] Upper bounds to the clique width of graphs
    Courcelle, B
    Olariu, S
    DISCRETE APPLIED MATHEMATICS, 2000, 101 (1-3) : 77 - 114
  • [9] Approximation Algorithms on k-Cycle Transversal and k-Clique Transversal
    Zhong-Zheng Tang
    Zhuo Diao
    Journal of the Operations Research Society of China, 2021, 9 : 883 - 892
  • [10] Algorithms for finding clique-transversals of graphs
    Duran, Guillermo
    Lin, Min Chih
    Mera, Sergio
    Szwarcfiter, Jayme L.
    ANNALS OF OPERATIONS RESEARCH, 2008, 157 (01) : 37 - 45
12345