Fast Hamiltonicity Checking Via Bases of Perfect Matchings

DOI10.1145/3148227zbMath1426.68117arXiv1211.1506MaRDI QIDQ4561499

Marek Cygan, Stefan Kratsch, Jesper Nederlof

Publication date: 6 December 2018

Published in: Journal of the ACM, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.1506

zbMATH Keywords

dynamic programming; randomized algorithm; matchings; Hamiltonicity; pathwidth; matrix rank; perfect matchings; parameterized complexity; bounded treewidth

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C39: Dynamic programming

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

68W20: Randomized algorithms

05C45: Eulerian and Hamiltonian graphs