OSA's Digital Library

Applied Optics

Applied Optics

APPLICATIONS-CENTERED RESEARCH IN OPTICS

  • Editor: Joseph N. Mait
  • Vol. 51, Iss. 29 — Oct. 10, 2012
  • pp: 6979–6983

Light-based solution for the dominating set problem

Sama Goliaei, Saeed Jalili, and Javad Salimi  »View Author Affiliations


Applied Optics, Vol. 51, Issue 29, pp. 6979-6983 (2012)
http://dx.doi.org/10.1364/AO.51.006979


View Full Text Article

Enhanced HTML    Acrobat PDF (378 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

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

OCIS Codes
(040.5190) Detectors : Photographic film
(200.0200) Optics in computing : Optics in computing
(200.3050) Optics in computing : Information processing
(200.4560) Optics in computing : Optical data processing
(200.4960) Optics in computing : Parallel processing
(210.4680) Optical data storage : Optical memories

ToC Category:
Optics in Computing

History
Original Manuscript: March 12, 2012
Revised Manuscript: July 26, 2012
Manuscript Accepted: August 20, 2012
Published: October 5, 2012

Citation
Sama Goliaei, Saeed Jalili, and Javad Salimi, "Light-based solution for the dominating set problem," Appl. Opt. 51, 6979-6983 (2012)
http://www.opticsinfobase.org/ao/abstract.cfm?URI=ao-51-29-6979


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. D. E. Tamir, N. T. Shaked, P. J. Wilson, and S. Dolev, “High-speed and low-power electro-optical DSP coprocessor,” J. Opt. Soc. Am. A 26, A11–A20 (2009). [CrossRef]
  2. H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261–263 (2010). [CrossRef]
  3. C. Qiu and Q. Xu, “Controlling normal incident optical waves with an integrated resonator,” Opt. Express 19, 26905–26910 (2011). [CrossRef]
  4. S. Goliaei and S. Jalili, “An optical wavelength-based solution to the 3-SAT problem,” Lect. Notes Comput. Sci. 5882, 77–85 (2009). [CrossRef]
  5. S. Goliaei and S. Jalili, “Optical graph 3-colorability,” Lect. Notes Comput. Sci. 6748, 16–22 (2011). [CrossRef]
  6. S. Goliaei and S. Jalili, “An optical solution to the 3-SAT problem using wavelength based selectors,” J. Supercomput. (to be published).
  7. M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Nat. Comput. 7, 57–70 (2008). [CrossRef]
  8. T. Haist, and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15, 10473–10482 (2007). [CrossRef]
  9. S. Dolev and H. Fitoussi, “Masking traveling beams: optical solutions for NP-complete problems, trading space for time,” Theor. Comput. Sci. 411, 837–853 (2010). [CrossRef]
  10. N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP-complete problems,” Appl. Opt. 46, 711–724 (2007). [CrossRef]
  11. N. T. Shaked, T. Tabib, G. Simon, S. Messika, S. Dolev, and J. Rosen, “Optical binary-matrix synthesis for solving bounded NP-complete combinatorial problems,” Opt. Eng. 46, 108201 (2007). [CrossRef]
  12. L. Yang, R. Ji, L. Zhang, J. Ding, and Q. Xu, “On-chip CMOS-compatible optical signal processor,” Opt. Express 20, 13560–13565 (2012). [CrossRef]
  13. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st ed. (W. H. Freeman, 1979).
  14. V. Koltun and C. H. Papadimitriou, “Approximately dominating representatives,” Theor. Comput. Sci. 371, 148–154 (2007). [CrossRef]
  15. J. Wu, “Extended dominating-set-based routing in ad hoc wireless networks with unidirectional link,” IEEE Trans. Parallel Distrib. Syst. 13, 866–881 (2002). [CrossRef]
  16. S. Misra, I. Woungang, and S. C. Misra, Guide to Wireless Ad Hoc Networks, 2nd ed. (Springer, 2009).
  17. X. Zhou, G. Yue, Z. Yang, and K. Li, “A new approach for the dominating-set problem by DNA-based supercomputing,” J. Software 5, 662–670 (2010). [CrossRef]
  18. H. J. Levinson, Proximity X-ray Lithography, 2nd ed. (SPIE, 2005).

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.


« Previous Article  |  Next Article »

OSA is a member of CrossRef.

CrossCheck Deposited