On NC algorithms for problems on bounded rank-width graphs

被引：0
|
作者：
Das, Bireswar [1 ]
Dasgupta, Anirban [1 ]
Enduri, Murali Krishna [1 ]
Reddy, I. Vinod [1 ]
机构：
[1] Indian Inst Technol Gandhinagar, Ahmadabad, Gujarat, India
来源：
INFORMATION PROCESSING LETTERS | 2018年 / 139卷
关键词：
Rank-width; NP-complete; Parallel algorithms; Clique-width; CLIQUE-WIDTH;
D O I：
10.1016/j.ipl.2018.07.007
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In this paper, we show that for a fixed k, there is an NC algorithm that separates the graphs of rank-width at most k from those with rank-width at least 3k + 1. (C) 2018 Elsevier B.V. All rights reserved.
引用
收藏
页码：64 / 67
页数：4
相关论文
共 50 条
  • [31] Obstructions for linear rank-width at most 1
    Adler, Isolde
    Farley, Arthur M.
    Proskurowski, Andrzej
    DISCRETE APPLIED MATHEMATICS, 2014, 168 : 3 - 13
  • [32] The Rank-Width of the Square Grid
    Jelinek, Vit
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2008, 5344 : 230 - 239
  • [33] The rank-width of the square grid
    Jelinek, Vit
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (07) : 841 - 850
  • [34] TREE PIVOT-MINORS AND LINEAR RANK-WIDTH
    Dabrowski, Konrad K.
    Dross, Francois
    Jeong, Jisu
    Kante, Mamadou M.
    Kwon, O-joung
    Oum, Sang-il
    Paulusma, Daniel
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2021, 35 (04) : 2922 - 2945
  • [35] TREE PIVOT-MINORS AND LINEAR RANK-WIDTH
    Dabrowski, K. K.
    Dross, F.
    Jeong, J.
    Kante, M. M.
    Kwon, O-J.
    Oum, S-I.
    Paulusma, D.
    ACTA MATHEMATICA UNIVERSITATIS COMENIANAE, 2019, 88 (03): : 577 - 583
  • [36] Linear rank-width of distance-hereditary graphs II. Vertex-minor obstructions
    Kante, Mamadou Moustapha
    Kwon, O-joung
    EUROPEAN JOURNAL OF COMBINATORICS, 2018, 74 : 110 - 139
  • [37] MSOL partitioning problems on graphs of bounded treewidth and clique-width
    Rao, Michael
    THEORETICAL COMPUTER SCIENCE, 2007, 377 (1-3) : 260 - 267
  • [38] Linear Rank-Width of Distance-Hereditary Graphs I. A Polynomial-Time Algorithm
    Isolde Adler
    Mamadou Moustapha Kanté
    O-joung Kwon
    Algorithmica, 2017, 78 : 342 - 377
  • [39] Recent developments on graphs of bounded clique-width
    Kaminski, Marcin
    Lozin, Vadim V.
    Milanic, Martin
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (12) : 2747 - 2761
  • [40] Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
    Coudert, David
    Ducoffe, Guillaume
    Popa, Alexandru
    ACM TRANSACTIONS ON ALGORITHMS, 2019, 15 (03)
12345