Expected Computation Time for Hamiltonian Path problem
From MaRDI portal
Publication:3801093
DOI10.1137/0216034zbMath0654.68083MaRDI 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
random graph; Hamiltonian path; average case complexity; edge probability; expected polynomial time; expected sublinear time; NP-hard Hamiltonian circuit
68Q25: Analysis of algorithms and problem complexity
05C80: Random graphs (graph-theoretic aspects)
68R10: Graph theory (including graph drawing) in computer science
05C38: Paths and cycles
60C05: Combinatorial probability
Related Items
Inclusion and exclusion algorithm for the Hamiltonian path problem, Average case completeness, The maximum clique problem, Some properties of sets tractable under every polynomial-time computable distribution, No NP problems averaging over ranking of distributions are harder