On NC algorithms for problems on bounded rank-width graphs

摘要

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.