Generalized threshold processes on graphs
Generalized threshold processes on graphs
复制标题
图上的广义阈值过程
DOI：
10.1016/j.tcs.2017.05.010
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
J.L. Szwarcfiter
中科院分区：
文献类型：
--
作者：
C.V.G.C. Lima;D. Rautenbach;U.S. Souza;J.L. Szwarcfiter
考虑图上的迭代不可逆过程。从给定图G的某个初始顶点集S开始，这个过程迭代地将G中S之外的所有顶点u添加到S，对于这些顶点u，当前集S与G中u的邻域NG（u）的交集属于为每个顶点u给定的NG（u）的子集的集合τ（u）。受离散凸性概念的启发，我们研究了相应的区间数，其中只执行一次迭代，以及船体数，其中迭代次数是无界的。函数τ的特殊选择允许在这个框架内包括几个研究得很好的图形过程和参数。我们的贡献包括非常有限的情况下，线性时间算法的树，和概率上限的硬度结果。
We consider an iterative irreversible process on graphs. Starting with some initial set S of vertices of a given graph G, this process iteratively adds to S all vertices u of G outside of S for which the intersection of the current set S with the neighborhood N G (u) of u in G belongs to a collection τ (u) of subsets of N G (u) given for each vertex u. Inspired by discrete convexity notions, we study the corresponding interval number, where only one iteration is executed, and the hull number, where the number of iterations is unbounded. Special choices of the function τ allow to include several well studied graph processes and parameters within this framework. Our contributions comprise hardness results for very restricted cases, linear time algorithms for trees, and a probabilistic upper bound.
登录
查看更多内容
影响因子：
0.8
作者：
V. Zverovich
通讯作者：
V. Zverovich
不可逆的 k 阈值过程：疾病和观点传播的图论阈值模型
DOI：
10.1016/j.dam.2008.09.012
发表时间：
2009
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Paul A. Dreyer;F. Roberts
通讯作者：
F. Roberts
影响因子：
1.1
作者：
J. Bermond;J. Bond;D. Peleg;S. Pérennes
通讯作者：
S. Pérennes
树木的最小奇邻域覆盖
DOI：
--
发表时间：
1989
期刊：
Great Lakes Computer Science Conference
影响因子：
--
作者：
R. Dawes
通讯作者：
R. Dawes
论图向量支配的近似性和精确算法及相关问题
影响因子：
1.1
作者：
F. Cicalese;Martin Milanič;U. Vaccaro
通讯作者：
U. Vaccaro