research
∙
08/03/2023
Another Hamiltonian Cycle in Bipartite Pfaffian Graphs
We present a linear-time algorithm that, given as input (i) a bipartite ...
share
research
∙
11/04/2021
The Shortest Even Cycle Problem is Tractable
Given a directed graph, we show how to efficiently find a shortest (dire...
research
∙
09/24/2020
An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs
We present a polynomial space Monte Carlo algorithm that given a directe...
research
∙
07/28/2020
Counting Short Vector Pairs by Inner Product and Relations to the Permanent
Given as input two n-element sets 𝒜,ℬ⊆{0,1}^d with d=clog n≤(log n)^2/(l...
research
∙
03/07/2020
The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid
We show that computing the Tutte polynomial of a linear matroid of dimen...
research
∙
06/20/2018
Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm
Given an undirected graph and two disjoint vertex pairs s_1,t_1 and s_2,...
research
∙
05/31/2018