Approximating rank-width and clique-width quickly
Approximating rank-width and clique-width quickly
复制标题
快速近似排名宽度和派系宽度
DOI：
10.1145/1435375.1435385
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Sang
中科院分区：
文献类型：
--
作者：
Sang
等级宽度由OUM和Seymour [2006]定义，以研究集团宽度。 ）对于某些函数<i> f </i>或确认在时间<i> o </i>（| <i> v </i> |）中的等级宽度大于<i> k </i> <sup> 9 </sup> log | <i> v </i> |）对于输入图<i> g </i> =（<i> v </i>，<i> e </i </i >）和固定<i> k </i>。 SUP>） - 使用<i> f </i>的时间算法（<i> k </i>）= 3 <i> k </i> + 1，通过为上一个算法构造子例程；最小化OUM和Seymour使用的子管道功能。 <i> o </i>（| <i> v </i> | <sup> 3 </sup>） - 带有<i> f </i>的时算法（<i> k </i>） = 24 <i> k </i>，通过将图形降低到二进制矩阵来实现； >（| <i> v </i> | <sup> 3 </sup>） - 带有<i> f </i>（<i> k </i>）= 3 k <> k <> f </i>的时代算法/i> - 1通过组合以前引用的两篇论文的想法。
Rank-width was defined by Oum and Seymour [2006] to investigate clique-width. They constructed an algorithm that either outputs a rank-decomposition of width at most <i>f</i>(<i>k</i>) for some function <i>f</i> or confirms that rank-width is larger than <i>k</i> in time <i>O</i>(|<i>V</i>|<sup>9</sup>log |<i>V</i>|) for an input graph <i>G</i> = (<i>V</i>,<i>E</i>) and a fixed <i>k</i>. We develop three separate algorithms of this kind with faster running time. We construct an <i>O</i>(|<i>V</i>|<sup>4</sup>)-time algorithm with <i>f</i>(<i>k</i>) = 3<i>k</i> + 1 by constructing a subroutine for the previous algorithm; we avoid generic algorithms minimizing submodular functions used by Oum and Seymour. Another one is an <i>O</i>(|<i>V</i>|<sup>3</sup>)-time algorithm with <i>f</i>(<i>k</i>) = 24<i>k</i>, achieved by giving a reduction from graphs to binary matroids; then we use an approximation algorithm for matroid branch-width by Hliněný [2005]. Finally we construct an <i>O</i>(|<i>V</i>|<sup>3</sup>)-time algorithm with <i>f</i>(<i>k</i>) = 3<i>k</i> − 1 by combining the ideas of the two previously cited papers.