Inclusion and exclusion algorithm for the Hamiltonian path problem

DOI10.1016/0020-0190(93)90033-6zbMath0778.68069OpenAlexW1975587904MaRDI QIDQ689624

Eric T. Bax

Publication date: 15 November 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90033-6

zbMATH Keywords

Hamiltonian pathsNP problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (17)

Algorithms to count paths and cycles ⋮ Set multi-covering via inclusion-exclusion ⋮ Computing optimal Steiner trees in polynomial space ⋮ Exact algorithms for finding longest cycles in claw-free graphs ⋮ A Hopf algebra for counting cycles ⋮ On partitioning a graph into two connected subgraphs ⋮ Faster Steiner Tree Computation in Polynomial-Space ⋮ Complexity of counting cycles using zeons ⋮ Open problems around exact algorithms ⋮ Solving the train marshalling problem by inclusion-exclusion ⋮ The Asymmetric Travelling Salesman Problem In Sparse Digraphs. ⋮ Inclusion/exclusion meets measure and conquer ⋮ Exact algorithms for exact satisfiability and number of perfect matchings ⋮ Enumerating simple paths from connected induced subgraphs ⋮ Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs ⋮ Exact algorithms for the Hamiltonian cycle problem in planar graphs ⋮ An exact algorithm for subgraph homeomorphism

Cites Work

• Unnamed Item
• A Dynamic Programming Approach to Sequencing Problems
• Expected Computation Time for Hamiltonian Path problem

This page was built for publication: Inclusion and exclusion algorithm for the Hamiltonian path problem