We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The stripping process can be slow: Part I.
- Authors
Gao, Pu; Molloy, Michael
- Abstract
Abstract: Given an integer k, we consider the parallel k‐stripping process applied to a hypergraph H: removing all vertices with degree less than k in each iteration until reaching the k‐core of H. Take H as H r ( n , m ): a random r‐uniform hypergraph on n vertices and m hyperedges with the uniform distribution. Fixing k , r ≥ 2 with ( k , r ) ≠ ( 2 , 2 ), it has previously been proved that there is a constant c r , k such that for all m = cn with constant c ≠ c r , k, with high probability, the parallel k‐stripping process takes O ( log n ) iterations. In this paper, we investigate the critical case when c = c r , k + o ( 1 ). We show that the number of iterations that the process takes can go up to some power of n, as long as c approaches c r , k sufficiently fast. A second result we show involves the depth of a non‐k‐core vertex v: the minimum number of steps required to delete v from H r ( n , m ) where in each step one vertex with degree less than k is removed. We will prove lower and upper bounds on the maximum depth over all non‐k‐core vertices.
- Subjects
PARALLEL algorithms; HYPERGRAPHS; PATHS &; cycles in graph theory; UNIFORM distribution (Probability theory); GRAPH theory
- Publication
Random Structures & Algorithms, 2018, Vol 53, Issue 1, p76
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20760