Parameterized Aspects of Triangle Enumeration
Parameterized Aspects of Triangle Enumeration
复制标题
三角形枚举的参数化方面
DOI：
10.1007/978-3-662-55751-8_9
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
R. Niedermeier
中科院分区：
文献类型：
--
作者：
M. Bentert;T. Fluschnik;A. Nichterlein;R. Niedermeier
列出无向图中所有三角形的任务是具有许多应用的基本图基元。它在时间立方中是平凡可解的。它已经看到了大量对这两个理论方面做出贡献的工作（例如，运行时间的上下限、适应新的计算模型）以及实际方面（例如，针对大型图调整的算法）。基于最坏情况下的运行时间是三次的事实，我们对三角枚举进行了系统的参数化复杂性研究。我们既提供了积极的结果（新的枚举核化，“次立方”参数化求解算法），以及负面的结果（推定无用的“更快”的参数化算法的某些参数，如图直径）。为此，我们引入新的和扩展以前的概念。
The task of listing all triangles in an undirected graph is a fundamental graph primitive with numerous applications. It is trivially solvable in time cubic in the number of vertices. It has seen a significant body of work contributing to both theoretical aspects (e.g., lower and upper bounds on running time, adaption to new computational models) as well as practical aspects (e.g. algorithms tuned for large graphs). Motivated by the fact that the worst-case running time is cubic, we perform a systematic parameterized complexity study of triangle enumeration. We provide both positive results (new enumerative kernelizations, “subcubic” parameterized solving algorithms) as well as negative results (presumable uselessness in terms of “faster” parameterized algorithms of certain parameters such as graph diameter). To this end, we introduce new and extend previous concepts.
登录
查看更多内容
在线社交网络系统的测量和分析
DOI：
--
发表时间：
2014
期刊：
Encyclopedia of Social Network Analysis and Mining
影响因子：
--
作者：
Emilio Ferrara
通讯作者：
Emilio Ferrara
稀疏图中半径和直径的近似和固定参数次二次算法
DOI：
10.1137/1.9781611974331.ch28
发表时间：
2016
期刊：
2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)
影响因子：
--
作者：
Amir Abboud;Virginia Vassilevska Williams;Joshua R. Wang
通讯作者：
Joshua R. Wang
DOI：
10.1007/10692760_1
发表时间：
1998-06
期刊：
--
影响因子：
--
作者：
B. Courcelle;J. Makowsky;Udi Rotics
通讯作者：
B. Courcelle;J. Makowsky;Udi Rotics
DOI：
10.1007/978-3-319-94418-0_19
发表时间：
2017-10
期刊：
--
影响因子：
--
作者：
T. Fluschnik;G. B. Mertzios;A. Nichterlein
通讯作者：
T. Fluschnik;G. B. Mertzios;A. Nichterlein
细粒度的匹配算法设计
DOI：
--
发表时间：
2016
期刊：
arXiv.org
影响因子：
--
作者：
G. B. Mertzios;A. Nichterlein;R. Niedermeier
通讯作者：
R. Niedermeier