Directed NLC-width


          

刊名：Theoretical computer science
作者：Gurski, Frank（Univ Dusseldorf, Inst Comp Sci, D-40225 Dusseldorf, Germany）
Wanke, Egon（Univ Dusseldorf, Inst Comp Sci, D-40225 Dusseldorf, Germany）
Yilmaz, Eda（Univ Dusseldorf, Inst Comp Sci, D-40225 Dusseldorf, Germany）
刊号：738LB004
ISSN：0304-3975
出版年：2016
年卷期：2016, vol.616
页码：1-17
总页数：17
分类号：TP3
关键词：Directed NLC-width；Directed clique-width；Digraphs
参考中译：
语种：eng
文摘：In this paper we generalize the concept of NLC-width introduced by Wanke in [39] to directed graphs. We show bounds of this new width parameter for directed graphs and relationships between directed NLC-width and directed clique-width which was introduced by Courcelle and Olariu in [8]. We also compare the measures with their undirected versions of the underlying undirected graphs. Our results imply that computing the directed NLC-width of a directed graph is NP-hard. Further we consider the directed width of digraph classes. We show that the set of directed co-graphs equals the set of graphs of directed NLC-width 1, while the set of directed co-graphs is characterized, by excluding two digraphs, as a proper subset of the set of all graphs of directed clique-width 2, which is a remarkable difference to the undirected versions of the graphs.



©2016机械工业出版社（机械工业信息研究院） 京ICP备05055788号-35