3 papers
math.CO2021
Path decompositions of random directed graphs
Alberto Espuny Díaz, Viresh Patel, Fabian Stroh
We consider the problem of decomposing the edges of a directed graph into as few paths as possible. There is a natural lower bound for the number of paths needed in an edge decompo…
math.CO2020
Switch-based Markov Chains for Sampling Hamiltonian Cycles in Dense Graphs
Pieter Kleer, Viresh Patel, Fabian Stroh
We consider the irreducibility of switch-based Markov chains for the approximate uniform sampling of Hamiltonian cycles in a given undirected dense graph on vertices. As our ma…
math.CO2020
A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs
Viresh Patel, Fabian Stroh
We give a polynomial-time algorithm for detecting very long cycles in dense regular graphs. Specifically, we show that, given , there exists a such that the fo…