Solving the Hamiltonian path problem with a light-based computer

DOI10.1007/S11047-007-9042-ZMaRDI QIDQ926517zbMATH OpenOpenAlexWikidataFDO

Authors Mihai Oltean

Publication date 20 May 2008

Published in Natural Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0708.1512

zbMATH Keywords

Hamiltonian pathNP-completelight-based computing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Abstract: In this paper we propose a special computational device which uses light rays for solving the Hamiltonian path problem on a directed graph. The device has a graph-like representation and the light is traversing it by following the routes given by the connections between nodes. In each node the rays are uniquely marked so that they can be easily identified. At the destination node we will search only for particular rays that have passed only once through each node. We show that the proposed device can solve small and medium instances of the problem in reasonable time.

Recommendations

• A Light-Based Device for Solving the Hamiltonian Path Problem
• Solving the subset-sum problem with a light-based device
• Solving the generalized subset sum problem with a light based device
• scientific article; zbMATH DE number 1342106
• The Traveling Beams Optical Solutions for Bounded NP-Complete Problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 743584 (Why is no real title available?)
• scientific article; zbMATH DE number 870411 (Why is no real title available?)
• scientific article; zbMATH DE number 3340881 (Why is no real title available?)
• A Light-Based Device for Solving the Hamiltonian Path Problem
• An Algorithm for SAT Without an Extraction Phase
• An optical model of computation
• Rainbow sort: Sorting at the speed of light
• The On-Line Encyclopedia of Integer Sequences

Cited in

(6)

• Exact cover with light
• A Light-Based Device for Solving the Hamiltonian Path Problem
• On the complexity of nonuniform wavelength-based machine
• Computing transparently: The independent sets in a graph
• Solving the generalized subset sum problem with a light based device
• Solving the subset-sum problem with a light-based device

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Solving the Hamiltonian path problem with a light-based computer

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q926517)