Michael Anastos

activity

20162025

most citedHamiltonicity of random graphs in the stochastic block model

3 citations · 11 across the 32 of their papers we have counts for

collaborators

Showing 2021 · math.COShow all

5 papers · 2 filters

math.CO2021

Fast algorithms for solving the Hamilton Cycle problem with high probability

Michael Anastos

We study the Hamilton cycle problem with input a random graph G=G(n,p) in two settings. In the first one, G is given to us in the form of randomly ordered adjacency lists while in…

math.CO2021★ 1 cited

A fast algorithm on average for solving the Hamilton Cycle problem

Michael Anastos

We present CertifyHAM, an algorithm which takes as input a graph G and either finds a Hamilton cycle of G or it outputs that such a cycle does not exists. If G=G(n, p) and p >2000/…

math.CO2021

Packing Hamilton Cycles in Cores of Random Graphs

Michael Anastos

Consider the random graph process ${G_{t}}_{t \geq 0}$ . For $k \geq 3$ let $G_{t}^{(k)}$ denote the $k$ -core of $G_{t}$ and let $τ_{k}$ be the minimum $t$ such that the $k$ -core of $G_{t}$ …

math.CO2021★ 1 cited

On a k-matching algorithm and finding k-factors in random graphs with minimum degree k+1 in linear time

Michael Anastos

We prove that for $k + 1 \geq 3$ and $c > (k + 1) /2$ w.h.p. the random graph on $n$ vertices, $c n$ edges and minimum degree $k + 1$ contains a (near) perfect $k$ -matching. As an immediate c…

math.CO2021

A note on long cycles in sparse random graphs

Michael Anastos

Let $L_{c, n}$ denote the size of the longest cycle in $G (n, c / n)$ , $c > 1$ constant. We show that there exists a continuous function $f (c)$ such that $L_{c, n} / n \to f (c)$ a.s. fo…