Preprints---Subject to change

2016


• Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk
  Colin Cooper, Alan M. Frieze. SIAM J. Discrete Math. 30(1): 166-205 (2016)
• On the length of a random minimum spanning tree
  C. Cooper, A. Frieze, N. Ince, S. Janson, J. Spencer, Combinatorics, Probability and Computing 25(1): 89-107 (2016)
• Discordant voting processes on finite graphs
  C. Cooper, M. Dyer, A, Frieze, N. Rivera, ICALP 2016, 144:1--144:12.
• The Linear Voting Model
  C. Cooper, N. Rivera, ICALP 2016, 145:1--145:13.
• N. Rivera. The coalescing-branching random walk on expanders and the dual epidemic process
  C. Cooper, T. Radzik,PODC 2016, 461--467, (2016)
  
  
  2015
  Long paths in random Apollonian networks
  C. Cooper, A. Frieze. Internet Mathematics 11(4-5): 308-318, (2015).
• P. Berenbrink, C. Cooper, T. Friedzetky, T. Friedrich, T. Sauerwald. Randomized diffusion for indivisible loads. J. Comput. Syst. Sci. 81(1): 159-185 (2015)
• P. Berenbrink, C. Cooper, T. Friedzetky. Random walks which prefer unvisited edges. Random Struct. Algorithms 46(1): 36-54 (2015)
• C. Cooper, T. Radzik, N. Rivera, T.Shiraga. Coalescing walks on rotor-router systems. Sirocco 2015: 444-458.
• M. Abdullah, C. Cooper, M. Draief. Speeding Up Cover Time of Sparse Graphs Using Local Knowledge. IWOCA 2015: 1-12
• F. Gao, K. Musial, C. Cooper, S. Tsoka. Link prediction methods and network metrics. Scientific Programming 2015.
• C. Cooper, A. Lamani, G. Vigiletta, M. Yamashita, Y. Yamauchi. Constructing self-stabilizing oscillators in population protocols. SSS 2015: 187-200.
• C. Cooper, R. Elsaesser, T. Radzik, N. Rivera, T.Shiraga. Fast consensus for voting on general expander graphs. DISC 2015 (Symposium on Distributed Computing): 248-262.
  
  
  2014
  
• A note on the vacant set of random walks on the hypercube and other regular graphs of high degree
  C. Cooper, A. Frieze. Moscow J. Combinatorics and Number Theory 4(4): 21-44 (2014)
• C. Cooper, A. Frieze, P. Pralat. Some Typical Properties of the Spatial Preferred Attachment Model. Internet Mathematics 10(1-2): 116-136 (2014)
• C. Cooper, T. Radzik, Y. Siantos. A Fast Algorithm to Find All High-Degree Vertices in Graphs with a Power-Law Degree Sequence. Internet Mathematics 10(1-2): 137-161 (2014)
• C. Cooper, T. Radzik, Y. Siantos. Estimating network parameters using random walks. Social Netw. Analys. Mining 4(1) (2014)
• Cover time of a random graph with a degree sequence II: Allowing vertices of degree two
  Colin Cooper, Alan M. Frieze, Eyal Lubetzky, Random Struct. Algorithms 45(4): 627-674 (2014)
• The height of random k-trees and related branching processes.
  C. Cooper, A. Frieze, R. Uehara.
  
• Recommender systems based on random walks.
  C. Cooper, S. H. Lee, T. Radzik, Y. Siantos
• Analyzing Two Competing Epidemic Processes. The Power of Influential Nodes.
  C. Cooper, R. Elsaesser, A. Ogierman, T. Radzik (2014)
  
• The power of two choices in distributed voting
  C. Cooper, R. Elsaesser, and T. Radzik. ICALP 2014, 435-446.
• Random walks in recommender systems: exact computation and simulations.
  C. Cooper, S-H. Lee, T. Radzik, Y. Siantos. WWW (Companion Volume) 2014: 811-816
  
  
  2013
  
