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
∙
08/04/2022
Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995^n) time
In a classical scheduling problem, we are given a set of n jobs of unit ...
research
∙
01/23/2022
Bounding generalized coloring numbers of planar graphs using coin models
We study Koebe orderings of planar graphs: vertex orderings obtained by ...
research
∙
11/07/2020
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
We revisit the classic task of finding the shortest tour of n points in ...
research
∙
10/16/2020
Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors
We present an 𝒪^⋆(2^0.5n) time and 𝒪^⋆(2^0.249999n) space randomized alg...
research
∙
05/22/2018
