Equational Bases for If–Then–Else
Four formalizations of the instruction if–then–else are considered. Let $K$ be an equational class of algebras. Assume the language has constants $ \bot $ in case II, $T$, $F$, $ \bot $ in c...
Four formalizations of the instruction if–then–else are considered. Let $K$ be an equational class of algebras. Assume the language has constants $ \bot $ in case II, $T$, $F$, $ \bot $ in c...
Weighted Leaf AVL-Trees
A new data structure called a weighted leaf AVL-tree is presented for representing a collection of weighted items drawn from a totally ordered set. It is shown that using this data structure, the aver...
A new data structure called a weighted leaf AVL-tree is presented for representing a collection of weighted items drawn from a totally ordered set. It is shown that using this data structure, the aver...
You are not logged in to this journal. Log in
Expected Computation Time for Hamiltonian Path problem
SIAM J. Comput. Volume 16, Issue 3, pp. 486-502 (1987)
Issue Date: 1987
Connotea
CiteULike
del.icio.us
BibSonomy
One way to cope with an NP-hard problem is to find an algorithm that is fact on average with respect to a natural probability distribution on inputs. We consider from that point of view the Hamiltonian Path Problem. Our algorithm for the Hamiltonian Path Problem constructs or establishes the nonexistence of a Hamiltonian path. For a fixed probability $p$, the expected run-time of our algorithm on a random graph with $n$ vertices and the edge probability $p$ is $O(n)$. The algorithm is adaptable to directed graphs.
©1987 Society for Industrial and Applied Mathematics
| History: | Received 1985-06-27; accepted 1986-07-26 |
| Permalink: | http://dx.doi.org/10.1137/0216034 |
KEYWORDS and AMS
average case complexity,
NP-hard Hamiltonian circuit Hamiltonian path,
probability,
random graphs,
expected polynomial time,
expected sublinear time
05G35, 60C05, 68A10, 68A20
PUBLICATION DATA
0097-5397 (print)
1095-7111 (online)
SIAM