• Fast Low-Cost Estimation of Network Properties Using Random Walks.
  C. Cooper, T. Radzik, Y. Siantos. WAW 2013.
  
• Coalescing random walks and voting on graphs
  Colin Cooper, Robert Elsaesser, Hirotaka Ono, Tomasz Radzik. PODC 2012, and SIAM J. Discrete Maths (2013)
  
• Random walks which prefer unvisited edges. Exploring high girth even degree expanders in linear time
  Petra Berenbrink, Colin Cooper, Tom Friedetzky. PODC 2012 and Random Structures and Algorithms.
  
• Viral processes by random walks on random regular graphs
  M. Abdullah, C. Cooper, M. Draief. Annals of Applied Probability (2013) and RANDOM 2011
  
• Component structure of the vacant set induced by a random walk on a random graph
  C. Cooper, A. Frieze. Random Structures and Algorithms (2013) and SODA 2011
  
  2012
  
• Stationary distribution and cover time of random walks on random digraphs.
  C. Cooper, A. Frieze. JCT(B) (2012). Earlier version in RANDOM 2007
  
• Some Typical Properties of the Spatial Preferred Attachment Model
  C. Cooper, A. Frieze, P. Pralat. WAW 2012
  
• A fast algorithm to find all high degree vertices in graphs with a power law degree sequence
  C. Cooper, T. Radzik, Y. Siantos. WAW 2012.
  
• Cover time of a random graph with given degree sequence
  M. Abdullah, C. Cooper, A. Frieze. Discrete Mathematics (2012).
  
• Speeding up random walks by choosing unvisited edges or vertices.
  P. Berenbrink, C. Cooper and T. Friedetzky. Experimental results on network exploration. 2012
  
  2011
  
• Random walks, interacting particles, dynamic networks: Randomness can be helpful.
  C. Cooper. SIROCCO 2011 (Invited survey paper)
  
• The cover times of random walks on hypergraphs
  C. Cooper, A. Frieze, T. Radzik. SIROCCO 2011
  
• Component structure of the vacant set induced by a random walk on a random graph
  C. Cooper, A. Frieze SODA 2011 and Random Structures and Algorithms. (2013)
  
• Networks of random cycles
  C. Cooper, M. Dyer, A. Handley. SODA 2011
  
• Randomized Diffusion for Indivisible Loads
  P. Berenbrink, C. Cooper,T. Friedetzky, T. Friedrich, T. Sauerwald. SODA 2011
  
• Scale-free graphs of increasing degree
  C. Cooper, P. Pralat. Random Structures and Algorithms. (2011)
  
• On the Imitation Strategy for Games on Graphs
  C. Cooper, M. E. Dyer, V. Mohanaraj: CoRR abs/1102.3879: (2011)
  
  2010
  
• Speeding up random walks with neighbourhood exploration
  P. Berenbrink, C. Cooper, R. Elsaesser, T. Radzik, T. Sauerwald. SODA 2010
  
• Scale free properties of random k-trees
  C. Cooper, R. Uehara. Mathematics in Computer Science (2010)
  
• Chains-into-Bins Processes
  T. Batu, P. Berenbrink, C. Cooper. IWOCA 2010
  
• The Cover Time of Cartesian Product Graphs
  M. Abdullah, C. Cooper, T. Radzik. IWOCA 2010
  
• Random walks with look-ahead in scale free random graphs
  C. Cooper, A. Frieze. SIAM J. Discrete Math. (2010)
  
• Hamilton cycles in fixed degree sequence random graphs
  C. Cooper, A. Frieze, M. Krivelevich. SIAM J Discrete Maths (2010)
  
  2009
  
• An efficient sparse regularity concept
  A. Coja-Oghlan, C. Cooper, A. Frieze. SODA 2009, SIAM J Discrete Maths.
  
• Multiple random walks and interacting particle systems.
  C. Cooper, A. Frieze, T. Radzik. ICALP 2009.
  
