Expected Computation Time for Hamiltonian Path problem

DOI10.1137/0216034zbMATH Open0654.68083OpenAlexW2012473793MaRDI QIDQ3801093FDOQ3801093

Publication date: 1987

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

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

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

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

Cited In (33)

Bandwidth and distortion revisited
Exponential approximation schemata for some network design problems
Computing optimal Steiner trees in polynomial space
No NP problems averaging over ranking of distributions are harder
Average case completeness
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
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
An exact exponential branch-and-merge algorithm for the single machine total tardiness problem
Parallel algorithms for finding Hamilton cycles in random graphs
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
When polynomial approximation meets exact computation
The Asymmetric Travelling Salesman Problem In Sparse Digraphs.
Improved fixed parameter tractable algorithms for two ``edge problems: MAXCUT and MAXDAG
When polynomial approximation meets exact computation
An Average Case NP-complete Graph Colouring Problem
Inclusion and exclusion algorithm for the Hamiltonian path problem
A simple linear expected time algorithm for finding a Hamilton path
Sublinear time algorithms in the theory of groups and semigroups.

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)