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
Full Article | PDF ArticleMore Like This
Natan T. Shaked, Stephane Messika, Shlomi Dolev, and Joseph Rosen
Appl. Opt. 46(5) 711-724 (2007)
Tobias Haist and Wolfgang Osten
Opt. Express 15(16) 10473-10482 (2007)
Janusz Mroczka and Damian Szczuczyński
Appl. Opt. 51(11) 1715-1723 (2012)