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
2023 2024
PRE-PRINTS -- Subject to revision
TOP TOP
Learning from a Sample in Online Algorithms Rank of the vertex-edge incidence matrix of r-out hypergraphs On the cover time of the emerging giant A randomly weighted minimum arborescence with a random cost constraint Giant descendant trees and matching sets in the preferential attachment graph Spanners in randomly weighted graphs: independent edge lengths Localization Game for Random Graphs A scaling limit for the length of the longest cycle in a sparse random digraph
TOP
The concentration of the maximum degree in the duplication-divergence models A scaling limit for the length of the longest cycle in a sparse random graph Hamiltonicity of random graphs in the stochastic block model The effect of adding randomly weighted edges Shortest paths with a cost constraint: a probabilistic analysis Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects Maker Breaker on Digraphs Finding maximum matchings in random regular graphs in linear expected time A randomly weighted minimum spanning tree with a random cost constraint Minimum-weight combinatorial structures under random cost-constraints Isomorphism for Random k-Uniform Hypergraphs
TOP
Degree Distribution for Duplication-Divergence Graphs: Large Deviations On the existence of Hamilton cycles with a periodic pattern in a random digraph Hamilton cycles in random graphs with minimum degree at least 3: an improved analysis On random multi-dimensional assignment problems The game chromatic number of a random hypergraph A note on randomly colored matchings in random graphs Separating effect from significance in Markov chain tests Random volumes in d-dimensional polytopes Random graphs with a fixed maximum degree A note on spanning K_r-cycles in random graphs On the connectivity threshold for colorings of random graphs and hypergraphs
TOP
Minors of a random binary matroid How many randomly colored edges make a randomly colored dense graph rainbow hamiltonian or rainbow connected?* Understanding Our Markov Chain Significance Test: A reply to Cho and Rubinstein-Salzedo On the cover time of dense graphs A note on log-concave random graphs Travelling in randomly embedded random graphs A random variant of the game of plates and olives Notes on Growing a Tree in a Graph On the connectivity threshold for colorings of random graphs and hypergraphsJOURNAL VERSION On the insertion time of random walk
cuckoo hashing Pattern Colored Hamilton Cycles in Random Graphs A note on the localization number of random graphs: diameter two case Perfect matchings and Hamiltonian cycles in the preferential attachment model On the rank of a random binary matrix
TOP
A note on dispersing particles on a line Diffusion limited aggregation on the Boolean lattice On the distribution of the minimum weight clique Online purchasing under uncertainty Elegantly colored paths and cycles in edge
colored random graphs On rainbow Hamilton cycles in random hypergraphs A greedy algorithm for finding a large 2-matching on a random cubic graph The cover time of a biased random walk on a random cubic graph Constraining the clustering transition for colorings of sparse random graphs Packing Hamilton Cycles Online Balanced Allocation Through Random Walk The covertime of a biased random walk on G(n,p) On the trace of random walks on random
graphs
TOP
On edge disjoint spanning trees in a randomly weighted complete graph Separating subadditive Euclidean functionals Randomly coloring simple hypergraphs with fewer colors Travelling in randomly embedded random graphsJOURNAL VERSION Minimum-cost matching in a random graph with random costs Assessing significance in a Markov chain without mixing Looking for vertex number one On random k-out sub-graphs of large graphs Embedding the Erdos-Renyi Hypergraph into the Random Regular Hypergraph and Hamiltonicity On the insertion time of random walk
cuckoo hashingJOURNAL VERSION
TOP
Rainbow Arborescence in Random Digraphs Separating subadditive Euclidean functionalsJOURNAL VERSION Vacant sets and vacant nets:
Component structures induced by a random walk Weak and Strong versions of the 1-2-3 conjecture for uniform
hypergraphs Discordant voting processes on finite graphs On the length of a random minimum spanning tree Rainbow Matchings and Hamilton Cycles in Random Graphs
TOP
Power of k choices and rainbow spanning trees in random graphs Rainbow Connection of Random Regular Graphs Walker-Breaker games Long paths in random Apollonian
networks An almost linear time algorithm for finding
Hamilton cycles in sparse random graphs with minimum degree at least
three Random triangle removal On-line list colouring of
random graphs A note on the vacant set of random walks on
the hypercube and other regular graphs of high degree On the chromatic number of a random hypergraph Between 2- and 3-colorability Efficient algorithms for three-dimensional axial and planar random assignment problems Loose Hamilton Cycles in Regular Hypergraphs
TOP
Random Structures and Algorithms The t-tone chromatic number of random graphs Maker-Breaker games on random
geometric graphs
The height of random k-trees and related branching processes
Cover time of a random graph with given degree sequence II:
Allowing vertices of degree two On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three Expanders via Random Spanning Trees The topology of competetively constructed graphs
Packing tree factors in random and pseudo-random graphs Rainbow Hamilton cycles in random graphs
TOP
Coloring simple hypergraphs Approximate counting of regular
hypergraphs via switchings On a sparse random graph with minimum degree
three: Likely Posa's sets are large On the non-planarity of a random
subgraph On the game chromatic number of sparse random graphs Tight Hamilton Cycles in Random Uniform Hypergraphs
Component structure induced by a random
walk on a random graph
TOP
Randomly coloring constant degree graphs Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs Cops and Robbers on Geometric Graphs
Cover time of a random graph with given degree sequence Maximum Matchings in Random Bipartite
Graphs and the Space Utilization of Cuckoo Hashtables Rainbow Connectivity of sparse random graphs Packing Hamilton Cycles in Random and Pseudo-Random Hypergraphs Packing Tight Hamilton Cycles in Uniform Hypergraphs Variations on Cops and Robbers Rainbow Hamilton cycles in uniform hypergraphs High Degree Vertices,
Eigenvalues and Diameter of Random Apollonian Networks Some typical properties of the Spatial
Preferred Attachment model Analyzing Walksat on Random Formulas
Stationary distribution and cover time of random walks on random digraphs Packing tight Hamilton cycles in 3-uniform hypergraphs
TOP
The cover time of random walks on random
uniform hypergraphs Karp-Sipser on random graphs with a fixed degree sequence Randomly colouring simple hypergraphs The cover time of random geometric
graphs John Wiley and Sons, 324-349An Analysis of Random-Walk Cuckoo Hashing Loose Hamilton Cycles in Random k-Uniform Hypergraphs Ramsey games with giants John Wiley and Sons, 1-32. Packing tight Hamilton cycles in 3-uniform hypergraphsJOURNAL VERSION Component structure induced by a random walk on a random graph JOURNAL VERSION
TOP
A note on the random greedy triangle-packing algorithm Hypergraphs with independent neighborhoods
Multiple random walks in random regular graphs Random walks with look-ahead in scale-free random graphs Logconcave Random Graphs Flips in Graphs An Efficient Sparse Regularity Concept Loose Hamilton Cycles in Random 3-Uniform Hypergraphs Hamilton cycles in random graphs with a fixed degree sequence Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time Anti-Ramsey Properties of Random Graphs Randomly colouring random graphs John Wiley and Sons, 251-272.Coloring H-free hypergraphs John Wiley and Sons, 11-25.
TOP
Hamilton cycles in 3-out John Wiley and Sons, 393-417. Program to check some calculation Multiple random walks in random regular graphs JOURNAL VERSION Memoryless Rules for Achlioptas Processes
Average-case analyses of Vickrey costs An Analysis of Random-Walk Cuckoo Hashing JOURNAL VERSION Line of Sight Networks
Seperating populations with wide data: a spectral analysis The cover time of random geometric
graphs JOURNAL VERSION An Efficient Sparse Regularity Concept On Smooth k-CNF Formulas and the Walksat Algorithm
TOP
On rainbow trees and cycles On the chromatic number of simple triangle-free triple systems A new approach to the planted clique problem Game Chromatic Index of Graphs with
Given Restrictions on Degrees On two Hamilton cycle problems in random graphs The cover time of the giant component of a random
graph John Wiley and Sons, 401-439. Logconcave Random Graphs JOURNAL VERSION Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time JOURNAL VERSION Hamilton cycles in random lifts of
complete directed graphs The game chromatic number of random graphs John Wiley and Sons, 223-235. Random k-SAT: the limiting probability for satisfiability for moderately growing k
TOP
On the average case performance of some greedy approximation
algorithms for the uncapacitated facility location problem Seperating populations with wide data: a spectral analysis JOURNAL VERSION On the chromatic number of random graphs with a fixed degree sequence A Geometric Preferential Attachment Model of
Networks II The cover time of random digraphs JOURNAL VERSION Product Rule Wins a Competitive Game Random 2-SAT with prescribed literal
degrees
The diameter of randomly perturbed digraphs and some applications John Wiley and Sons, 484-504. A Geometric Preferential Attachment Model of
Networks First Order Definability of Trees and Sparse Random Graphs Adversarial deletions in a scale free random graph process The probabilistic relationship between the assignment
and asymmetric traveling salesman problems Codes Identifying Sets of Vertices in Random Networks A survey on the use of Markov chains to randomly sample colorings The cover time of the preferential attachment graph On Randomly Generated Intersecting Hypergraphs II John Wiley and Sons, 17-34.The cover time of sparse random graphs John Wiley and Sons, 1-16.Line of Sight Networks JOURNAL VERSION
TOP
The influence of search engines on preferential attachment Randomly coloring sparse random graphs with fewer colors than the maximum degree John Wiley and Sons, 450-465Hamilton Cycles in Random Lifts of Graphs Almost universal graphs John Wiley and Sons, 499-510On randomly colouring locally sparse graphs The satisfiability threshold for randomly generated binary constraint satisfaction
problems John Wiley and Sons, 323-339
On the random 2-stage minimum spanning tree John Wiley and Sons, 24-36.
TOP
Random k-SAT: A tight threshold for moderately
growing k The strong chromatic index of random graphs
High degree vertices and eigenvalues in the preferential attachment graph The game of JumbleG On the average case performance of some greedy approximation
algorithms for the uncapacitated facility location problem JOURNAL VERSION The cover time of random regular graphs Perfect matchings in random bipartite graphs with minimal degree at least 2 John Wiley and Sons, 319-358.
On packing Hamilton Cycles in epsilon-regular Graphs The influence of search engines on preferential attachment JOURNAL VERSION Adversarial deletions in a scale free random graph process JOURNAL VERSION On the random 2-stage minimum spanning tree JOURNAL VERSION
TOP
Fast Monte-Carlo algorithms for finding low rank
approximations A Geometric Preferential Attachment Model of
Networks Random deletions in a scale free random graph process Avoidance of a giant component in half the edge
set of a random graph Program to check some calculations John Wiley and Sons, 432-449.On random symmetric travelling salesman problems Randomly coloring constant degree graphs JOURNAL VERSION The diameter of randomly perturbed digraphs and some applications JOURNAL VERSION Perfect matchings in random graphs with prescribed minimal degree Clustering Large Graphs via the Singular Value Decomposition The size of the largest strongly connected
component of a random digraph with a given degree sequence On the b-independence number of sparse random graphs Efficient communication in an ad-hoc network Adding random edges to dense graphs John Wiley and Sons, 105-117.The emergence of a giant component in a random
subgraph of pseudo-random graphs John Wiley and Sons, 42-50.
TOP
Randomly colouring graphs with lower bounds on
girth and maximum degree John Wiley and Sons, 167-179.High degree vertices and eigenvalues in the preferential attachment graph JOURNAL VERSION The satisfiability threshold for randomly generated binary constraint satisfaction
problems JOURNAL VERSION Crawling on web graphs On Randomly Generated Intersecting Hypergraphs Arc-Disjoint Paths in Expander Digraphs On a general model of web graphs John Wiley and Sons, 311-335.A probabilistic analysis of randomly generated
binary constraint satisfaction problems The cover time of sparse random graphs JOURNAL VERSION
Perfect matchings in random graphs with prescribed minimal degree JOURNAL VERSION How many random edges make a dense graph Hamiltonian?
TOP
On Counting Independent Sets in Sparse Graphs Hamilton Cycles in Random Subgraphs of Pseudo-Random
Graphs On graph irregularity strength Random regular graphs of non-constant degree:
independence and chromatic number On random symmetric travelling salesman problemsJOURNAL VERSION
Random regular graphs of non-constant degree:
connectivity and Hamilton cycles Probabilistic analysis of the Traveling Salesman
Problem Crawling on web graphsJOURNAL VERSION
Random k-SAT: A tight threshold for moderately
growing k JOURNAL VERSION
Optimal sequencing by hybridization in rounds A New Rounding Procedure for the Assignment Problem
with Applications to Dense Graph Arrangement Problems Multi-coloured Hamilton cycles in randomly
coloured random graphs A note on random 2-SAT with prescribed literal
degrees JOURNAL VERSION
Balls and Bins Models with Feedback
TOP
A general approach to dynamic packet routing with
bounded buffers Vertex covers by edge disjoint cliques G-intersecting families Arc-Disjoint Paths in Expander DigraphsJOURNAL VERSION
On a general model of web graphsJOURNAL VERSION
Randomly colouring graphs with lower bounds on
girth and maximum degreeJOURNAL VERSION
Avoiding a giant component John Wiley and Sons, 75-85Optimal sequencing by hybridization in roundsJOURNAL VERSION
Edge disjoint paths in expander graphs On Markov chains for randomly H-colouring a graph Hamilton cycles in the union of random permutations
John Wiley and Sons, 83-94.
The probabilistic relationship between the assignment
and asymmetric traveling salesman problemsJOURNAL VERSION
TOP
On the number of perfect matchings and Hamilton
cycles in epsilon-regular non-bipartite graphs Mixing properties of the Swendsen-Wang process on
classes of graphs II A note on random minimum length spanning trees Optimal Construction of Edge-Disjoint Paths
in Random Regular Graphs
Hamilton cycles in random graphs and directed graphs John Wiley and Sons, 369-401.Edge disjoint paths in expander graphs JOURNAL VERSION
Average-case analysis of shortest-paths algorithms
in the vertex potential model John Wiley and Sons, 33-46.
A Note on Sparse Random Graphs and Cover
Graphs On Hamilton cycles in sparse random graphs with
minimum degree at least k John
Wiley and Sons, 42-59.Min-Wise independent linear permutations
TOP
On counting independent
sets in sparse graphs JOURNAL VERSION
On the Power of Universal Bases in Sequencing by
Hybridization Mixing Properties of the Swendsen-Wang Process on
Classes of Graphs John Wiley and Sons, 242-261.
Splitting an expander graph Existence and construction of edge low congestion
paths on expander graphs John Wiley and Sons, 87-109. Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs
JOURNAL VERSION
Torpid mixing of some MCMC algorithms in Statistical
Physics Clustering in large graphs and matricesJOURNAL VERSION
A simple algorithm for constructing Szemeredi's
Regularity Partition Optimal construction of edge-disjoint paths
in random graphs On Perfect Matchings and Hamiltonian Cycles in
Sums of Random Trees Log-Sobolev inequalities and sampling from log-concave
distributions Quick approximation to matrices and applications
TOP
Dynamic packet routing on arrays with bounded buffers Maximum matchings in sparse random graphs: Karp-Sipser
revisited John Wiley and Sons ,111-178.Greedy algorithms for the shortest common superstring
that are asymptotically optimal Min-Wise Independent permutations
Approximately counting Hamilton cycles in dense
graphs On balls and bins with deletions
Disjoint Paths in Expander Graphs via Random Walks:
a Short Survey Probabilistic Analysis of Algorithms A polynomial-time algorithm for learning noisy
linear threshold functions Average case analysis of the merging algorithm of
Hwang and Lin Fast Monte-Carlo algorithms for finding low rank approximations JOURNAL VERSION
Random minimum length spanning trees in regular
graphs
TOP TOP
On the connectivity of random k-th nearest
neighbour graphs
Analysis of Two Simple Heuristics on a Random
Instance of k-SAT
Perfect matchings in random r-regular, s-uniform
hypergraphs Greedy algorithms for the shortest common superstring that are asymptotically
optimalJOURNAL VERSION
Analysis of Parallel Algorithms for Finding
A Maximal Independent Set in A Random Hypergraph
John Wiley and Sons , 359-378.
Generating and counting Hamilton cycles
in random regular graphs A New Rounding Procedure for the Assignment Problem with Applications
to Dense Graph Arrangement ProblemsJOURNAL VERSION
A polynomial-time algorithm for learning noisy linear threshold functionsJOURNAL
VERSION
Learning linear transformations The regularity lemma and approximation schemes for dense problemsJOURNAL VERSION
A general approach to dynamic packet routing with
bounded buffersJOURNAL VERSION
Coloring Bipartite Hypergraphs An efficient algorithm for the vertex-disjoint paths problem in random
graphs. On the best case of heapsort
TOP
Randomised greedy matching II John Wiley and Sons , 55-74. An Analysis of a Monte Carlo Algorithm for Estimating
the Permanent
Multicoloured Hamilton Cycles
Ordering Clone Libraries in Computational Biology
When is the Assignment Bound Tight for the Asymmetric
Traveling-Salesman Problem ?
Polynomial Time Randomised Approximation Schemes
for Tutte-Grothendieck Invariants: The Dense Case
John Wiley and Sons , 459-478.
Analysis of a simple greedy matching algorithm
on random cubic graphs
Perfect Matchings in Random s-Uniform Hypergraphs John Wiley and Sons , 41-57.Covering the edges of a random graph by cliques Multicoloured Hamilton cycles in random graphs:
an anti-Ramsey threshold. Balanced allocations for tree-like inputs
On key storage in secure networks The worst-case running time of the random simplex
algorithm is exponential in the height
Improved approximation algorithms for MAX k-CUT and MAX BISECTIONJOURNAL VERSION
Probabilistic analysis of an algorithm in
the theory of markets in indivisible goods
TOP
Random walks, totally unimodular
matrices and a randomised dual simplex algorithm. Multicoloured trees in random graphs John Wiley and Sons , 45-56.Randomised greedy matching IIJOURNAL VERSION
Optimal construction of edge disjoint paths in random graphsJOURNAL
VERSION
Approximately counting Hamilton cycles in dense graphsJOURNAL VERSION
On the Problem of Approximating the Number
of Bases of a Matroid The probability of unique solutions of sequencing
by hybridization
Hamilton cycles in random regular digraphs Finding hidden Hamilton cycles John Wiley and Sons , 395-410. Sampling from log-concave distributions
Near-perfect token distribution John Wiley and Sons , 559-572Broadcasting in random graphs, Hamilton cycles in a class of random directed graphs Polynomial time randomised approximation schemes for the Tutte polynomial
of dense graphs.JOURNAL VERSION
On the complexity of computing the diameter of a polyhedron On the independence number of random cubic graphs John Wiley and Sons , 649-664.Existence and construction of edge disjoint paths on expander graphs
TOP TOP
On the independence and chromatic numbers of
random regular graphs On the expected performance of a parallel algorithm for finding
maximal independent sets John Wiley and Sons , 215 -
222.On small subgraphs of random graphs John Wiley and Sons 67 - 90.Counting Hamilton cycles in random directed graphs John Wiley and Sons , 235-242.Probabilistic analysis of the generalised assignment problem Random walks, totally unimodular matrices and a randomised dual
simplex algorithm.JOURNAL VERSION
When is the assignment bound asymptotically tight for the asymmetric
traveling-salesman problem?JOURNAL VERSION
Existence and construction of edge disjoint paths on expander graphsJOURNAL VERSION
On subgraph sizes in random graphs Separator based parallel divide and conquer in computational geometry
TOP
Randomised greedy matching John Wiley and Sons , 29-46.
Occupancy problems and random algebras A random polynomial time algorithm for approximating the volume of convex
bodies Spanning maximal planar subgraphs of random graphs John Wiley and Sons , 225-232.
A parallel algorithm for finding the lexicographically first depth first
search tree in a random graph John Wiley and Sons , 233-240. On the length of the longest monotone subsequence
of a random permutation
On hidden Hamilton cyclesJOURNAL VERSION
Computing the volume of a convex body: a
case where randomness provably helps
On a conjecture of
Bondy and Fan
TOP
Edge disjoint trees in random graphs
Probabilistic analysis of a parallel algorithm for finding maximal
independent sets John Wiley and Sons , 39-50.
The limiting probability that a-in, b-out is strongly connected On an optimisation problem with nested constraints Probabilistic analysis of graph algorithms
Probabilistic analysis of the generalised assignment problem JOURNAL VERSION On the independence number of random graphs
On patching algorithms for random asymmetric travelling salesman problems Pancyclic random graphs John Wiley
and Sons , 29-39.Parallel colouring of random graphs John Wiley
and Sons , 41-52.Hamiltonian cycles in a class of random graphs: one step further John Wiley
and Sons , 53-59.
Greedy matching on the line Hamilton cycles in random graphs with minimal degree at least k
TOP
A new integer programming formulation of the permutation flowshop problem
Probabilistic analysis of random m-dimensional
knapsack problems A randomized algorithm for
fixed dimensional linear programming Algorithms for assignment
problems on an array processor Algorithms for shortest
paths problems on an array processor Random graph orders
The solution of some random NP-hard problems
in polynomial expected time Survival time of a random graph On the number of hamilton cycles in a random graph On matchings and Hamilton cycles in random graphs
On random minimum length spanning trees A random polynomial time algorithm for approximating the volume of
convex bodies JOURNAL VERSION
TOP
Probabilistic analysis of a relaxation for the k-median problem On the random construction of heaps Reconstructing truncated integer variables satsifying linear congruences Finding hamilton cycles in sparse random graphs An algorithm for finding hamilton cycles in random digraphs Partitioning random graphs into large cycles On the complexity of computing the volume of a polyhedron Edge-colouring random graphs On random regular graphs with non-constant degree
TOP
On large induced trees in sparse random graphs
Parallel algorithms for finding hamilton cycles in random graphs
On the strength of connectivity of random subgraphs of the n-cube A probabilistic analysis of the next fit decreasing bin packing
heuristic
On the exact solution of random travelling salesman problems with
medium-sized integer costs Large holes in sparse random graphs An algorithm for finding hamilton paths and cycles in random graphs
TOP TOP
On the value of a random minimum spanning tree problem An algorithm for finding hamiltonian cycles in random graphsJOURNAL VERSION
The shortest path problem for graphs with random arc-lengths On the complexity of partitioning graphs into connected subgraphs An analysis of some graph theoretic heuristics for the facilities layout
problem A parallel algorithm for all-pairs shortest paths in a random graph A simple heuristic for the p-centre problem An algorithm for finding a matroid basis that maximises the product
of the weights of the elements On matchings and hamiltonian cycles in random graphs Limit distribution for the existence of hamiltonian cycles in random
bipartite graphs
TOP
Approximation algorithms for the m-dimensional 0-1 knapsack problem:
worst-case and probabilistic analysis A partitioning algorithm for minimum weighted euclidean matching Linear congruential generators do not produce random sequences JOURNAL VERSION
Long cycles in sparse random graphs Algebraic flows Hamiltonian cycles in random regular graphs On the existence of polychromatic sets of edges in graphs and digraphs Partitioning heuristics for two geometric maximisation problems
TOP TOP TOP TOP TOP TOP TOP
Minimum paths in directed graphs A generalisation of the greedy algorithm for matroids
TOP TOP TOP TOP