论文标题
计算最小fip数量的弱优势图
Computing Weak Dominance Drawings with Minimum Number of Fips
论文作者
论文摘要
一个弱的统治地图$ g $ g =（v，e）$的$γ$是$ d $二维图，因此，对于每个d（u）<d（v）$ d $ d $ d $ $γ$，有从顶点$ u $到$ g $ in $ g $ in $ g $ in $ g $ in $ g $ in $ g $中的有向路径。当每个尺寸$ d $ of〜$γ$的$ d（u）<d（v）$时，我们有一个\ emph {错误的隐含路径（fip）}，但是从$ u $到$ v $没有路径。将FIP的数量最小化是一个重要的理论和实用问题，即NP-HARD。我们表明，这是参数$ k $的FPT〜问题，其中$ k $是\ $ g $的\ emph {modular〜分解〜树的最大程度。也就是说，对于任何常数$ d $，我们会呈现一个$ o（nm+ndk^2（k！）^d）$ time算法来计算一个弱$ d $ d $ d $ d $ d的优势，绘制了dag $ g $的$γ$具有最小fips数量的dag $ g $。此结果的一个有趣的含义是，我们可以决定在时间$ O（NM+NK^2（k！）^3）$的时间$ O（nm+nk^2（k！）^3）$中，DAG是否具有主导地位〜$ 3 $（众所周知的NP完整问题）。
A weak dominance drawing $Γ$ of a DAG $G=(V,E)$, is a $d$-dimensional drawing such that there is a directed path from a vertex $u$ to a vertex $v$ in $G$ if $D(u) <D(v)$ for every dimension $D$ of $Γ$. We have a \emph{falsely implied path (fip)} when $D(u) < D(v)$ for every dimension $D$ of~$Γ$, but there is no path from $u$ to $v$. Minimizing the number of fips is an important theoretical and practical problem, which is NP-hard. We show that it is an FPT~problem for parameter $k$, where $k$ is the maximum degree of a vertex of the \emph{modular~decomposition~tree} of~$G$. Namely, for any constant $d$, we present an $O(nm+ndk^2(k!)^d)$ time algorithm to compute a weak $d$-dimensional dominance drawing $Γ$ of a DAG $G$ having the minimum number of fips. An interesting implication of this result is that we can decide if a DAG has dominance dimension~$3$ (a well-known NP-complete problem) in time $O(nm+nk^2(k!)^3)$.
