Hamiltonian path


Also found in: Wikipedia.

Hamiltonian path

[‚ham·əl′tō·nē·ən ‚path]
(mathematics)
A path along the edges of a graph that traverses every vertex exactly once and terminates at its starting point. Also known as Hamiltonian circuit; Hamiltonian cycle.

Hamiltonian path

References in periodicals archive ?
1) Assume that there is a Hamiltonian path which does not end at [x.
For convenience we first transform the problem to a Hamiltonian path problem and also get rid of the special base node.
They showed that after removing at most [square root of n](2[square root of 2]) edges from any complete geometric graph of n vertices, the resulting graph still contains a plane Hamiltonian path.
Among the topics are synthesizing cyclotriphosphazene containing an aminopropylsilicone functional group as a flame retardant, the design and analysis of an optical-communication-band sub-wavelength grating polarizer, the synthesis and electrochromic properties of crystalline three-dimensional urchin-like nanostructures, calculating the beating-up force for three-dimensional weaving, the aging process of vegetable insulating oil, an algorithm for extracting visual features from images of the surface of Mars, and self-learning by robots and the model of a Hamiltonian path with a fixed number of color repetitions for systems of scenarios creation.
A Hamiltonian path in G may be realized as a subgraph [P.
In a Hamiltonian Path problem, a series of towns are connected to each other by a fixed number of bridges.
The research team including four faculty members and 15 undergraduate students from the biology and mathematics departments engineered the DNA of Escherichia coli bacteria and created bacterial computers capable of solving a classic mathematical problem known as the Hamiltonian Path Problem.
It was previously known that an unconstrained Hamiltonian path exists in a triangular grid under very mild conditions, and that there are triangular grids for which there is no through-edge Hamiltonian path.
Adleman used his DNA computer to solve the Hamiltonian Path problem that most of us likely encountered in junior high or high school math class.
The proof involves a reduction of a known NP-hard problem, the Hamiltonian path problem [Garey and Johnson 1979], to the problem of precise, flow-insensitive, intraprocedural may-alias analysis.
The problem of making the list described in the foregoing is called finding a Hamiltonian path through the tournament.
Mathematically, this is known as the directed Hamiltonian path problem, and it serves as a surrogate for a wide variety of practical computational problems.