Carnegie Mellon University
Browse

Approximately counting Hamilton paths and cycles in dense graphs

Download (1.6 MB)
journal contribution
posted on 1993-01-01, 00:00 authored by Martin Dyer, Frieze, Jerrum
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."

History

Publisher Statement

All Rights Reserved

Date

1993-01-01

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC