List of Publications
197419751976197719781979
1980198119821983198419851986198719881989
1990199119921993199419951996199719981999
200020012002
20032004200520062007
20082009
PRE-PRINTS -- Subject to revision
TOP
2009
- Hamilton cycles in 3-out
Random Structures and Algorithms 33, John Wiley and Sons, 393-417.
Program to check some calculation
[Co-author: T.Bohman]
- Multiple random walks in random regular graphs
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
to appear in 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
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 Combiantorics 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
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
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
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
- 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
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
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 saleman 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]
- Fast algorithms for some random NP-hard problems
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]
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
- On large matchings and cycles in sparse random graphs
Discrete Mathematics 59, 243-256.
- On the Lagarias-Odlyzko algorithm for the subset-sum problem
SIAM Journal on Computing 15, 536-539.
- Maximum matchings in a class of random graphs
Journal of Combinatorial Theory Series B 40, 196-212.
- Planar 3DM is NP-Complete
Journal of Algorithms 7, 174-184.
[Co-author: M.E. Dyer]
- Linear programs with random costs
Mathematical Programming 35, 3-16.
[Co-authors: M.E. Dyer and C.J.H. Mc.Diarmid]
- Fast algorithms for some random NP-hard problems
Extended abstract in the proceedings of the 27th Annual IEEE Symposium
on the Foundations of Computer Science.
[Co-author: M.E. Dyer]
- Expected behaviour of line balancing heuristics
I.M.A. Journal on Mathematics in Management 1, 1-11.
[Co-author: I. Baybars]
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
- On the quadratic assignment problem
Discrete Applied Mathematics 5, 89-98.
[Co-author: J. Yadegar]
- An extension of Christofides Heuristic to the k-person travelling
salesman problem
Discrete Applied Mathematics 6, 79-83.
- On the existence of hamiltonian cycles in a class of random graphs
Discrete Mathematics 45, 301-305.
[Co-author: T.I. Fenner]
- Complexity of a 3-dimensional assignment problem
European Journal of Operational Research 13, 161-164.
TOP
1982
TOP
1981
- An algorithm for solving 3-dimensional assignment problems with
application to scheduling a teaching practice
Journal of the Operational Research Society 32, 989-995.
[Co-author: J. Yadegar]
TOP
1980
- Probabilistic analysis of some Euclidean clustering problems
Discrete Applied Mathematics 2, 295-309.
TOP
1979
TOP
1978
- A partitioned inverse in linear programming
Journal of the Operational Research Society 29, 383-388.
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
- Shortest path algorithms for knapsack type problems
Mathematical Programming 11, 150-157.
TOP
1975
- Bottleneck linear programming
Operational Research Quarterly 26, 871-874.
TOP
1974
- A cost function property for plant location problems
Mathematical Programming 7, 245-248.
- A bilinear programming formulation of the 3-dimensional assignment problem
Mathematical Programming 7, 376-379.
TOP