Expected Computation Time for Hamiltonian Path problem

DOI10.1137/0216034MaRDI QIDQ3801093zbMATH OpenOpenAlexFDO

Authors S. Shelah, Yuri Gurevich

Publication date 1987

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/939282b9d9d5b24bf86dcfd894f45e8e69c9cc14

zbMATH Keywords

random graphHamiltonian pathaverage case complexityedge probabilityexpected polynomial timeexpected sublinear timeNP-hard Hamiltonian circuit

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Paths and cycles (05C38)

Recommendations

• A simple linear expected time algorithm for finding a Hamilton path
• An algorithm for finding Hamilton paths and cycles in random graphs
• A successful algorithm for solving directed Hamiltonian path problems
• An algorithm for finding hamilton cycles in random directed graphs
• Finding a Hamilton cycle fast on average using rotations and extensions

Cited in

(35)

• Bandwidth and distortion revisited
• Exponential approximation schemata for some network design problems
• Average case completeness
• Computing optimal Steiner trees in polynomial space
• No NP problems averaging over ranking of distributions are harder
• The maximum clique problem
• Evaluation of permanents in rings and semirings
• A note on exact algorithms for vertex ordering problems on graphs
• Exponential-time approximation of weighted set cover
• Exact algorithms for exact satisfiability and number of perfect matchings
• A polynomial-space exact algorithm for TSP in degree-6 graphs
• Approximating asymmetric TSP in exponential time
• Finding a Hamilton cycle fast on average using rotations and extensions
• Traveling in randomly embedded random graphs
• \textit{Branch} \& \textit{memorize} exact algorithms for sequencing problems: efficient embedding of memorization into search trees
• An \(\mathcal{O}(N)\) time algorithm for finding Hamilton cycles with high probability
• Reductions and convergence rates of average time
• Average-case intractability vs. worst-case intractability
• Some properties of sets tractable under every polynomial-time computable distribution
• Parallel algorithms for finding Hamilton cycles in random graphs
• An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
• Hamiltonian paths in some classes of grid graphs
• Many-visits TSP revisited
• Rankable distributions do not provide harder instances than uniform distributions
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• Faster Steiner Tree Computation in Polynomial-Space
• Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
• When polynomial approximation meets exact computation
• The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
• Exact and heuristic computation of the scanwidth of directed acyclic graphs
• When polynomial approximation meets exact computation
• An Average Case NP-complete Graph Colouring Problem
• Inclusion and exclusion algorithm for the Hamiltonian path problem
• Sublinear time algorithms in the theory of groups and semigroups.
• A simple linear expected time algorithm for finding a Hamilton path

This page was built for publication: Expected Computation Time for Hamiltonian Path problem

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