research
∙
08/08/2023
On the concentration of the maximum degree in the duplication-divergence models
We present a rigorous and precise analysis of the maximum degree and the...
share
research
∙
08/05/2023
On the expected efficiency of branch and bound for the asymmetric TSP
Let the costs C(i,j) for an instance of the asymmetric traveling salespe...
research
∙
10/04/2022
Rainbow spanning trees in randomly coloured G_k-out
Given a graph G=(V,E) on n vertices and an assignment of colours to its ...
research
∙
06/01/2022
Subexponential mixing for partition chains on grid-like graphs
We consider the problem of generating uniformly random partitions of the...
research
∙
05/04/2021
Spanners in randomly weighted graphs: independent edge lengths
Given a connected graph G=(V,E) and a length function ℓ:E→ℝ we let d_v,w...
research
∙
09/07/2020
Probabilistic analysis of algorithms for cost constrained minimum weighted combinatorial objects
We consider cost constrained versions of the minimum spanning tree probl...
research
∙
06/18/2020
Karp's patching algorithm on dense digraphs
We consider the following question. We are given a dense digraph D with ...
research
∙
07/08/2019
A randomly weighted minimum arborescence with a random cost constraint
We study the minimum spanning arborescence problem on the complete digra...
research
∙
04/08/2019
Practical tests for significance in Markov Chains
We give improvements to theorems which enable significance testing in Ma...
research
∙
01/22/2019
On random multi-dimensional assignment problems
We study random multidimensional assignment problems where the costs dec...
research
∙
10/10/2018
On the cover time of dense graphs
We consider arbitrary graphs G with n vertices and minimum degree at lea...
research
∙
03/14/2018
On the connectivity threshold for colorings of random graphs and hypergraphs
Let Ω_q=Ω_q(H) denote the set of proper [q]-colorings of the hypergraph ...
research
∙
01/02/2018
The cover time of a biased random walk on a random cubic graph
We study a random walk that preferes touse unvisited edges in the contex...
research
∙
06/25/2007