%0 Journal Article %A Dyer, Martin %A Frieze %A Jerrum %D 1993 %T Approximately counting Hamilton paths and cycles in dense graphs %U https://kilthub.cmu.edu/articles/journal_contribution/Approximately_counting_Hamilton_paths_and_cycles_in_dense_graphs/6476891 %R 10.1184/R1/6476891.v1 %2 https://kilthub.cmu.edu/ndownloader/files/11908511 %K Hamiltonian graph theory. %K Paths and cycles (Graph theory) %X Abstract: "We describe fully polynomial randomized approximation schemes for the problems of determining the number of Hamilton paths and cycles in an n-vertex graph with minimum degree (1/2 + [epsilon])n, for any fixed [epsilon] > 0. We show that the exact counting problems are #P-complete. We also describe fully polynomial randomized approximation schemes for counting paths and cycles of all sizes in such graphs." %I Carnegie Mellon University