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 条

[41] Algorithms for vertex-partitioning problems on graphs with fixed clique-width
Gerber, MU
Kobler, D
THEORETICAL COMPUTER SCIENCE, 2003, 299 (1-3) : 719 - 734
[42] Alliances in graphs of bounded clique-width
Kiyomi, Masashi
Otachi, Yota
DISCRETE APPLIED MATHEMATICS, 2017, 223 : 91 - 97
[43] Line graphs of bounded clique-width
Gurski, Frank
Wanke, Egon
DISCRETE MATHEMATICS, 2007, 307 (22) : 2734 - 2754
[44] On powers of graphs of bounded NLC-width (clique-width)
Suchana, Karol
Todinca, Ioan
DISCRETE APPLIED MATHEMATICS, 2007, 155 (14) : 1885 - 1893
[45] Constrained-Path Labellings on Graphs of Bounded Clique-Width
Courcelle, Bruno
Twigg, Andrew
THEORY OF COMPUTING SYSTEMS, 2010, 47 (02) : 531 - 567
[46] Polynomial algorithms for partitioning problems on graphs with fixed clique-width (Extended abstract)
Kobler, D
Rotics, U
PROCEEDINGS OF THE TWELFTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2001, : 468 - 476
[47] Critical properties of graphs of bounded clique-width
Lozin, Vadim V.
Milanic, Martin
DISCRETE MATHEMATICS, 2013, 313 (09) : 1035 - 1044
[48] The NLC-width and clique-width for powers of graphs of bounded tree-width
Gurski, Frank
Wanke, Egon
DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 583 - 595
[49] Bounded width problems and algebras
Benoit Larose
László Zádori
Algebra universalis, 2007, 56 : 439 - 466
[50] Bounded width problems and algebras
Larose, Benoit
Zadori, Laszlo
ALGEBRA UNIVERSALIS, 2007, 56 (3-4) : 439 - 466

← 1 2 3 4 5 →