• Multiple random walks in random regular graphs
  SIAM J Discrete Maths (2009). C. Cooper, A. Frieze, T. Radzik
  
• The cover time of random geometric graphs
  C. Cooper, A. Frieze. SODA 2009. Random Structures and Algorithms (2010)
  
• An exact analysis of the Cockayne-Goodman-Hedetniemi algorithm for a class of random tree processes
  C. Cooper, M. Zito. Discrete Applied Mathematics (2009)
  
• Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies
  C. Cooper, D. Ilcinkas, R. Klasing. A. Kosowski. ICALP 2009. Distributed Computing (2011)
  
• The Flip Markov Chain and a Randomising P2P Protocol
  C. Cooper, M. Dyer, A. Handley. PODC 2009.
  
• Martingales on trees and the empire chromatic number of random trees
  C. Cooper, A. McGrae, M. Zito. FCT 2009.
  
  
  2008
  
• Locating and repairing faults in a network with mobile agents
  C. Cooper, R. Klasing, T. Radzik. Theoretical Computer Science (SIROCCO'08)
  
• Random walks in random graphs
  C. Cooper, A. Frieze. Nano-Net 2008.
  
• The cover time of the giant component of G(n,p).
  C. Cooper, A. Frieze.  Random Structures and Algorithms 2008
  
• A spatial web graph model with local influence regions
  W. Aiello, A. Bonato, C. Cooper, J. Janssen, P. Pralat. Internet Mathematics (2008), WAW 2007.
  
  2007
  
• Energy efficient randomized communication in unknown adhoc networks
  P. Berenbrink, C. Cooper, Z. Hu.  SPAA07
  
• Realistic synthetic data for testing association rule mining algorithms for market basket databases. 
  C. Cooper, M. Zito.   PKDD 2007
  Go to Synthetic Data Generator CoZi to download market basket data.   (CoZi generator available here)
  
• Realistic synthetic data for rule mining.
  C. Cooper, M. Zito.   PKDD 2007
• An exact analysis of the Cockayne-Goodman-Hedetniemi algorithm for a class of random tree processes
  C. Cooper, M. Zito.   Discrete Applied Mathematics 2007 .
  
• The cover time of sparse random graphs.
  C. Cooper, A. Frieze.   Random Structures and Algorithms 2007
• The cover time of the preferential attachment graphs.
  C. Cooper, A. Frieze.   Journal of Combinatorial Theory 2007
  
  2006
  
• The degree distribution of the generalized duplication model.
  G. Bebek, P. Berenbrink, C. Cooper, T. Friedetzky, J. Nadeau, C. Sahinalp.  Theoretical Computer Science 2006
  
• The age specific degree distribution of web-graphs.
  C. Cooper.   Combinatorics Probability and Computing 2006
  
• Hamilton Cycles in Random Lifts of Graphs.
  K. Burgin, C. Cooper, A.M. Frieze, P. Chebolu.  European Journal of Combinatorics 2006
• Searching for black-hole faults in a network using multiple agents.
  C. Cooper, R. Klasing, T. Radzik. OPODIS 2006.
  
  2005
  
• Sampling regular graphs and a peer to peer network.
  C. Cooper, M. Dyer, C. Greenhill.  SODA 2005
  Corrigendum to above
  
  
• The cover time of two classes of random graphs.
  C. Cooper, A. Frieze.   SODA 2005
  
• Lower bounds and algorithms for dominating sets in web graphs.
  C. Cooper, R. Klasing, M.Zito.   Internet Mathematics 2005
  
  2004
  
• A randomized algorithm for the joining protocol in dynamic distributed networks .
  C. Cooper, R. Klasing, T. Radzik.   INRIA research report RR-5376 (CNRS report I3S/RR-2004-39-FR)
  
• Dominating sets in web graphs.
  C. Cooper, R. Klasing, M.Zito.  WAW2004
  
• The cover time of random regular graphs.
  C. Cooper, A. Frieze.  SIAM J. Discrete Mathematics
  
• Random vertex deletion in a scale free random graph
  C. Cooper, A. Frieze, J. Vera.  Internet Mathematics 2004
• The size of the cores of a random graph with a given degree sequence.
  C. Cooper.   Random Structures and Algorithms 2004
• The size of the largest strong component of a random digraph with a given degree sequence.
  C. Cooper, A. Frieze.   Combinatorics Probability and Computing 2004
  
  2003
  
• Crawling on simple models of web-graphs.
  C. Cooper, A. Frieze.  STOC 2002, Internet Mathematics 2003.
  
• The cover time of sparse random graphs
  C. Cooper, A. Frieze.  SODA 2003
  
• A general model of web graphs.
  C. Cooper, A. Frieze.  Random Structures and Algorithms 2003
  
• On randomly generated intersecting hypergraphs
  T. Bohman, C.Cooper, A. Frieze, R. Martin, M. Ruszinko Electronic Journal on Combinatorics, R29
  
  2002
  
• Classifying special interest groups in web graphs.
  C. Cooper.   Proceedings of RANDOM 2002
  
• Multicoloured Hamilton cycles in random edge coloured graphs.
  C. Cooper, A. Frieze   Combinatorics Probability and Computing 2002
  
• A note on random 2SAT with prescribed literal degrees.
  C. Cooper, A. Frieze, G. Sorkin.  SODA 2002
  
  2001
  
• A general model of web graphs.
  C. Cooper, A. M. Frieze.  ESA 2001
  
• Hamilton cycles in Random regular graphs of non-constant degree.
  C. Cooper, A. Frieze, B. Reed. Combinatorics Probability and Computing 2001
  
• Chromatic number of random regular graphs of non-constant degree
  C. Cooper, A. Frieze, B. Reed, O. Riordan.  Combinatorics, Probability and Computing 2001
  
• On Markov chains for randomly H-colouring a graph.
  C. Cooper, M. Dyer, A. M. Frieze. Journal of Algorithms 39, 117-134 (2001)
• The union of two random permutations does not have a directed Hamilton cycle.
  C. Cooper Random Structures and Algorithms (2001).
  
  2000
  
• On the asymptotic distribution of rank of random matrices over a finite field.
  C. Cooper. Random Structures and Algorithms, 17 (2000)
  
• On the rank of random matrices.
  C. Cooper. Random Structures and Algorithms 16 (2000) 209-232.
  
• A lower bound for the number of good permutations.
  C. Cooper. Data Recording, Storage and Processing (Nat. Acad. Sci. Ukraine) (2000)
  
• On the average case complexity of shortest-paths problems in the vertex-potential model
  C. Cooper, A. M. Frieze, K. Melhorn, V. Priebe.  Random Structures and Algorithms
  
• Deriving the number of good permutations, with applications to cryptography.
  C. Cooper, R. Gilchrist, I. Kovalenko, D. Novakovic. Cybernetics and Systems Analysis 5 (2000) 10-16.
  
• Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids.
  C. Cooper, M. Dyer, A. M. Frieze, R. Rue. Journal of Mathematical Physics, (2000)
  
• Hamilton cycles in sparse random graphs of minimum degree at least k.
  B. Bollobas, C. Cooper, T. Fenner, A. M. Frieze. Journal of Graph Theory.
  
• Min-Wise independent linear permutations.
  T. Bohman, C. Cooper, A. M. Frieze. Electronic Journal of Combinatorics, 7(1) (2000)
  
• Hamilton cycles in random graphs and digraphs.
  C. Cooper, A. M. Frieze. Random Structures and Algorithms, 16 (2000) 369-401.
  
  1999
  
• Asymptotics for dependent sums of random vectors.
  C. Cooper.   Random Structures and Algorithms (1999)
  
• Mixing properties of the Swendsen-Wang process on classes of graphs.
  C. Cooper, A. M. Frieze. Random Structures and Algorithms, 15.4 (1999) 242-261.
  
  1997
  
• Average-case complexity of shortest-paths problems in the vertex potential model.
  C. Cooper, A. M. Frieze, K. Mehlhorn, V. Priebe   RANDOM 1997
  
  1996
  
• Perfect matchings in random r-regular s-uniform hypergraphs.
  C. Cooper, A. M. Frieze, M. Molloy and B. Reed. Combinatorics, Probability and Computing 5.3 (1996) 1-14
  
• Asymptotic enumeration of predicate-junction flowgraphs.
  C. Cooper. Combinatorics Probability and Computing 5.3 (1996)215-226.
  
  1995
  
• On the 2-cyclic property in 2-regular digraphs.
  C. Cooper. Random Structures and Algorithms 6.4 (1995) 439-448
  
• On the Vapnik-Chervonenkis dimension of a random graph.
  M. Anthony, G. Brightwell and C. Cooper. Proceedings of 1993 British Combinatorial Conference, Discrete Maths 138 (1995) 43-56
  
• Multicoloured Hamilton cycles in sparse random graphs; an anti-Ramsey threshold
  C. Cooper and A.M. Frieze. Electronic Journal of Combinatorics 2 (1995) R.19
  
• On the connectivity of random k-th nearest neighbour graphs.
  C. Cooper and A. M. Frieze. Combinatorics, Probability and Computing 4.4 (1995) 343-362
  
• An upper bound for the number of complete mappings.
  C. Cooper and I. Kovalenko. Prob. Theory and Math. Stats. (Kiev, Ukraine) (1995)
  
  1994
  
• Hamilton cycles in a class of random directed graphs.
  C. Cooper and A. M. Frieze. Journal of Combinatorial Theory (B)62,1 (1994) 151-163
  
• C. Cooper, A. M. Frieze and M. Molloy. Hamilton cycles in random regular digraphs. Combinatorics, Probability and Computing 3 (1994) 39-49
• Probabilistic analysis of two k-cluster problems.
  C. Cooper. Discrete Applied Maths. 50 (1994) 27-51
  
• The threshold for Hamilton cycles in the square of a random graph.
  C. Cooper.Random Structures and Algorithms 5.1 (1994) 25-31
  
  1993
  
• A note on the connectivity of 2-regular digraphs.
  C. Cooper. Random Structures and Algorithms 4.4 (1993) 469-472
• On the thickness of sparse random graphs.
  C. Cooper. Combinatorics, Probability and Computing 1.4 (1993) 303-310
  
  19xx
  
• 1-pancyclic Hamilton cycles in random graphs.
  C. Cooper. Random Structures and Algorithms 3.3 (1992) 277-287
• Pancyclic Hamilton cycles in random graphs.
  C. Cooper.Discrete Maths. 91 (1991) 141-148
• Pancyclic random graphs.
  C. Cooper and A. M. Frieze. In Random Graphs, (Ed: Karonski M, Javorski J, and Rucinski A.) Wiley (1990)
• On the lower bound for the number of Hamilton cycles in a random graph.
  C. Cooper and A. M. Frieze. Journal of Graph Theory 13.6 (1989) 719-735
• The limiting probability that alpha-in, beta-out is strongly connected.
  C. Cooper and A. M. Frieze. Journal of Combinatorial Theory (B) 48.1 (1989) 117-134
• A probabilistic analysis of a relaxation for the k-median problem.
  S. Ahn, C. Cooper, G. Cornuejols and A. M. Frieze. Mathematics of Operational Research 13 (1988) 1-31

Petra Berenbrink
Moez Draief
Martin Dyer
Robert Elsaesser
Alan Frieze
Ralf Klasing
Pawel Pralat
Tomasz Radzik
Thomas Sauerwald
Michele Zito


Department of Informatics