Abstract

In this paper, an optical solution for the dominating set problem is provided. The solution is based on long ribbon-shaped optical filters, on which some operations can be optically applied efficiently. The provided solution requires polynomial time, exponential length of filters, and exponential number of photons to solve the dominating set problem. The provided solution is implemented experimentally using lithographic sheets, on a graph with six vertices, to find all dominating sets with two vertices.

© 2012 Optical Society of America

Optical solution for bounded NP-complete problems

Natan T. Shaked, Stephane Messika, Shlomi Dolev, and Joseph Rosen
Appl. Opt. 46(5) 711-724 (2007)

An Optical Solution For The Traveling Salesman Problem

Tobias Haist and Wolfgang Osten
Opt. Express 15(16) 10473-10482 (2007)

Simulation research on improved regularized solution of the inverse problem in spectral extinction measurements

Janusz Mroczka and Damian Szczuczyński
Appl. Opt. 51(11) 1715-1723 (2012)

Robust numerical solution to the Levi-Civita wavefront coupling problem via level set computation of the point characteristic function

Rosa Vila, Javier Portilla, and Sergio Barbero
J. Opt. Soc. Am. A 40(2) 277-284 (2023)

Solution to the shearing problem

Clemens Elster and Ingolf Weingärtner
Appl. Opt. 38(23) 5024-5031 (1999)