Some recent papers that are available on-line:
List of Publications
1974 1975 1976
1977 1978 1979
1980 1981 1982
1983 1984 1985
1986 1987 1988
1989
1990 1991 1992
1993 1994 1995
1996 1997 1998
1999
2000 2001 2002
2003 2004
2005 2006 2007
2008 2009 2010
2011 2012 2013
2014 2015 2016
2017 2018 2019
2020 2021 2022
PRE-PRINTS -- Subject to revision
TOP
2022
On the cover time of the emerging giant
SIAM Journal on Discrete Mathematics 36, 441 - 468
[Co-authors: W. Pegden, T. Tkocz]
A randomly weighted minimum arborescence with a random cost constraint
Mathematics of Operations Research 47, 1664-1680.
[Co-author: T. Tkocz]
Giant descendant trees and matching sets in the preferential attachment graph
Journal of Applied Probability 59, 2021-2029.
[Co-authors: H. Acan, B. Pittel]
Spanners in randomly weighted graphs: independent edge lengths
Discrete Applied Mathematics 309, 68-74.
[Co-author: W. Pegden]
Localization Game for Random Graphs
Discrete Applied Mathematics 309, 202-214.
[Co-authors: A. Dudek, S. English, C. MacRury, P. Pralat]
A scaling limit for the length of the longest cycle in a sparse random digraph
Random Structures and Algorithms 60, 3-24.
[Co-author: M. Anastos]
TOP
2021
The concentration of the maximum degree in the duplication-divergence models
Proceedings of COCOON 2021, 413-424.
[Co-authors: K. Turowski, W. Szpankowski]
A scaling limit for the length of the longest cycle in a sparse random graph
Journal of Combinatorial Theory B, 184-208.
[Co-author: M. Anastos]
Hamiltonicity of random graphs in the stochastic block model
SIAM Journal on Discrete Mathematics 35, 1854-1880.
[Co-authors: M. Anastos, J. Gao]
The effect of adding randomly weighted edges
SIAM Journal on Discrete Mathematics 35, 1182-1200.
Shortest paths with a cost constraint: a probabilistic analysis
Discrete Applied Mathematics 302, 46-53.
[Co-author:T. Tkocz]
Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects
Operations Research Letters 49, 400-404.
[Co-author:T. Tkocz]
Maker Breaker on Digraphs
Journal of Graph Theory 98. 653-661
[Co-author: W. Pegden]
Finding maximum matchings in random regular graphs in linear expected time
Random Structures and Algorithms 58, 390-429
[Co-author: M. Anastos]
A randomly weighted minimum spanning tree with a random cost constraint
Electronic Journal of Combinatorics 28
[Co-author:T. Tkocz]
Minimum-weight combinatorial structures under random cost-constraints
Electronic Journal of Combinatorics 28
[Co-authors: W. Pegden, G. Sorkin, T. Tkocz]
Isomorphism for Random k-Uniform Hypergraphs
Information Processing Letters 166.
[Co-authors: D. Chakraborti, S. Haber, M. Hasabnis]
TOP
2020
Degree Distribution for Duplication-Divergence Graphs: Large Deviations
Graph-Theoretic Concepts in Computer Science, WG2020, 226-237.
[Co-authors: K. Turowski, W. Szpankowski]
On the existence of Hamilton cycles with a periodic pattern in a random digraph
Electronic Journal on Combinatorics, 27.
[Co-authors: P. Pralat, X. Perez-Gimenez]
Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis
Random Structures and Algorithms 57, 865-878.
[Co-author: M. Anastos]
On random multi-dimensional assignment problems
Discrete Applied Mathematics 287, 1-9.
[Co-authors: W. Pegden, T. Tkocz]
The game chromatic number of a random hypergraph
Discrete Mathematics and Applications, 111-131, Springer Optimization and Its Applications, 165.
[Co-authors: D. Chakraborti, M. Hasabnis]
A note on randomly colored matchings in random graphs
Discrete Mathematics and Applications, Springer Optimization and Its Applications, 165.
Separating effect from significance in Markov chain tests
Statistics and Public Policy
[Co-authors: M. Chikina, J. Mattingly, W. Pegden]
Random volumes in d-dimensional polytopes
Discrete Analysis
[Co-authors: W. Pegden, T. Tkocz]
Random graphs with a fixed maximum degree
SIAM Journal on Discrete Mathematics 34, 53-61
[Co-author:T. Tkocz]
A note on spanning K_r-cycles in random graphs
AIMS Mathematics 5, 4849-4852
On the connectivity threshold for colorings of random graphs and hypergraphs
Random Structures and Algorithms 56, 988-997.
[Co-author: M. Anastos]
TOP
2019
Minors of a random binary matroid
Random Structures and Algorithms 55, 865-880.
[Co-authors: C. Cooper and W. Pegden]
How many randomly colored edges make a randomly colored dense graph rainbow hamiltonian or rainbow connected?*
Journal of Graph Theory 92, 405-414.
[Co-author: M. Anastos]
Understanding Our Markov Chain Significance Test: A reply to Cho and Rubinstein-Salzedo
Statistics and Public Policy 6, 50-52.
[Co-authors: M. Chikina and W. Pegden]
On the cover time of dense graphs
SIAM Journal on Discrete Mathematics 33,
[Co-authors: C, Cooper, W. Pegden]
A note on log-concave random graphs
Electronic Journal of Combinatorics 26
[Co-author: T. Tkocz]
Travelling in randomly embedded random graphs
Random Structures and Algorithms 55, 649-676
[Co-author: W. Pegden]
A random variant of the game of plates and olives
SIAM Journal on Discrete Mathematics 33, 1216-1227
[Co-authors: A. Dudek, S. English]
Notes on Growing a Tree in a Graph
Random Structures and Algorithms 55, 290-312.
[Co-Authors: L. Devroye, V. Dujmović, A. Mehrabian, P. Morin, B. Reed]
On the connectivity threshold for colorings of random graphs and hypergraphsJOURNAL VERSION
Proceedings of Random 2019
[Co-author: M. Anastos]
On the insertion time of random walk
cuckoo hashing
Random Structures and Algorithms 54, 721-729.
[Co-author: T. Johansson]
Pattern Colored Hamilton Cycles in Random Graphs
SIAM Journal on Discrete Mathematics 33, 528-545.
[Co-author: M. Anastos]
A note on the localization number of random graphs: diameter two case
Discrete Applied Mathematics 254, 107-112.
[Co-authors: A. Dudek, W. Pegden]
Perfect matchings and Hamiltonian cycles in the preferential attachment model
Random Structures and Algorithms 54, 258-288.
[Co-authors: P. Pralat, X. Perez-Gimenez, B. Reiniger]
On the rank of a random binary matrix
Electronic Journal of Combinatorics 26
[Co-authors: C. Cooper and W. Pegden]
TOP
2018
A note on dispersing particles on a line
Random Structures and Algorithms 53, 586-591.
[Co-Author: W. Pegden]
Diffusion limited aggregation on the Boolean lattice
Annals of Applied Probability 28, 3528-3557.
[Co-Author: W. Pegden]
On the distribution of the minimum weight clique
SIAM Journal on Discrete Mathematics 32, 2115-2133.
[Co-authors: W. Pegden and G. Sorkin]
Online purchasing under uncertainty
Random Structures and Algorithms 53, 327-351.
[Co-author: W. Pegden]
Elegantly colored paths and cycles in edge
colored random graphs
SIAM Journal on Discrete Mathematics 32, 1585-1618
[Co-authors: L. Espig, M. Krivelevich]
On rainbow Hamilton cycles in random hypergraphs
Electronic Journal of Combinatorics 25
[Co-authors: A. Dudek and S. English]
A greedy algorithm for finding a large 2-matching on a random cubic graph
Journal of Graph Theory 88, 449-481.
[Co-authors: D. Bal, P. Bennett, T. Bohman]
The cover time of a biased random walk on a random cubic graph
Proceedings of AofA 2018, 16:1--16:12.
[Co-authors: C. Cooper, T.Johansson]
Constraining the clustering transition for colorings of sparse random graphs
Electronic Journal of Combinatorics 25
[Co-Authors: M. Anastos and W. Pegden]
Packing Hamilton Cycles Online
Combinatorics, Probability and Computing 27, 475-496.
[Co-authors: J. Briggs, P. Loh, M. Krivelevich, B. Sudakov]
Balanced Allocation Through Random Walk
Information Processing Letters, 131, 39-43.
[Co-author: S. Petti]
The covertime of a biased random walk on G(n,p)
Proceedings of ANALCO 2017, 158-167.
[Co-authors: C. Cooper and S. Petti]
On the trace of random walks on random
graphs
Proceedings of the London Mathematical Society 16, 847-877.
[Co-authors: M. Krivelevich, P. Michaeli, R. Peled]
TOP
2017
On edge disjoint spanning trees in a randomly weighted complete graph
Combinatorics, Probability and Computing, 1-17. doi:10.1017/S0963548317000426
[Co-author: T. Johansson]
Separating subadditive Euclidean functionals
Random Structures and Algorithms 51, 375-403
[Co-author: W. Pegden]
Randomly coloring simple hypergraphs with fewer colors
Information Processing Letters 126, 39-42.
[Co-author: M. Anastos]
Travelling in randomly embedded random graphsJOURNAL VERSION
Extended abstract in RANDOM2017
[Co-author: W. Pegden]
Minimum-cost matching in a random graph with random costs
SIAM Journal on Discrete Mathematics 31, 489-510.
[Co-author: T. Johansson]
Assessing significance in a Markov chain without mixing
Proceedings of the National Academy of Sciences 114, 2860-2864.
[Co-authors: M. Chikina, W. Pegden]
Looking for vertex number one
Annals of Applied Probability 27, 582-630.
[Co-author: W. Pegden]
On random k-out sub-graphs of large graphs
Random Structures and Algorithms 50, 143-157
[Co-author: T. Johansson]
Embedding the Erdos-Renyi Hypergraph into the Random Regular Hypergraph and Hamiltonicity
Journal of Combinatorial Theore B, 122C, 719-740.
[Co-authors: A. Dudek, A. Rucinski, M. Siliekis]
On the insertion time of random walk
cuckoo hashingJOURNAL VERSION
Proceedings of SODA 2017.
[Co-author: T. Johansson]
TOP
2016
Rainbow Arborescence in Random Digraphs
Journal of Graph Theory 83
[Co-authors: Bal, Bennett, Cooper, PraĆat]
Separating subadditive Euclidean functionalsJOURNAL VERSION
Proceedings of STOC 2016, 22-35.
[Co-author: W. Pegden]
Vacant sets and vacant nets:
Component structures induced by a random walk
SIAM Journal on Discrete Mathematics 30, 166-205.
[Co-author: C. Cooper]
Weak and Strong versions of the 1-2-3 conjecture for uniform
hypergraphs
The Electronic Journal of Combinatorics 23.
[Co-authors: P. Bennett, A. Dudek, L. Helenius]
Discordant voting processes on finite graphs
Proceedings of ICALP 2016.
[Co-authors: C. Cooper, M. Dyer, N. Rivera]
On the length of a random minimum spanning tree
Combinatorics, Probability and Computing 25, 89-107.
[Co-authors: C. Cooper, N. Ince, S. Janson, J. Spencer]
Rainbow Matchings and Hamilton Cycles in Random Graphs
Random Structures and Algorithms 48, 503-523.
[Co-author: D. Bal]
TOP
2015
Power of k choices and rainbow spanning trees in random graphs
The Electronic Journal of Combinatorics 22
[Co-authors: D. Bal, P. Bennett and P. Pralat]
Rainbow Connection of Random Regular Graphs
SIAM Journal on Discrete Mathematics 29, 2255-2266.
[Co-authors: A. Dudek, C. Tsourakakis]
Walker-Breaker games
SIAM Journal on Discrete Mathematics 29, 1476-1485.
[Co-authors: L. Espig, M. Krivelevich, W. Pegden]
Long paths in random Apollonian
networks
Internet Mathematics 11, 308-318.
[Co-author: C. Cooper]
An almost linear time algorithm for finding
Hamilton cycles in sparse random graphs with minimum degree at least
three
Random Structures and Algorithms 47, 73-98.
[Co-author: S. Haber]
Random triangle removal
Advances in Mathematics 280, 379-438.
[Co-authors: T. Bohman, E. Lubetzky]
On-line list colouring of
random graphs
Electronic Journal on Combinatorics
[Co-authors: D. Mitsche, X. Perez-Gimenez, P. Pralat]A note on the vacant set of random walks on
the hypercube and other regular graphs of high degree
Moscow Journal of Combinatorics and Number Theory, 4, 21-44.
[Co-author: C. Cooper]
On the chromatic number of a random hypergraph
Journal of Combinatorial Theore B, 113, 68-122.
[Co-authors: M. Dyer, C. Greenhill]
Between 2- and 3-colorability
Electronic Journal of Combinatorics
[Co-author: W. Pegden]
Efficient algorithms for three-dimensional axial and planar random assignment problems
Random Structures and Algorithms 46, 160-196.
[Co-author: G.Sorkin]
Loose Hamilton Cycles in Regular Hypergraphs
Combinatorics, Probability and Computing 24, 179-194.
[Co-authors: A. Dudek, A. Rucinski, M. Silekis]
TOP
2014
Random Structures and Algorithms
Proceedings of the International Congress of Mathematicians, Seoul 2014, Volume 1, 311-340.
The t-tone chromatic number of random graphs
Graphs and Combinatorics 30, 1073-1086.
[Co-authors: D. Bal, P. Bennett, A. Dudek]
Maker-Breaker games on random
geometric graphs
Random Structures and Algorithms 45, 553-607
[Co-authors: A. Beveridge, A. Dudek, T. Mueller, M. Stojakovic]
The height of random k-trees and related branching processes
Random Structures and Algorithms 45, 675-702
[Co-author: C. Cooper, R. Uehera]
Cover time of a random graph with given degree sequence II:
Allowing vertices of degree two
Random Structures and Algorithms 45, 627-674
[Co-authors: C. Cooper, E. Lubetzky]
On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three
Random structures and Algorithms 45, 443-497.
Expanders via Random Spanning Trees
SIAM Journal on Computing 43, 497-513
[Co-authors: N. Goyal, L. Rademacher and S. Vempala]
The topology of competetively constructed graphs
Electronic Journal of Combinatorics 21
[Co-author: W. Pegden]
Packing tree factors in random and pseudo-random graphs
Electronic Journal of Combinatorics 21
[Co-authors: D. Bal, M. Krivelevich, P. Loh]
Rainbow Hamilton cycles in random graphs
Random Structures and Algorithms 44, 328-354.
[Co-author: P. Loh]
TOP
2013
Coloring simple hypergraphs
Journal of Combinatorial Theory B 103, 767-794.
[Co-author: D.Mubayi]
Approximate counting of regular
hypergraphs via switchings
Information Processing Letters 113, 785-788.
[Co-authors: A. Dudek, A. Rucinski, M. Silekis]
On a sparse random graph with minimum degree
three: Likely Posa's sets are large
Journal of Combinatorics 4, 123-156
[Co-author: B. Pittel]
On the non-planarity of a random
subgraph
Combinatorics, Probability and Computing 22, 722-732.
[Co-authors: M. Krivelevich]
On the game chromatic number of sparse random graphs
SIAM Journal of Discrete Mathematics 27, 768-790.
[Co-authors: S. Haber, M. M. Lavrov]
Tight Hamilton Cycles in Random Uniform Hypergraphs
Random structures and Algorithms 42, 374-385
[Co-author: A. Dudek]
Component structure induced by a random
walk on a random graph
Random structures and Algorithms 42, 135-158
[Co-author: C.Cooper]
TOP
2012
Randomly coloring constant degree graphs
Random Structures and Algorithms 43, 181-200.
[Co-authors: M. Dyer, T. Hayes and E. Vigoda]
Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs
Electronic Journal of Combinatorics 19.
[Co-authors: A.Dudek, P. Loh, S. Speiss]
Cops and Robbers on Geometric Graphs
Combinatorics, Probability and Computing 21, 816-834
[Co-authors: A. Beveridge, A. Dudek, T. Mueller]
Cover time of a random graph with given degree sequence
Discrete Mathematics 312, 3146-3163
[Co-authors: M. Abdullah and C.Cooper]
Maximum Matchings in Random Bipartite
Graphs and the Space Utilization of Cuckoo Hashtables
Random Structures and Algorithms 41, 334-364.
[Co-author: P.Melsted]
Rainbow Connectivity of sparse random graphs
Proceedings of Random 2012 and Electronic Journal of Combinatorics 19.
[Co-author: C.E. Tsourakakis]
Packing Hamilton Cycles in Random and Pseudo-Random Hypergraphs
Random Structures and Algorithms 41, 1-22.
[Co-authors: M. Krivelevich]
Packing Tight Hamilton Cycles in Uniform Hypergraphs
SIAM Journal on Discrete Mathematics 26, 435-451.
[Co-author: D. Bal]
Variations on Cops and Robbers
Journal of Graph Theory 69, 383-402.
[Co-authors: M. Krivelevich and P.Loh]
Rainbow Hamilton cycles in uniform hypergraphs
Electronic Journal of Combinatorics 19.
[Co-authors: A. Dudek, A. Rucinski]
High Degree Vertices,
Eigenvalues and Diameter of Random Apollonian Networks
WAW2012
[Co-author: C. Tsourakakis]
Some typical properties of the Spatial
Preferred Attachment model
WAW2012
[Co-authors: C. Cooper, P. Pralat]
Analyzing Walksat on Random Formulas
Proceedings of ANALCO 2012.
[Co-author: A. Coja-Oghlan]
Stationary distribution and cover time of random walks on random digraphs
Journal of Combinatorial Theory B 102, 329-362.
[Co-author: C. Cooper]
Packing tight Hamilton cycles in 3-uniform hypergraphs
Random Structures and Algorithms 40, 269-300.
[Co-authors: M.Krivelevich and P.Loh]
TOP
2011
The cover time of random walks on random
uniform hypergraphs
SIROCCO 2011, 210-221.
[Co-authors: C.Cooper,T.Radzik]
Karp-Sipser on random graphs with a fixed degree sequence
Combinatorics, Probability and Computing 20, 721-742.
[Co-author: T. Bohman]
Randomly colouring simple hypergraphs
Information Processing Letters 11, 848-853.
[Co-author: P.Melsted]
The cover time of random geometric
graphs
Random Structures and Algorithms 38, John Wiley and Sons, 324-349
[Co-author: C.Cooper]
An Analysis of Random-Walk Cuckoo Hashing
SIAM Journal on Computing 40, 291-308.
[Co-authors: P.Melsted and M.Mitzenmacher]
Loose Hamilton Cycles in Random k-Uniform Hypergraphs
Electronic Journal of Combinatorics, P48.
[Co-author: A.Dudek]
Ramsey games with giants
Random Structures and Algorithms 38, John Wiley and Sons, 1-32.
[Co-authors: T.Bohman, M.Krivelevich, P. Loh, B. Sudakov]
Packing tight Hamilton cycles in 3-uniform hypergraphsJOURNAL VERSION
SODA 2011
[Co-authors: M.Krivelevich and P.Loh]
Component structure induced by a random walk on a random graph JOURNAL VERSION
SODA 2011
[Co-author: C.Cooper]
TOP
2010
A note on the random greedy triangle-packing algorithm
Journal of Combinatorics 1, 477-488.
[Co-authors: T.Bohman, E.Lubetzky]
Hypergraphs with independent neighborhoods
Combinatorica 30, 277-293
[Co-authors: T.Bohman, D.Mubayi and O.Pikhurkho]
Multiple random walks in random regular graphs
SIAM Journal on Discrete Mathematics 23, 1738-1761.
[Co-authors: C.Cooper and T.Radzik]
Random walks with look-ahead in scale-free random graphs
SIAM Journal on Discrete Mathematics 24 1162-1176.
[Co-author: C.Cooper]
Logconcave Random Graphs
Electronic Journal of Combinatorics
[Co-authors: S.Vempala and J.Vera]
Flips in Graphs
SIAM Journal on Discrete Mathematics 24 1046-1055
[Co-authors: T.Bohman, A. Dudek and O.Pikhurkho]
An Efficient Sparse Regularity Concept
SIAM Journal on Discrete Mathematics 23 2000-2034
[Co-authors: A. Coja-Oghlan and C.Cooper]
Loose Hamilton Cycles in Random 3-Uniform Hypergraphs
Electronic Journal of Combinatorics 17, N28
Hamilton cycles in random graphs with a fixed degree sequence
SIAM Journal on Discrete Mathematics 24, 558-569
[Co-authors: C.Cooper and M.Krivelevich]
Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time
JACM 57 1-27
[Co-authors: P.Chebolu and P.Melsted]
Anti-Ramsey Properties of Random Graphs
Journal of Combinatorial Theory B 100, 299-312.
[Co-authors: T.Bohman, O.Pikhurkho and C.Smyth]
Randomly colouring random graphs
Random Structures and Algorithms 36, John Wiley and Sons, 251-272.
[Co-author: M.Dyer]
Coloring H-free hypergraphs
Random Structures and Algorithms 36, John Wiley and Sons, 11-25.
[Co-authors: T.Bohman and D.Mubayi]
TOP
2009
Hamilton cycles in 3-out
Random Structures and Algorithms 35, John Wiley and Sons, 393-417.
Program to check some calculation
[Co-author: T.Bohman]
Multiple random walks in random regular graphs JOURNAL VERSION
Multiple Random Walks and Interacting Particle Systems, Springer Berlin / Heidelberg, 399-410.
[Co-authors: C.Cooper and T.Radzik]
Memoryless Rules for Achlioptas Processes
SIAM Journal on Discrete Mathematics 23, 993-1008.
[Co-authors: A.Beveridge, T.Bohman and O.Pikhurkho]
Average-case analyses of Vickrey costs
to appear in RANDOM09
[Co-authors: P.Chebolu,P.Melsted and G.Sorkin]
An Analysis of Random-Walk Cuckoo Hashing JOURNAL VERSION
RANDOM09
[Co-authors: P.Melsted and M.Mitzenmacher]
Line of Sight Networks
Combinatorics, Probability and Computing 18, 145-163.
[Co-authors: J. Kleinberg, R. Ravi and W. Debany]
Seperating populations with wide data: a spectral analysis
Electronic Journal of Statistics 3, 76-113.
[Co-authors: A. Coja-Oghlan, A. Blum, S. Zhou]
The cover time of random geometric
graphs JOURNAL VERSION
Proceedings of SODA 2009, 48-57
[Co-author: C.Cooper]
An Efficient Sparse Regularity Concept
Proceedings of SODA 2009, 207-216
[Co-authors: A. Coja-Oghlan and C.Cooper]
On Smooth k-CNF Formulas and the Walksat Algorithm
Proceedings of SODA 2009, 451-460
[Co-authors: A. Coja-Oghlan, U. Feige, M. Krivelevich, D. Vilenchik]
TOP
2008
On rainbow trees and cycles
Electronic Journal of Combinatorics 15, R59
[Co-author: M.Krivelevich]
On the chromatic number of simple triangle-free triple systems
Electronic Journal of Combinatorics, R121.
[Co-author: D.Mubayi]
A new approach to the planted clique problem
Proceedings of Foundations of Software Technology and Theoretical Computer Science, Bangalore, India
[Co-author: R. Kannan]
Game Chromatic Index of Graphs with
Given Restrictions on Degrees
Theoretical Computer Science 407, 242-249
[Co-authors: A.Beveridge, T.Bohman and O.Pikhurkho]
On two Hamilton cycle problems in random graphs
Israel Journal of Mathematics 166, 221-234.
[Co-author: M.Krivelevich]
The cover time of the giant component of a random
graph
Random Structures and Algorithms 32, John Wiley and Sons, 401-439.
[Co-author: C. Cooper]
Logconcave Random Graphs JOURNAL VERSION
Proceedings of STOC 2008
[Co-authors: S.Vempala and J.Vera]
Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time JOURNAL VERSION
Proceedings of ICALP2008
[Co-authors: P.Chebolu and P.Melsted]
Hamilton cycles in random lifts of
complete directed graphs
SIAM Journal on Discrete Mathematics 22, 520-540.
[Co-author: P. Chebolu]
The game chromatic number of random graphs
Random Structures and Algorithms 32, John Wiley and Sons, 223-235.
[Co-authors: T.Bohman and B.Sudakov]
Random k-SAT: the limiting probability for satisfiability for moderately growing k
Electronic Journal on Combinatorics, N2
[Co-author: A. Coja-Oghlan]
TOP
2007
On the average case performance of some greedy approximation
algorithms for the uncapacitated facility location problem
Combinatorics, Probability and Computing 16, 713-732.
[Co-authors: A. Flaxman, J.Vera]
Seperating populations with wide data: a spectral analysis JOURNAL VERSION
Proceedings of ISAAC 2007
[Co-authors: A. Coja-Oghlan, A. Blum, S. Zhou]
On the chromatic number of random graphs with a fixed degree sequence
Combinatorics, Probability and Computing 16, 733-746.
[Co-authors: M.Krivelevich and C.Smyth]
A Geometric Preferential Attachment Model of
Networks II
Internet Mathematics 4, 87-112
(also in Proceedings of WAW 2007).
[Co-authors: A.Flaxman and J.Vera]
The cover time of random digraphs JOURNAL VERSION
Proceedings of RANDOM 2007.
[Co-author: C. Cooper]
Product Rule Wins a Competitive Game
Proceedings of the American Mathematical Society 135, 3061-3071.
[Co-authors: A.Beveridge, T.Bohman and O.Pikhurko]
Random 2-SAT with prescribed literal
degrees
Algorithmica 48, 249-265
[Co-authors: C. Cooper and G. Sorkin]
The diameter of randomly perturbed digraphs and some applications
Random Structures and Algorithms 30, John Wiley and Sons, 484-504.
[Co-author: A. Flaxman]
A Geometric Preferential Attachment Model of
Networks
Internet Mathematics 3, 187-205.
[Co-authors: A.Flaxman and J.Vera]
First Order Definability of Trees and Sparse Random Graphs
Combinatorics, Probability and Computing 16, 375-400.
[Co-authors: T.Bohman, T. Luczak, O. Pikhurko, C.Smyth, J. Spencer, O. Verbitsky]
Adversarial deletions in a scale free random graph process
Combinatorics, Probability and Computing 16, 261-270.
[Co-authors:A. Flaxman, J.Vera]
The probabilistic relationship between the assignment
and asymmetric traveling salesman problems
SIAM Journal on Computing 36, 1435-1452.
[Co-author: G.Sorkin]
Codes Identifying Sets of Vertices in Random Networks
Discrete Mathematics 307, 1094-1107.
[Co-authors: R. Martin, J. Moncel, M. Ruszinko, C.Smyth]
A survey on the use of Markov chains to randomly sample colorings
In Combinatorics, Complexity and Chance, A tribute to Dominic Welsh, (G. Grimmett, C. McDiarmid Eds.), 53-71.
[Co-author: E.Vigoda]
The cover time of the preferential attachment graph
Journal of Combinatorial Theory, Series B 97, 269-290.
[Co-author: C. Cooper]
On Randomly Generated Intersecting Hypergraphs II
Random Structures and Algorithms 30, John Wiley and Sons, 17-34.
[Co-authors: T. Bohman, R. Martin, M. Ruszinko, C. Smyth]
The cover time of sparse random graphs
Random Structures and Algorithms 30, John Wiley and Sons, 1-16.
[Co-author: C.Cooper]
Line of Sight Networks JOURNAL VERSION
SODA 2007.
[Co-authors: J. Kleinberg, R. Ravi and W. Debany]
TOP
2006
The influence of search engines on preferential attachment
Internet Mathematics 3, 361-381.
[Co-authors: J.Vera,S.Chakrabarti ]
Randomly coloring sparse random graphs with fewer colors than the maximum degree
Random Structures and Algorithms 29, John Wiley and Sons, 450-465
[Co-authors: M. Dyer,A. Flaxman, E. Vigoda]
Hamilton Cycles in Random Lifts of Graphs
European Journal of Combinatorics 27, 1282-1293.
[Co-authors: K. Burgin, P. Chebolu, C. Cooper]
Almost universal graphs
Random Structures and Algorithms 28, John Wiley and Sons, 499-510
[Co-author: M.Krivelevich]
On randomly colouring locally sparse graphs
Discrete Mathematics & Theoretical Computer Science 8
[Co-author: J.Vera]
The satisfiability threshold for randomly generated binary constraint satisfaction
problems
Random Structures and Algorithms 28, John Wiley and Sons, 323-339
[Co-author: M.Molloy]
On the random 2-stage minimum spanning tree
Random Structures and Algorithms 28, John Wiley and Sons, 24-36.
[Co-authors:A. Flaxman, M.Krivelevich]
TOP
2005
Random k-SAT: A tight threshold for moderately
growing k
Combinatorica 25, 297-305.
[Co-author: N.C. Wormald]
The strong chromatic index of random graphs
SIAM Journal on Discrete Mathematics 19, 719-727.
[Co-authors: M.Krivelevich, B.Sudakov]
High degree vertices and eigenvalues in the preferential attachment graph
Internet Mathematics 2, 1-20
[Co-authors: A. Flaxman and T. Fenner]
The game of JumbleG
Combinatorics, Probability and Computing 14, 783-794.
[Co-authors: M. Krivelevich, O. Pikhurko and T. Szabo]
On the average case performance of some greedy approximation
algorithms for the uncapacitated facility location problem JOURNAL VERSION
STOC 2005
[Co-authors: A. Flaxman, J.Vera]
The cover time of random regular graphs
SIAM Journal on Discrete Mathematics 18, 728-740.
[Co-author: C. Cooper]
Perfect matchings in random bipartite graphs with minimal degree at least 2
Random Structures and Algorithms 26, John Wiley and Sons, 319-358.
On packing Hamilton Cycles in epsilon-regular Graphs
Journal of Combinatorial Theory B, 94, 159-172.
[Co-author: M.Krivelevich]
The influence of search engines on preferential attachment JOURNAL VERSION
Proceedings of SODA 2005
[Co-authors: J.Vera,S.Chakrabarti ]
Adversarial deletions in a scale free random graph process JOURNAL VERSION
Proceedings of SODA 2005
[Co-authors:A. Flaxman, J.Vera]
On the random 2-stage minimum spanning tree JOURNAL VERSION
Proceedings of SODA 2005
[Co-authors:A. Flaxman, M.Krivelevich]
TOP
2004
Fast Monte-Carlo algorithms for finding low rank
approximations
JACM 51, 1025-1041
[Co-authors: R.Kannan and S.Vempala]
A Geometric Preferential Attachment Model of
Networks
Algorithms and Models for the Web-Graph: Third International Workshop, WAW
2004, Rome, Italy, October 16, 2004, Proceeedings. Lecture Notes in Computer
Science 3243 Springer, 44-55.
[Co-authors: A. Flaxman and J. Vera]
Random deletions in a scale free random graph process
Internet Mathematics 1, 463-483.
[Co-authors: C. Cooper and J. Vera]
Avoidance of a giant component in half the edge
set of a random graph
Program to check some calculations
Random Structures and Algorithms 25, John Wiley and Sons, 432-449.
[Co-authors: T. Bohman and N. Wormald]
On random symmetric travelling salesman problems
Mathematics of Operations Research 29, 878-890.
Randomly coloring constant degree graphs JOURNAL VERSION
Proceedings of FOCS 2004.
[Co-authors: M. Dyer, T. Hayes and E. Vigoda]
The diameter of randomly perturbed digraphs and some applications
Proc. of the 7th International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems and 8th International Workshop
on Randomization and Computation 345-356. JOURNAL VERSION
[Co-author: A. Flaxman]
Perfect matchings in random graphs with prescribed minimal degree
Trends in Mathematics, Birkhauser Verlag, Basel 95-132.
[Co-author: B. Pittel]
Clustering Large Graphs via the Singular Value Decomposition
Machine Learning 56, 9-33.
[Co-authors: P.Drineas,R.Kannan,S.Vempala,V.Vinay]
The size of the largest strongly connected
component of a random digraph with a given degree sequence
Combinatorics, Probability and Computing 13, 319-338.
[Co-author: C.Cooper]
On the b-independence number of sparse random graphs
Combinatorics, Probability and Computing 13, 295-310.
[Co-author: G. Atkinson]
Efficient communication in an ad-hoc network
Journal of Algorithms 52, 1-7.
[Co-authors: A. Flaxman and E. Upfal]
Adding random edges to dense graphs
Random Structures and Algorithms 24, John Wiley and Sons, 105-117.
[Co-authors: T. Bohman, M. Krivelevich, R. Martin]
The emergence of a giant component in a random
subgraph of pseudo-random graphs
Random Structures and Algorithms 24,John Wiley and Sons, 42-50.
[Co-authors: M.Krivelevich, R. Martin]
TOP
2003
Randomly colouring graphs with lower bounds on
girth and maximum degree
Random Structures and Algorithms 23, John Wiley and Sons, 167-179.
[Co-author: M.E. Dyer]
High degree vertices and eigenvalues in the preferential attachment graph JOURNAL VERSION
Proceedings of RANDOM 2003
[Co-authors: A. Flaxman and T. Fenner]
The satisfiability threshold for randomly generated binary constraint satisfaction
problems JOURNAL VERSION
Proceedings of RANDOM 2003
[Co-author: M.Molloy]
Crawling on web graphs
Internet Mathematics 1, 57-90
[Co-author: C.Cooper]
On Randomly Generated Intersecting Hypergraphs
Electronic Journal on Combinatorics, R29
[Co-authors: T. Bohman, C.Cooper, R. Martin, M. Ruszinko]
Arc-Disjoint Paths in Expander Digraphs
SIAM Journal on Computing 32, 326-344.
[Co-author: T. Bohman]
On a general model of web graphs
Random Structures and Algorithms 22, John Wiley and Sons, 311-335.
[Co-author: C. Cooper]
A probabilistic analysis of randomly generated
binary constraint satisfaction problems
Theoretical Computer Science 290, 1815-1828
[Co-authors: M.E. Dyer and M. Molloy]
The cover time of sparse random graphs JOURNAL VERSION
Proceedings of SODA 2003, 140-147.
[Co-author: C.Cooper]
Perfect matchings in random graphs with prescribed minimal degree JOURNAL VERSION
Proceedings of SODA 2003, 148-157.
[Co-author: B. Pittel]
How many random edges make a dense graph Hamiltonian?
Random Structures and Algorithms 22, 33-42.
[Co-authors: T. Bohman, R. Martin]
TOP
2002
On Counting Independent Sets in Sparse Graphs
SIAM Journal on Computing 31, 1527-1541
[Co-authors: M.E. Dyer and M.R. Jerrum]
Hamilton Cycles in Random Subgraphs of Pseudo-Random
Graphs
Discrete Mathematics 256, 137-150
[Co-author: M. Krivelevich]
On graph irregularity strength
Journal of Graph Theory 41, 120-137.
[Co-authors: R.J. Gould, M. Karonski, F. Pfender]
Random regular graphs of non-constant degree:
independence and chromatic number
Combinatorics, Probability and Computing 11, 323-342.
[Co-authors: C.Cooper, B.Reed, O.Riordan]
On random symmetric travelling salesman problems
Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 789-790.JOURNAL VERSION
Random regular graphs of non-constant degree:
connectivity and Hamilton cycles
Combinatorics, Probability and Computing 11, 249-262.
[Co-authors: C.Cooper, B.Reed]
Probabilistic analysis of the Traveling Salesman
Problem
The traveling salesman problem and its variations, G. Gutin and A.P. Punnen
(Eds.), Kluwer Academic Publisher, 257-308.
[Co-author: J.Yukich]
Crawling on web graphs
STOC 2002, 419-427 JOURNAL VERSION
[Co-author: C.Cooper]
Random k-SAT: A tight threshold for moderately
growing k
Proceedings of the Fifth International Symposium on Theory and Applications
of Satisfiability Testing, 1-6. JOURNAL VERSION
[Co-author: N.C. Wormald]
Optimal sequencing by hybridization in rounds
Journal of Computational Biology 9, 355-369.
[Co-author: B. Halldorsson]
A New Rounding Procedure for the Assignment Problem
with Applications to Dense Graph Arrangement Problems
Mathematical Programming A 92, 1-36.
[Co-authors: S.Arora and H.Kaplan]
Multi-coloured Hamilton cycles in randomly
coloured random graphs
Combinatorics, Probability and Computing 11, 129--134.
[Co-author: C. Cooper]
A note on random 2-SAT with prescribed literal
degrees
Proceedings of SODA 2002, 316-320. JOURNAL VERSION
[Co-authors: C. Cooper and G. Sorkin]
Balls and Bins Models with Feedback
Proceedings of SODA 2002, 308-315.
[Co-authors: E. Drinea and M. Mitzenmacher]
TOP
2001
A general approach to dynamic packet routing with
bounded buffers
[Co-authors: A.Z.broder and E.Upfal]
Journal of the ACM (JACM) 48, 324-349.
Vertex covers by edge disjoint cliques
Combinatorica 21 171-197.
[Co-authors: T.Bohman, M.Ruszinko, L.Thoma]
G-intersecting families
Combinatorics, Probability and Computing 10, 367-384.
[Co-authors: T.Bohman, M.Ruszinko, L.Thoma]
Arc-Disjoint Paths in Expander Digraphs
Proceedings of FOCS 2001, 558-567.
[Co-author: T. Bohman]JOURNAL VERSION
On a general model of web graphs
Proceedings of ESA 2001, 500-511.
[Co-author: C. Cooper]JOURNAL VERSION
Randomly colouring graphs with lower bounds on
girth and maximum degree
Proceedings of FOCS 2001, 579-587.JOURNAL VERSION
[Co-author: M.E. Dyer]
Avoiding a giant component
Random Structures and Algorithms 19,John Wiley and Sons, 75-85
[Co-author: T. Bohman]
Optimal sequencing by hybridization in rounds
Proceedings of RECOMB2001, 141-148.
[Co-author: B. Halldorsson] JOURNAL VERSION
Edge disjoint paths in expander graphs
SIAM Journal on Computing 30, 1790-1801.
On Markov chains for randomly H-colouring a graph
Journal of Algorithms 39, 117-134
[Co-authors: C.Cooper and M.E.Dyer]
Hamilton cycles in the union of random permutations
Random Structures and Algorithms 18, John Wiley and Sons, 83-94.
The probabilistic relationship between the assignment
and asymmetric traveling salesman problems
Proceedings of SODA 2001, 652-660.
[Co-author: G. Sorkin]JOURNAL VERSION
TOP
2000
On the number of perfect matchings and Hamilton
cycles in epsilon-regular non-bipartite graphs
Electronic Journal of Combinatorics 7, R57.
Mixing properties of the Swendsen-Wang process on
classes of graphs II
Journal of Mathematical Physics 4, 1499-1527.
[Co-authors: C.Cooper, M.E.Dyer and R.Rue]
A note on random minimum length spanning trees
Electronic Journal of Combinatorics 7, R41.
[Co-authors: M.Ruszinko, L.Thoma]
Optimal Construction of Edge-Disjoint Paths
in Random Regular Graphs
Combinatorics, Probability and Computing 9, 241-264.
[Co-author: L.Zhao]
Hamilton cycles in random graphs and directed graphs
Random Structures and Algorithms 16,John Wiley and Sons, 369-401.
[Co-author: C.Cooper]
Edge disjoint paths in expander graphs
Proceedings of SODA 2000, 717-725. JOURNAL VERSION
Average-case analysis of shortest-paths algorithms
in the vertex potential model
Random Structures and Algorithms 16,John Wiley and Sons, 33-46.
[Co-authors: C.Cooper, V.Priebe and K.Mehlhorn]
A Note on Sparse Random Graphs and Cover
Graphs
Electronic Journal of Combinatorics 7, R19.
[Co-authors: T.Bohman, M.Ruszinko, L.Thoma]
On Hamilton cycles in sparse random graphs with
minimum degree at least k
Journal of Graph Theory 34, John
Wiley and Sons, 42-59.
[Co-authors: B.Bollobas, C.Cooper and T.I.Fenner]
Min-Wise independent linear permutations
Electronic Journal of Combinatorics 7, R26.
[Co-authors: T.Bohman and C.Cooper]
TOP
1999
On counting independent
sets in sparse graphs
Proceedings of FOCS '99, 210-217.
[Co-authors: M.E.Dyer and M.R.Jerrum]JOURNAL VERSION
On the Power of Universal Bases in Sequencing by
Hybridization
Proceedings of RECOMB '99
Journal version appeared as
Optimal Reconstruction of a Sequence from its Probes
in Journal of Computational Biology 6, 361-368.
[Co-authors: F.Preparata and E.Upfal]
Mixing Properties of the Swendsen-Wang Process on
Classes of Graphs
Random Structures and Algorithms 15, John Wiley and Sons, 242-261.
[Co-author: C.Cooper]
Splitting an expander graph
Journal of Algorithms 33, 166-172.
[Co-author: M.Molloy]
Existence and construction of edge low congestion
paths on expander graphs
Random Structures and Algorithms 14, John Wiley and Sons, 87-109.
[Co-authors: A.Broder and E.Upfal]
Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs
Proceedings of SODA '99, 346-355.JOURNAL VERSION
[Co-author: L.Zhao]
Torpid mixing of some MCMC algorithms in Statistical
Physics
Proceedings of FOCS '99, 218-229.
[Co-authors: C.Borgs, J.Chayes, J.H.Kim, P.Tetali, E.Vigoda and V.Vu]
Clustering in large graphs and matrices
Proceedings of SODA '99, 291-299
[Co-authors: P.Drineas, R.Kannan, S.Vempala and V.Vinay]JOURNAL VERSION
A simple algorithm for constructing Szemeredi's
Regularity Partition
Electronic Journal of Combinatorics, 6(1) R17.
[Co-author: R.Kannan]
Optimal construction of edge-disjoint paths
in random graphs
SIAM Journal on Computing 28, 541-574.
[Co-authors: A.Z.Broder, S.Suen and E.Upfal]
On Perfect Matchings and Hamiltonian Cycles in
Sums of Random Trees
SIAM Journal on Discrete Mathematics 12, 208-216.
[Co-authors: M.Karonski and L.Thoma]
Log-Sobolev inequalities and sampling from log-concave
distributions
Annals of Applied Probability 9, 14-26.
[Co-author: R. Kannan]
Quick approximation to matrices and applications
Combinatorica 19, 175-220.
[Co-author: R. Kannan]
TOP
1998
Dynamic packet routing on arrays with bounded buffers
LATIN 3, 273-281
[Co-authors: A.Broder, E.Upfal]
Maximum matchings in sparse random graphs: Karp-Sipser
revisited
Random Structures and Algorithms 12, John Wiley and Sons ,111-178.
[Co-authors: J.Aronson and B.Pittel]
Greedy algorithms for the shortest common superstring
that are asymptotically optimal
Algorithmica 21, 21-36.
[Co-author: W.Szpankowski]
Min-Wise Independent permutations
Proceedings of the 30th Annual ACM Symposium on Theory of Computing,
327-336.
[Co-authors: A.Broder, M.Charikar, M.Mitzenmacher]
Approximately counting Hamilton cycles in dense
graphs
SIAM Journal on Computing 27, 1262-1272.
[Co-authors: M.E.Dyer and M.R.Jerrum]
On balls and bins with deletions
Proceedings of Random '98, Lecture Notes in Computer Science 1518, Springer,
145-158.
[Co-authors: M.Cole, B.Maggs, M.Mitzenmacher, A.Richa, R.Sitaraman]
Disjoint Paths in Expander Graphs via Random Walks:
a Short Survey
Proceedings of Random '98, Lecture Notes in Computer Science 1518, Springer,
1-14.
Probabilistic Analysis of Algorithms
Probabilistic Methods for Algorithmic Discrete Mathematics, Springer,
36-92.
[Co-author: B.Reed]
A polynomial-time algorithm for learning noisy
linear threshold functions
Algorithmica 22, 35-52.
[Co-authors: A.Blum, R.Kannan and S.Vempala]
Average case analysis of the merging algorithm of
Hwang and Lin
Algorithmica 22, 483-489.
[Co-authors: W.Fernandez de la Vega and M.Santha]
Fast Monte-Carlo algorithms for finding low rank approximations JOURNAL VERSION
Proceedings of 1998 IEEE Symposium on Foundations of Computer Science,
370-378.
[Co-authors: R.Kannan and S.Vempala]
Random minimum length spanning trees in regular
graphs
Combinatorica 18, 311-333.
[Co-author: A.Beveridge and C.McDiarmid]
TOP
1997
TOP
1996
On the connectivity of random k-th nearest
neighbour graphs
Combinatorics, Probability and Computing 4, 343-362.
[Co-author: C.Cooper]
Analysis of Two Simple Heuristics on a Random
Instance of k-SAT
Journal of Algorithms 20, 312-355.
[Co-author: S.Suen]
Perfect matchings in random r-regular, s-uniform
hypergraphs
Combinatorics, Probability and Computing 5, 1-15.
[Co-authors: C.Cooper, M.Molloy and B.Reed]
Greedy algorithms for the shortest common superstring that are asymptotically
optimal
Proceedings of ESA96, Springer Lecture Notes in Computer Science 1136,
194-207.
[Co-author: W.Szpankowski] JOURNAL VERSION
Analysis of Parallel Algorithms for Finding
A Maximal Independent Set in A Random Hypergraph
Random Structures and Algorithms 9, John Wiley and Sons , 359-378.
[Co-author: H.Chen]
Generating and counting Hamilton cycles
in random regular graphs
Journal of Algorithms 21, 176-198.
[Co-authors: M.R.Jerrum, M.Molloy, R.Robinson and N.C.Wormald]
A New Rounding Procedure for the Assignment Problem with Applications
to Dense Graph Arrangement Problems
Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer
Science, 21-30
[Co-authors: S.Arora and H.Kaplan]JOURNAL VERSION
The journal version of this paper is in preparation.
A polynomial-time algorithm for learning noisy linear threshold functions
Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer
Science, 330-338.
[Co-authors: A.Blum, R.Kannan and S.Vempala] JOURNAL
VERSION
Learning linear transformations
Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer
Science, 359-368.
[Co-authors: R.Kannan and M.R.Jerrum]
The regularity lemma and approximation schemes for dense problems
Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer
Science, 12-20.
[Co-author: R.Kannan] JOURNAL VERSION
A general approach to dynamic packet routing with
bounded buffers
Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer
Science, 390-399.
[Co-authors: A.Z.Broder and E.Upfal]JOURNAL VERSION
Coloring Bipartite Hypergraphs
IPCO '96, 345-358.
[Co-author: H.Chen]
An efficient algorithm for the vertex-disjoint paths problem in random
graphs.
Proceedings of SODA '96, 261-268.
[Co-authors: A.Z.Broder, S.Suen and E.Upfal]
On the best case of heapsort
Journal of Algorithms 20, 205-217.
[Co-authors: B.Bollobas and T.I.Fenner]
TOP
1995
Randomised greedy matching II
Random Structures and Algorithms 6, John Wiley and Sons , 55-74.
[Co-authors: J.Aronson, M.E.Dyer and S.Suen]
An Analysis of a Monte Carlo Algorithm for Estimating
the Permanent
Combinatorica 15, 67-83.
[Co-author: M.R.Jerrum]
Multicoloured Hamilton Cycles
Electronic Journal of Combinatorics 2, R10
[Co-authors: M.Albert and B.Reed]
Ordering Clone Libraries in Computational Biology
Journal of Computational Biology 2, 207--218
[Co-authors: M.E.Dyer and S.Suen]
When is the Assignment Bound Tight for the Asymmetric
Traveling-Salesman Problem ?
SIAM Journal on Computing 24, 484-493.
[Co-authors: R.M.Karp and B.Reed]
Polynomial Time Randomised Approximation Schemes
for Tutte-Grothendieck Invariants: The Dense Case
Random Structures and Algorithms 6, John Wiley and Sons , 459-478.
[Co-authors: N.Alon and D.Welsh]
Analysis of a simple greedy matching algorithm
on random cubic graphs
Combinatorics, Probability and Computing 4, 47-66.
[Co-authors: A.J.Radcliffe and S.Suen]
Perfect Matchings in Random s-Uniform Hypergraphs
Random Structures and Algorithms 7, John Wiley and Sons , 41-57.
[Co-author: S.Janson]
Covering the edges of a random graph by cliques
Combinatorica 15, 1-9.
[Co-author: B.Reed]
Multicoloured Hamilton cycles in random graphs:
an anti-Ramsey threshold.
Electronic Journal of Combinatorics 2, R19.
[Co-author: C.Cooper]
Balanced allocations for tree-like inputs
Information Processing Letters 55, 329-332.
[Co-authors: A.Z.Broder, C.Lund, S.Phillips, N.Reingold]
On key storage in secure networks
Journal of Cryptology 8, 189-200.
[Co-authors: M.E.Dyer, T.I.Fenner and A.Thomason]
The worst-case running time of the random simplex
algorithm is exponential in the height
Information Processing Letters 56, 79-81.
[Co-authors: A.Z.Broder, M.E.Dyer, P.Raghavan and E.Upfal]
Improved approximation algorithms for MAX k-CUT and MAX BISECTION
Proceedings of the fourth Integer Programming and Combinatorial Optimization
Conference (IPCO4)}, Springer-Verlag Lecture Notes in Computer Science 920,
1-13.
[Co-author: M.R.Jerrum] JOURNAL VERSION
Probabilistic analysis of an algorithm in
the theory of markets in indivisible goods
Annals of Applied Probability 5, 768-808.
[Co-author: B.Pittel]
TOP
1994
Random walks, totally unimodular
matrices and a randomised dual simplex algorithm.
Mathematical Programming 64, 1-16.
[Co-author: M.E.Dyer]
Multicoloured trees in random graphs
Random Structures and Algorithms 5, John Wiley and Sons , 45-56.
[Co-author: B.D.Mckay]
Randomised greedy matching II
Proceedings of 4th Annual Symposium on Discrete Algorithms (1994)
141-149.
[Co-authors: J.Aronson, M.E.Dyer and S.Suen] JOURNAL VERSION
Optimal construction of edge disjoint paths in random graphs
Proceedings of 4th Annual Symposium on Discrete Algorithms (1994)
603-612
[Co-authors: A.Z.Broder, S.Suen and E.Upfal] JOURNAL
VERSION
Approximately counting Hamilton cycles in dense graphs
Proceedings of 4th Annual ACM/SIAM Symposium on Discrete Algorithms
336-343
[Co-authors: M.E.Dyer and M.R.Jerrum] JOURNAL VERSION
On the Problem of Approximating the Number
of Bases of a Matroid
Information Processing letters 50, 9-11.
[Co-authors: Y.Azar and A.Broder]
The probability of unique solutions of sequencing
by hybridization
Journal of Computational Biology 1, 105-110.
[Co-authors: M.E.Dyer and S.Suen]
Hamilton cycles in random regular digraphs
Combinatorics, Probability and Computing 3, 39-50.
[Co-authors: C.Cooper and M.J.Molloy]
Finding hidden Hamilton cycles
Random Structures and Algorithms 5, John Wiley and Sons , 395-410.
[Co-authors: A.Broder and E.Shamir]
Sampling from log-concave distributions
Annals of Applied Probability 4, 812-837.
[Co-authors: R.Kannan and N.Polson]
Near-perfect token distribution
Random Structures and Algorithms 5, John Wiley and Sons , 559-572
[Co-authors: A.Broder, E.Shamir and E.Upfal]
Broadcasting in random graphs,
Discrete Applied Mathematics 54, 77-79.
[Co-author: M.Molloy]
Hamilton cycles in a class of random directed graphs
Journal of Combinatorial Theory B 62, 151-163
[Co-author: C.Cooper]
Polynomial time randomised approximation schemes for the Tutte polynomial
of dense graphs.
Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer
Science 24-35.
[Co-authors: N.Alon and D.Welsh] JOURNAL VERSION
On the complexity of computing the diameter of a polyhedron
Journal of Computational Complexity 4, 207-219.
[Co-author: S.Teng]
On the independence number of random cubic graphs
Random Structures and Algorithms 5, John Wiley and Sons , 649-664.
[Co-author: S.Suen]
Existence and construction of edge disjoint paths on expander graphs
SIAM Journal of Computing 23, 976-989.
[Co-authors: A.Broder and E.Upfal]
TOP
1993
TOP
1992
On the independence and chromatic numbers of
random regular graphs
Journal of Combinatorial Theory 54 , 123-132.
[Co-author: T.Luczak]
On the expected performance of a parallel algorithm for finding
maximal independent sets
Random Structures and Algorithms 3, John Wiley and Sons , 215 -
222.
[Co-authors: N.Calkin and L.Kucera]
On small subgraphs of random graphs
Proceedings of Random Graphs 1989, Poznan, John Wiley and Sons 67 - 90.
Counting Hamilton cycles in random directed graphs
Random Structures and Algorithms 3, John Wiley and Sons , 235-242.
[Co-author: S.Suen]
Probabilistic analysis of the generalised assignment problem
Mathematical Programming 55, 169-181.
[Co-author: M.E.Dyer]
Random walks, totally unimodular matrices and a randomised dual
simplex algorithm.
Proceedings of IPCO '92, 72-84.
[Co-author: M.E.Dyer] JOURNAL VERSION
When is the assignment bound asymptotically tight for the asymmetric
traveling-salesman problem?
Proceedings of IPCO '92, 453-461.
[Co-author: R.M.Karp and B.Reed] JOURNAL VERSION
Existence and construction of edge disjoint paths on expander graphs
Proceedings of the 24th Annual ACM Symposium on Theory of Computing,
140-149.
[Co-authors: A.Broder and E.Upfal] JOURNAL VERSION
On subgraph sizes in random graphs
Combinatorics, Probability and Computing 1 , 123-134.
[Co-authors: N.J.Calkin and B.D.Mckay]
Separator based parallel divide and conquer in computational geometry
Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and
Architecture
[Co-authors: G.L.Miller and S.Teng]
TOP
1991
Randomised greedy matching
Random Structures and Algorithms 2, John Wiley and Sons , 29-46.
[Co-author: M.E.Dyer]
Occupancy problems and random algebras
Discrete Mathematics 87 , 1-8.
[Co-author: M.Albert]
A random polynomial time algorithm for approximating the volume of convex
bodies
Journal of the Association for Computing Machinery 38 , 1-17.
[Co-authors: M.E.Dyer and R.Kannan]
Spanning maximal planar subgraphs of random graphs
Random Structures and Algorithms 2, John Wiley and Sons , 225-232.
[Co-author: B.Bollobas]
A parallel algorithm for finding the lexicographically first depth first
search tree in a random graph
Random Structures and Algorithms 2, John Wiley and Sons , 233-240.
[Co-author: M.E.Dyer]
On the length of the longest monotone subsequence
of a random permutation
The Annals of Applied Probability 1 , 301-305.
On hidden Hamilton cycles
Proceedings of the 23rd Annual ACM Symposium on Theory of
Computing,182-189.
[Co-authors: A.Broder and E.Shamir] JOURNAL VERSION
Computing the volume of a convex body: a
case where randomness provably helps Proceedings
of AMS Symposium on Probabilistic Combinatorics and Its Applications
, 123-170.
[Co-author: M.E.Dyer]
On a conjecture of
Bondy and Fan
Ars Combinatoria 11, 191-205.
[Co-authors: C.J.H.McDiarmid and B.Reed]
TOP
1990
Edge disjoint trees in random graphs
Periodica Mathematica Hungarica 21 , 28-30
[Co-author: T.Luczak]
Probabilistic analysis of a parallel algorithm for finding maximal
independent sets
Random Structures and Algorithms 1, John Wiley and Sons , 39-50.
[Co-author: N.Calkin]
The limiting probability that a-in, b-out is strongly connected
Journal of Combinatorial Theory 48 , 117-134.
[Co-author: C. Cooper]
On an optimisation problem with nested constraints
Discrete Applied Mathematics 26 , 159-173.
[Co-author: M.E. Dyer]
Probabilistic analysis of graph algorithms
Computing Supplement 7, Computational Graph Theory, Edited by Tinhofer,
Mayr, Noltemeier and Syslo, Springer-Verlag , 209-234.
Probabilistic analysis of the generalised assignment problem
Proceedings of Integer Programming and Combinatorial Optimization 1,
189 - 200.
[Co-author: M.E.Dyer] JOURNAL VERSION
On the independence number of random graphs
Discrete Mathematics 81 , 171-176.
On patching algorithms for random asymmetric travelling salesman problems
Mathematical Programming 46 , 361-378.
[Co-author: M.E. Dyer]
Pancyclic random graphs
in Proceedings of Random Graphs '87, Edited by M.Karonski, J.Jaworski
and A.Rucinski, John Wiley
and Sons , 29-39.
[Co-author: C. Cooper]
Parallel colouring of random graphs
in Proceedings of Random Graphs '87, Edited by M.Karonski, J.Jaworski
and A.Rucinski, John Wiley
and Sons , 41-52.
[Co-author: L. Kucera]
Hamiltonian cycles in a class of random graphs: one step further
in Proceedings of Random Graphs '87, Edited by M.Karonski, J.Jaworski
and A.Rucinski, John Wiley
and Sons , 53-59.
[Co-author: T. Luczak]
Greedy matching on the line
SIAM Journal on Computing 19 , 666-672.
[Co-authors: C.J.H.McDiarmid and B.Reed]
Hamilton cycles in random graphs with minimal degree at least k
in A tribute to Paul Erdos, edited by A.Baker, B.Bollobas and A.Hajnal,
59 - 96.
[Co-authors: B.Bollobas and T.I.Fenner]
TOP
1989
A new integer programming formulation of the permutation flowshop problem
European Journal of Operations Research 40 , 90-98
[Co-author: J. Yadegar]
Probabilistic analysis of random m-dimensional
knapsack problems
Mathematics of Operations Research 14 , 162-176.
[Co-author: M.E. Dyer]
A randomized algorithm for
fixed dimensional linear programming
Mathematical Programming 44 , 203-212.
[Co-author: M.E. Dyer]
Algorithms for assignment
problems on an array processor
Parallel Computing 11 , 151-162
[Co-authors: J.Yadegar, D.Parkinson and S.El-Horbaty]
Algorithms for shortest
paths problems on an array processor
Proceedings of the Fourth International Conference on Supercomputing,
Santa Clara CA.
[Co-authors: J.Yadegar, D.Parkinson and S.El-Horbaty]
Random graph orders
Order 6 , 19-30.
[Co-author: M.Albert]
The solution of some random NP-hard problems
in polynomial expected time
Journal of Algorithms 10 , 451-489.
[Co-author: M.E. Dyer]
Survival time of a random graph
Combinatorica 9 , 133-143.
On the number of hamilton cycles in a random graph
Journal of Graph Theory 13 , 719-735.
[Co-author: C.Cooper]
On matchings and Hamilton cycles in random graphs
Surveys in Combinatorics, 1989, Proceedings of British Combinatorial
Conference, 84-114.
On random minimum length spanning trees
Combinatorica 9 , 363-374.
[Co-author: C.McDiarmid]
A random polynomial time algorithm for approximating the volume of
convex bodies
Proceedings of 21st ACM Symposium on Theory of Computing, 375-381.
[Co-authors: M.E.Dyer and R.Kannan] JOURNAL VERSION
TOP
1988
Probabilistic analysis of a relaxation for the k-median problem
Mathematics of Operations Research 13, 1-31.
[Co-authors: S. Ahn, C. Cooper and G. Cornuejols]
On the random construction of heaps
Information Processing Letters 27, 103-109.
Reconstructing truncated integer variables satsifying linear congruences
SIAM Journal on Computing 17, 262-280.
[Co-authors: J. Hastad, R. Kannan, J.C. Lagarias, A. Shamir]
Finding hamilton cycles in sparse random graphs
Journal of Combinatorial Theory B 44, 230-250.
An algorithm for finding hamilton cycles in random digraphs
Journal of Algorithms 9 181-204.
Partitioning random graphs into large cycles
Discrete Mathematics 70 149-158.
On the complexity of computing the volume of a polyhedron
SIAM Journal on Computing 17 , 967-974.
[Co-author: M.E. Dyer]
Edge-colouring random graphs
Journal of Combinatorial Theory B 45 , 135-149.
[Co-authors: B. Jackson, C. Mc.Diarmid and B. Reed]
On random regular graphs with non-constant degree Unpublished Research Report.
TOP
1987
On large induced trees in sparse random graphs
Journal of Cominatorial Theory B42, 181-195.
[Co-author: B. Jackson]
Parallel algorithms for finding hamilton cycles in random graphs
Information Processing Letters 25, 111-117.
On the strength of connectivity of random subgraphs of the n-cube
Annals of Discrete Mathematics, 33, 17-40.
[Co-authors: M.E. Dyer and L.R. Foulds]
A probabilistic analysis of the next fit decreasing bin packing
heuristic
Operations Research Letters 5, 233-236.
[Co-authors: J. Csirik, J.B.G. Frenk, G. Galambos and A.H.G. Rinnooy
Kan]
On the exact solution of random travelling salesman problems with
medium-sized integer costs
SIAM Journal on Computing, 16, 1052-1072.
Large holes in sparse random graphs
Combinatorica 7, 265-274.
[Co-author: B. Jackson]
An algorithm for finding hamilton paths and cycles in random graphs
Combinatorica 7, 327-341.
[Co-authors: B.Bollobas and T.I.Fenner]
TOP
1986
TOP
1985
On the value of a random minimum spanning tree problem
Discrete Applied Mathematics 10, 47-56.
An algorithm for finding hamiltonian cycles in random graphs
Proceedings of the 17th Annual ACM Symposium on Theory of Computing,
430-439.
[Co-authors: B. Bollobas and T.I. Fenner] JOURNAL VERSION
The shortest path problem for graphs with random arc-lengths
Discrete Applied Mathematics 10, 57-77.
[Co-author: G.R. Grimmett]
On the complexity of partitioning graphs into connected subgraphs
Discrete Applied Mathematics 10, 139-153.
[Co-author: M.E. Dyer]
An analysis of some graph theoretic heuristics for the facilities layout
problem
European Journal of Operational Research 20, 102-114.
[Co-authors: M.E. Dyer and L.R. Foulds]
A parallel algorithm for all-pairs shortest paths in a random graph
Proceedings of the 22nd Allerton Conference on Communication, Control
and Computing, 663-670.
[Co-author: L. Rudolph]
A simple heuristic for the p-centre problem
Operations Research Letters 3, 285-288.
[Co-author: M.E. Dyer]
An algorithm for finding a matroid basis that maximises the product
of the weights of the elements
BIT 25, 434-438.
[Co-author: T.I. Fenner]
On matchings and hamiltonian cycles in random graphs
Annals of Discrete Mathematics 28, 23-46.
[Co-author: B. Bollobas]
Limit distribution for the existence of hamiltonian cycles in random
bipartite graphs
European Journal of Combinatorics 6, 327-334.
TOP
1984
Approximation algorithms for the m-dimensional 0-1 knapsack problem:
worst-case and probabilistic analysis
European Journal of Operations Research 15, 100-109.
[Co-author: M.R.B. Clarke]
A partitioning algorithm for minimum weighted euclidean matching
Information Processing Letters 18, 59-62.
[Co-author: M.E.Dyer]
Linear congruential generators do not produce random sequences
Proceedings of 25th IEEE Conference on the Foundations of Computer
Science, 480-484.
[Co-authors: R.Kannan and J.C.Lagarias] JOURNAL VERSION
Long cycles in sparse random graphs
Graph theory and combinatorics, 59-64. Proceedings of Cambridge
Combinatorial Conference in honour of Paul Erdos.
[Co-authors: B.Bollobas and T.I.Fenner]
Algebraic flows
Annals of Discrete Mathematics 19, 135-146.
Hamiltonian cycles in random regular graphs
Journal of Combinatorial Theory, Series B, 103-112.
[Co-author: T.I. Fenner]
On the existence of polychromatic sets of edges in graphs and digraphs
Progress in Graph Theory, Edited by J.A. Bondy and U.S.R. Murty, Academic
Press, 219-232.
[Co-author: T.I. Fenner]
Partitioning heuristics for two geometric maximisation problems
Operations Research Letters 3, 267-270.
[Co-authors: M.E. Dyer and C.J.H. Mc.Diarmid]
TOP
1983
TOP
1982
TOP
1981
TOP
1980
TOP
1979
TOP
1978
TOP
1977
Minimum paths in directed graphs
Operational Research Quarterly 28, 339-346.
A generalisation of the greedy algorithm for matroids
Proceedings of CP77, Conference on Combinatorial Programming at Liverpool
University.
TOP
1976
TOP
1975
TOP
1974
TOP