Exploiting sparsity for bipartite Hamiltonicity

DOI10.4230/LIPICS.ISAAC.2018.3MaRDI QIDQ5090992FDO

Authors Andreas Björklund

Publication date 21 July 2022

zbMATH Keywords

Hamiltonian cyclebipartite graph

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Determinant sums for undirected Hamiltonicity
• Finding Hamilton cycles in sparse random graphs
• An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three

Cites work

• scientific article; zbMATH DE number 2086688 (Why is no real title available?)
• A bound on the pathwidth of sparse graphs with applications to exact algorithms
• A probabilistic remark on algebraic program testing
• A simplified NP-complete satisfiability problem
• Algorithms for propositional model counting
• An Improved Exact Algorithm for Cubic Graph TSP
• Computing and Combinatorics
• Determinant sums for undirected Hamiltonicity
• Directed Hamiltonicity and out-branchings via generalized Laplacians
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Faster exponential-time algorithms in graphs of bounded average degree
• Functional analysis
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Pathwidth of cubic graphs and exact algorithms
• Reducibility among combinatorial problems
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The Traveling Salesman Problem for Cubic Graphs
• The traveling salesman problem in bounded degree graphs

Cited in

(1)

• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.

This page was built for publication: Exploiting sparsity for bipartite Hamiltonicity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090992)