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 Article

References

  • View by:
  • |
  • |
  • |

  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).

2012 (1)

2011 (2)

C. Qiu and Q. Xu, “Controlling normal incident optical waves with an integrated resonator,” Opt. Express 19, 26905–26910 (2011).
[CrossRef]

S. Goliaei and S. Jalili, “Optical graph 3-colorability,” Lect. Notes Comput. Sci. 6748, 16–22 (2011).
[CrossRef]

2010 (3)

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]

H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261–263 (2010).
[CrossRef]

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]

2009 (2)

S. Goliaei and S. Jalili, “An optical wavelength-based solution to the 3-SAT problem,” Lect. Notes Comput. Sci. 5882, 77–85 (2009).
[CrossRef]

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]

2008 (1)

M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Nat. Comput. 7, 57–70 (2008).
[CrossRef]

2007 (4)

N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP-complete problems,” Appl. Opt. 46, 711–724 (2007).
[CrossRef]

T. Haist, and W. Osten, “An optical solution for the traveling salesman problem,” Opt. Express 15, 10473–10482 (2007).
[CrossRef]

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]

V. Koltun and C. H. Papadimitriou, “Approximately dominating representatives,” Theor. Comput. Sci. 371, 148–154 (2007).
[CrossRef]

2002 (1)

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]

Caulfield, H. J.

H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261–263 (2010).
[CrossRef]

Ding, J.

Dolev, S.

H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261–263 (2010).
[CrossRef]

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]

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]

N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP-complete problems,” Appl. Opt. 46, 711–724 (2007).
[CrossRef]

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]

Fitoussi, H.

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]

Garey, M. R.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st ed. (W. H. Freeman, 1979).

Goliaei, S.

S. Goliaei and S. Jalili, “Optical graph 3-colorability,” Lect. Notes Comput. Sci. 6748, 16–22 (2011).
[CrossRef]

S. Goliaei and S. Jalili, “An optical wavelength-based solution to the 3-SAT problem,” Lect. Notes Comput. Sci. 5882, 77–85 (2009).
[CrossRef]

S. Goliaei and S. Jalili, “An optical solution to the 3-SAT problem using wavelength based selectors,” J. Supercomput. (to be published).

Haist, T.

Jalili, S.

S. Goliaei and S. Jalili, “Optical graph 3-colorability,” Lect. Notes Comput. Sci. 6748, 16–22 (2011).
[CrossRef]

S. Goliaei and S. Jalili, “An optical wavelength-based solution to the 3-SAT problem,” Lect. Notes Comput. Sci. 5882, 77–85 (2009).
[CrossRef]

S. Goliaei and S. Jalili, “An optical solution to the 3-SAT problem using wavelength based selectors,” J. Supercomput. (to be published).

Ji, R.

Johnson, D. S.

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st ed. (W. H. Freeman, 1979).

Koltun, V.

V. Koltun and C. H. Papadimitriou, “Approximately dominating representatives,” Theor. Comput. Sci. 371, 148–154 (2007).
[CrossRef]

Levinson, H. J.

H. J. Levinson, Proximity X-ray Lithography, 2nd ed. (SPIE, 2005).

Li, K.

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]

Messika, S.

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]

N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP-complete problems,” Appl. Opt. 46, 711–724 (2007).
[CrossRef]

Misra, S.

S. Misra, I. Woungang, and S. C. Misra, Guide to Wireless Ad Hoc Networks, 2nd ed. (Springer, 2009).

Misra, S. C.

S. Misra, I. Woungang, and S. C. Misra, Guide to Wireless Ad Hoc Networks, 2nd ed. (Springer, 2009).

Oltean, M.

M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Nat. Comput. 7, 57–70 (2008).
[CrossRef]

Osten, W.

Papadimitriou, C. H.

V. Koltun and C. H. Papadimitriou, “Approximately dominating representatives,” Theor. Comput. Sci. 371, 148–154 (2007).
[CrossRef]

Qiu, C.

Rosen, J.

N. T. Shaked, S. Messika, S. Dolev, and J. Rosen, “Optical solution for bounded NP-complete problems,” Appl. Opt. 46, 711–724 (2007).
[CrossRef]

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]

Shaked, N. T.

