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 条
  • [21] On low rank-width colorings
    Kwon, O-joung
    Pilipczuk, Michal
    Siebertz, Sebastian
    EUROPEAN JOURNAL OF COMBINATORICS, 2020, 83
  • [22] Rank-width is less than or equal to branch-width
    Oum, Sang-il
    JOURNAL OF GRAPH THEORY, 2008, 57 (03) : 239 - 244
  • [23] On Low Rank-Width Colorings
    Kwon, O-joung
    Pilipczuk, Michal
    Siebertz, Sebastian
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2017), 2017, 10520 : 372 - 385
  • [24] Rank-width and well-quasi-ordering
    Oum, Sang-Il
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2008, 22 (02) : 666 - 682
  • [25] Isomorphism Testing for Graphs of Bounded Rank Width
    Grohe, Martin
    Schweitzer, Pascal
    2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2015, : 1010 - 1029
  • [26] Canonisation and Definability for Graphs of Bounded Rank Width
    Grohe, Martin
    Neuen, Daniel
    2019 34TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2019,
  • [27] Graphs of small rank-width are pivot-minors of graphs of small tree-width
    Kwon, O-joung
    Oum, Sang-il
    DISCRETE APPLIED MATHEMATICS, 2014, 168 : 108 - 118
  • [28] Directed Rank-Width and Displit Decomposition
    Kante, Mamadou Moustapha
    Rao, Michael
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2010, 5911 : 214 - +
  • [29] Computing rank-width exactly
    Oum, Sang-il
    INFORMATION PROCESSING LETTERS, 2009, 109 (13) : 745 - 748
  • [30] Linear Rank-Width of Distance-Hereditary Graphs I. A Polynomial-Time Algorithm
    Adler, Isolde
    Kante, Mamadou Moustapha
    Kwon, O-Joung
    ALGORITHMICA, 2017, 78 (01) : 342 - 377
12345