On NC algorithms for problems on bounded rank-width graphs

Publications

On NC algorithms for problems on bounded rank-width graphs

Author : Dr Murali Krishna Enduri

Year : 2018

Publisher : Elsevier B.V.

Source Title : Information Processing Letters

Document Type : Article

Link

DOI

https://doi.org/10.1016/j.ipl.2018.07.007

Web

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85050452509&origin=inward

Abstract

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.