Simon, G.

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]

Tabib, T.

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]

Tamir, D. E.

Wilson, P. J.

Woungang, I.

S. Misra, I. Woungang, and S. C. Misra, Guide to Wireless Ad Hoc Networks, 2nd ed. (Springer, 2009).

Wu, J.

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]

Xu, Q.

Yang, L.

Yang, Z.

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]

Yue, G.

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]

Zhang, L.

Zhou, X.

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]

Appl. Opt. (1)

IEEE Trans. Parallel Distrib. Syst. (1)

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]

J. Opt. Soc. Am. A (1)

J. Software (1)

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]

Lect. Notes Comput. Sci. (2)

S. Goliaei and S. Jalili, “An optical wavelength-based solution to the 3-SAT problem,” Lect. Notes Comput. Sci. 5882, 77–85 (2009).
[CrossRef]

S. Goliaei and S. Jalili, “Optical graph 3-colorability,” Lect. Notes Comput. Sci. 6748, 16–22 (2011).
[CrossRef]

Nat. Comput. (1)

M. Oltean, “Solving the Hamiltonian path problem with a light-based computer,” Nat. Comput. 7, 57–70 (2008).
[CrossRef]

Nat. Photonics (1)

H. J. Caulfield and S. Dolev, “Why future supercomputing requires optics,” Nat. Photonics 4, 261–263 (2010).
[CrossRef]

Opt. Eng. (1)

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]

Opt. Express (3)

Theor. Comput. Sci. (2)

V. Koltun and C. H. Papadimitriou, “Approximately dominating representatives,” Theor. Comput. Sci. 371, 148–154 (2007).
[CrossRef]

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]

Other (4)

M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1st ed. (W. H. Freeman, 1979).

S. Goliaei and S. Jalili, “An optical solution to the 3-SAT problem using wavelength based selectors,” J. Supercomput. (to be published).

S. Misra, I. Woungang, and S. C. Misra, Guide to Wireless Ad Hoc Networks, 2nd ed. (Springer, 2009).

H. J. Levinson, Proximity X-ray Lithography, 2nd ed. (SPIE, 2005).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (7)

Fig. 1.
Fig. 1.

Example of a graph that has several 2-vertex dominating sets.

Fig. 2.
Fig. 2.

Example of a graph with no 2-vertex dominating set.

Fig. 3.
Fig. 3.

Finding the intersection of two filters.

Fig. 4.
Fig. 4.

Finding the union of two filters.

Fig. 5.
Fig. 5.

Examples of bit filters.

Fig. 6.
Fig. 6.

Examples of the implemented filters to solve the DSP on a graph with six vertices. (a) Φ0, (b) Φ1, (c) Φ2.

Fig. 7.
Fig. 7.

Examples of the implemented filters to solve the DSP on a graph with six vertices. (a) Ψ0, (b) Ψ1, (c) Ψ2, (d) Ψ3, (e) Ψ4, (f) Ψ5, (g) Γ.

Equations (14)

Equations on this page are rendered with MathJax. Learn more.

Φs=(ϒ1s2ϒ2s1ϒ3s0)(ϒ4s2ϒ5s1ϒ6s0).
Φ0=(ϒ10ϒ20ϒ30)(ϒ40ϒ50ϒ60),
Φ1=(ϒ10ϒ20ϒ31)(ϒ40ϒ50ϒ61),
Φ2=(ϒ10ϒ21ϒ30)(ϒ40ϒ51ϒ60),
Φ3=(ϒ10ϒ21ϒ31)(ϒ40ϒ51ϒ61),
Φ4=(ϒ11ϒ20ϒ30)(ϒ41ϒ50ϒ60),
Φ5=(ϒ11ϒ20ϒ31)(ϒ41ϒ50ϒ61).
Ψ0=Φ0Φ1Φ2,
Ψ1=Φ0Φ1Φ2Φ3Φ4,
Ψ2=Φ0Φ1Φ2Φ4Φ5,
Ψ3=Φ1Φ3Φ4,
Ψ4=Φ1Φ2Φ3Φ4Φ5,
Ψ5=Φ2Φ4Φ5.
Γ=Ψ0Ψ1Ψ2Ψ3Ψ4Ψ5.

Metrics