Expected Computation Time for Hamiltonian Path problem

DOI10.1137/0216034zbMath0654.68083OpenAlexW2012473793MaRDI QIDQ3801093

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 graph Hamiltonian path average case complexity edge probability expected polynomial time expected sublinear time NP-hard Hamiltonian circuit

Mathematics Subject Classification ID

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

Related Items (33)

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

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