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 ?
Let V = {[v.sub.1],..., [v.sub.n]), and let the first Hamiltonian path be [v.sub.1], [v.sub.2], [v.sub.3]...,[ v.sub.n].
The proposed heuristic uses greedy depth first search to create a Hamiltonian path. The path construction starts from the highest degree vertex because it increases the probability of returning to the starting vertex.
Assume that H[{[u.sub.2], [v.sub.2], [w.sub.1], [w.sub.2], [x.sub.3]}] has a Hamiltonian path.
(2007) have proposed a method of determining the order of presentation of the visualization schemes using Hamiltonian paths. A Hamiltonian path will ensure that all the visualization schemes are presented before a participant.
But if a sufficient condition can be derived for a graph with diameter more than two, Hamiltonian path or cycle may be found with fewer edges.
We consider each type at every level of the network, as data flows from source [right arrow] (through) intermediary [right arrow] (to) destination, thus modeling the relation between nodes of a pair in a game of 2 players with only 3 strategies and each path from a given source to sink as Hamiltonian path [14], as data visits each node exactly once [15].
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.
Hamiltonian Path Problem (HPP) is one of the best known NP-complete problems, which asks whether or not for a given graph [gamma] = (N, E) (N is the set of nodes and E is the set of edges in y) contains a Hamiltonian path, that is a path of length n that visits all nodes from y exactly once; we do not specify the first and last nodes of a path, and each node in node set N can be the first node or the last one.
A Hamiltonian path in G may be realized as a subgraph [P.sub.[pi]] = (V, [E.sub.[pi]]) of G, where [pi] is a permutation of V and [E.sub.[pi]] = {{[pi](i), [pi](i + 1)}|0 [less than or equal to] I < n - 1}.
However, even with a computer, a Hamiltonian Path problem can easily become too complicated to solve.
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.
Key words: adaptive grid refinement; Hamiltonian path; load balancing; refinement-tree partition.