Аннотация
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.
Пользователи данного ресурса
Пожалуйста,
войдите в систему, чтобы принять участие в дискуссии (добавить собственные рецензию, или комментарий)