Directed Hamiltonicity and Out-Branchings via Generalized Laplacians

2016/07/14 by Björklund, Andreas, Kaski, Petteri, Koutis, Ioannis
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1607.04002

Abstract

We are motivated by a tantalizing open question in exact algorithms: can we detect whether an n-vertex directed graph G has a Hamiltonian cycle in time significantly less than 2ⁿ? We present new randomized algorithms that improve upon several previous works: 1. We show that for any constant 0

Related

• Getting directed Hamilton cycle twice faster
• An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs
• An O(n) time algorithm for finding Hamilton cycles with high probability
• Hamiltonicity below Dirac's condition
• Random directed graphs are robustly Hamiltonian