论文标题
有限元宽度图内的最佳直径计算
Optimal diameter computation within bounded clique-width graphs
论文作者
论文摘要
Coudert等。 （苏打18）证明，在强烈的指数时间假设下，对于任何$ε> 0 $，都没有$ {\ cal o}（2^{o（k）} n^{2-ε}）$ - 计算$ n $ n $ - vertex cubthe in Clique-k $ $ k $ k $ k $ k $ k $ k $ k $ k $ k的时间算法。我们提出了一种算法，该算法给出了$ n $ -vertex $ m $ - edge Graph $ g $和$ k $ -expression，以$ {\ cal o}（2^{{\ cal o}（k）}（k）}（n+m）^{1+o（1+o（1+o（1+o（1+o（1+o（1+o），计算所有偏心），则计算所有偏心率。可以修改它，以计算同一时间内的Wiener指数和$ G $的中位数。在途中，我们使用$ {\ cal o}（k \ log o}（k \ log^2 {n}）$每个顶点$ bits $ n $ k $ $ n $ -vertex $ m $ m $ m $ - g $的距离图，每个顶点$ littex $ bits $ bits $ {k（n+m）（k（n+m）\ log log log oft a $ nime offertex ussible ofttex $ nighttex $ nime-exply。这样做，我们匹配了Courcelle和Vanicat（DAM 2016）获得的标签尺寸，而我们在其计划中大大提高了对$ K $的依赖。作为推论，我们获得了$ {\ cal o}（kn^2 \ log {n}）$ - 用于计算$ n $ vertex clique-width的$ n $ vertex图表的time算法，最多$ k $。这部分回答了Kratsch和Nelles（STACS'20）的公开问题。
Coudert et al. (SODA'18) proved that under the Strong Exponential-Time Hypothesis, for any $ε>0$, there is no ${\cal O}(2^{o(k)}n^{2-ε})$-time algorithm for computing the diameter within the $n$-vertex cubic graphs of clique-width at most $k$. We present an algorithm which given an $n$-vertex $m$-edge graph $G$ and a $k$-expression, computes all the eccentricities in ${\cal O}(2^{{\cal O}(k)}(n+m)^{1+o(1)})$ time, thus matching their conditional lower bound. It can be modified in order to compute the Wiener index and the median set of $G$ within the same amount of time. On our way, we get a distance-labeling scheme for $n$-vertex $m$-edge graphs of clique-width at most $k$, using ${\cal O}(k\log^2{n})$ bits per vertex and constructible in ${\cal O}(k(n+m)\log{n})$ time from a given $k$-expression. Doing so, we match the label size obtained by Courcelle and Vanicat (DAM 2016), while we considerably improve the dependency on $k$ in their scheme. As a corollary, we get an ${\cal O}(kn^2\log{n})$-time algorithm for computing All-Pairs Shortest-Paths on $n$-vertex graphs of clique-width at most $k$. This partially answers an open question of Kratsch and Nelles (STACS'20).
