%0 Generic %1 Kante2007Rankwidth %A Kante, Mamadou %D 2007 %K networks %T The rank-width of Directed Graphs %U http://arxiv.org/abs/0709.1433 %X lique-width is a complexity measure of directed as well as undirected graphs. Rank-width is an equivalent complexity measure for undirected graphs which has good algorithmic and structural properties. We compare several possible definitions of the rank-width of directed graphs. They turn out to be equivalent. We give for one of them an algebraic characterization in terms of graph operations, similar to the one that we have given for the rank-width of undirected graphs. We also adapt some recognition algorithms of Oum et al. in order to give a polynomial time approximation algorithm for the rank-width of directed graphs, and then, a polynomial time approximation algorithm for the clique-width of directed graphs.

@misc{Kante2007Rankwidth, abstract = {lique-width is a complexity measure of directed as well as undirected graphs. Rank-width is an equivalent complexity measure for undirected graphs which has good algorithmic and structural properties. We compare several possible definitions of the rank-width of directed graphs. They turn out to be equivalent. We give for one of them an algebraic characterization in terms of graph operations, similar to the one that we have given for the rank-width of undirected graphs. We also adapt some recognition algorithms of Oum et al. in order to give a polynomial time approximation algorithm for the rank-width of directed graphs, and then, a polynomial time approximation algorithm for the clique-width of directed graphs.}, added-at = {2009-09-24T14:55:30.000+0200}, archiveprefix = {arXiv}, author = {Kante, Mamadou}, biburl = {https://www.bibsonomy.org/bibtex/22cb6452c22179fa15ff4d44420a2bdab/andreacapocci}, citeulike-article-id = {1653572}, citeulike-linkout-0 = {http://arxiv.org/abs/0709.1433}, citeulike-linkout-1 = {http://arxiv.org/pdf/0709.1433}, eprint = {0709.1433}, interhash = {53c1fc7263907c13292110283c9f8b68}, intrahash = {2cb6452c22179fa15ff4d44420a2bdab}, keywords = {networks}, month = Sep, posted-at = {2007-09-14 01:30:40}, priority = {2}, timestamp = {2009-09-24T14:55:36.000+0200}, title = {The rank-width of Directed Graphs}, url = {http://arxiv.org/abs/0709.1433}, year = 2007 }