Solving Minimum Hitting Set Problem and Generalized Exact Cover Problem with Light Based Devices

被引：0

作者：

Hasan, Masud ^{[1
]}

Hossain, Shabab ^{[1
,2
]}

Rahman, Md. Mahmudur ^{[1
,2
]}

Rahman, M. Sohel ^{[1
,3
]}

机构：

[1] BUET, Dept CSE, Dhaka 1000, Bangladesh

[2] UIU, Dept CSE, Dhaka 1209, Bangladesh

[3] Kings Coll London, Dept Comp Sci, London, England

来源：

INTERNATIONAL JOURNAL OF UNCONVENTIONAL COMPUTING | 2011年 / 7卷 / 1-2期

关键词：

light based device; optical computing; NP-Complete problems; ALGORITHMS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We suggest a new way for solving the exact cover and the minimum hitting set problems using massive parallelism of light. The idea is to build an optical device that will generate all possible solution sets and then to select the correct one among those sets. The device has a graph like structure. There are several nodes connected by arcs (optical fibers). The light ray passing through an arc is delayed by some predefined time represented by the number assigned to the arc. The arcs are connected in such a way that the existence of a solution is represented by the arrival of a light signal at the destination at a predefined time.

引用

页码：125 / 140

页数：16

共 20 条

[1] AARONSON S, 2005, TR05026 ECCC
[2] MOLECULAR COMPUTATION OF SOLUTIONS TO COMBINATORIAL PROBLEMS
ADLEMAN, LM
[J]. SCIENCE, 1994, 266 (5187) : 1021 - 1024
[3] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[4] Ausiello G., 1980, J COMP SYS SO, V21
[5] Bringsjord S., 2004, P NP CS CC 0406056
[6] Goodman J. W., 1982, Journal of Electrical and Electronics Engineering, Australia, V2, P139
[7] Hasan M., 2010, NATURAL COM IN PRESS
[8] Hasan M, 2010, PROC INFO COMMUN, V2, P165
[9] Hasan MR, 2009, LECT NOTES COMPUT SC, V5882, P70, DOI 10.1007/978-3-642-10442-8_9
[10] Light speed reduction to 17 metres per second in an ultracold atomic gas
Hau, LV
Harris, SE
Dutton, Z
Behroozi, CH
[J]. NATURE, 1999, 397 (6720) : 594 - 598

← 1 2 →