Fixed-parameter algorithms for DAG Partitioning
Fixed-parameter algorithms for DAG Partitioning
复制标题
DAG 分区的固定参数算法
DOI：
10.1016/j.dam.2016.12.002
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
O. Suchý
中科院分区：
文献类型：
--
作者：
R. van Bevern;R. Bredereck;M. Chopin;S. Hartung;F. Hüffner;A. Nichterlein;O. Suchý
Leskovec等人(2009)将寻找在网络上传播的短短语的原点形式化为DAG划分：给定n个顶点和m个弧上的弧加权有向无环图，删除总权至多为k的弧，使得每个产生的弱连接分量恰好包含一个下沉-一个没有传出弧的顶点。DAG划分是NP难的。给出了一种在O(2k⋅(n+m))时间内，即对固定k在线性时间内求解DAG划分的算法，并补充了线性时间可执行的数据约简规则。我们的实验表明，当k≤190和m大于等于107时，它们可以在5分钟内最优地解决模拟引文网络上的DAG划分问题。利用我们得到的最优解对Leskovec等人的S启发式算法的解质量进行了评价。我们证明了Leskovec等人的S启发式算法在树上是最优的，并且推广了这一结果，证明了如果给出了输入图的宽度-t树分解，则在2 O(T2)⋅n时间内是可解的.因此，我们改进了一个算法，并回答了Alamdari和Mehrabian(2012)的一个公开问题。我们通过精确算法的运行时间和数据约简的有效性的下界来补充我们的算法。
Finding the origin of short phrases propagating through the web has been formalized by Leskovec et al.(2009) as DAG Partitioning: given an arc-weighted directed acyclic graph on n vertices and m arcs, delete arcs with total weight at most k such that each resulting weakly-connected component contains exactly one sink—a vertex without outgoing arcs. DAG Partitioning is NP-hard. We show an algorithm to solve DAG Partitioning in O (2 k⋅(n+ m)) time, that is, in linear time for fixed k. We complement it with linear-time executable data reduction rules. Our experiments show that, in combination, they can optimally solve DAG Partitioning on simulated citation networks within five minutes for k≤ 190 and m being 10 7 and larger. We use our obtained optimal solutions to evaluate the solution quality of Leskovec et al.’s heuristic. We show that Leskovec et al.’s heuristic works optimally on trees and generalize this result by showing that DAG Partitioning is solvable in 2 O (t 2)⋅ n time if a width-t tree decomposition of the input graph is given. Thus, we improve an algorithm and answer an open question of Alamdari and Mehrabian (2012). We complement our algorithms by lower bounds on the running time of exact algorithms and on the effectivity of data reduction.
登录
查看更多内容
有根 k 叶分支问题的线性时间核化
DOI：
10.1016/j.dam.2015.04.028
发表时间：
2013
期刊：
Revue d'epidemiologie et de sante publique
影响因子：
--
作者：
Frank Kammer
通讯作者：
Frank Kammer
关于 DAG 分区问题
DOI：
10.1007/978-3-642-30541-2_2
发表时间：
2012
期刊：
EPL (Europhysics Letters)
影响因子：
--
作者：
Soroush Alamdari;Abbas Mehrabian
通讯作者：
Abbas Mehrabian
影响因子：
1.1
作者：
René van Bevern
通讯作者：
René van Bevern
DOI：
10.1007/978-3-642-28050-4_15
发表时间：
2011-09
期刊：
--
影响因子：
--
作者：
T. Hagerup
通讯作者：
T. Hagerup
（太阳）花的捷径：对数空间或线性时间中的内核
影响因子：
1.1
作者：
S. Fafianie;Stefan Kratsch
通讯作者：
Stefan Kratsch