Publikationsansicht

Molecular Computation Of Solutions To Combinatorial Problems (1994)

Abstract

this report the possibility of computing directly with molecules is explored. A directed graph G with designated vertices v in and v out , is said to have a Hamiltonian path (2) if and only if there exists a sequence of compatible `one way' edges e 1 ; e 2 ; :::; e z (that is, a `path') which begins at v in , ends at v out and enters every other vertex exactly once. Figure 1 shows a graph which for v in = 0 and v out = 6 has a Hamiltonian path, given by the edges 0!1,1!2,2!3,3!4,4!5,5!6. If the edge 2!3 were removed from the graph then the resulting graph with the same designated vertices would not have a Hamiltonian path. Similarly if the designated vertices were changed to v in = 3, v out = 5 there would be no Hamiltonian path (since for example there are no edges entering vertex 0). There are well known algorithms for deciding whether an arbitrary directed graph with designated vertices has a Hamiltonian path or not. However, all Adleman 4 known algorithms for this problem have exponential worst-case complexity and hence there are instances of modest size for which these algorithms require an impractical amount of computer time to render a decision. Since the directed Hamiltonian path problem has been proven to be NP-complete, it seem likely that no efficient (that is, polynomial time) algorithm exists for solving it (2,3). The following (non-deterministic) algorithm solves the directed Hamiltonian path problem: ffl Step 1: Generate random paths through the graph. ffl Step 2: Keep only those paths which begin with v in and end with v out . ffl Step 3: If the graph has n vertices, then keep only those paths which enter exactly n vertices. ffl Step 4: Keep only those paths which enter all of the vertices of the graph at least once. ffl Step 5: If any paths remain, sa...

Details der Publikation

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.2565
Quelle	ftp://ftp.krl.caltech.edu/pub/users/brown/adleman.ps.gz
Mitarbeiter	CiteSeerX
Archiv	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Typ	text
Sprache	Englisch
Verknüpfungen	10.1.1.17.5821, 10.1.1.45.144, 10.1.1.50.7037, 10.1.1.76.8425, 10.1.1.47.6982, 10.1.1.68.2237, 10.1.1.49.7537, 10.1.1.34.3677, 10.1.1.17.1806, 10.1.1.49.4409, 10.1.1.54.8878, 10.1.1.40.2271, 10.1.1.47.451, 10.1.1.55.2306, 10.1.1.31.1765, 10.1.1.31.2532, 10.1.1.33.2193, 10.1.1.42.2568, 10.1.1.27.9656, 10.1.1.38.6998, 10.1.1.55.1003, 10.1.1.31.744, 10.1.1.53.1991, 10.1.1.39.2542, 10.1.1.48.775, 10.1.1.16.6487, 10.1.1.46.4669, 10.1.1.48.44, 10.1.1.38.569, 10.1.1.19.1000, 10.1.1.32.8076, 10.1.1.17.4208, 10.1.1.130.8807, 10.1.1.51.9800, 10.1.1.9.2547, 10.1.1.40.9610, 10.1.1.16.8629, 10.1.1.74.103, 10.1.1.41.7980, 10.1.1.50.2121, 10.1.1.35.5804, 10.1.1.27.2721, 10.1.1.33.149, 10.1.1.46.6794, 10.1.1.125.8263, 10.1.1.89.6640, 10.1.1.56.5552, 10.1.1.52.7003, 10.1.1.26.3822, 10.1.1.56.8740, 10.1.1.1.5588, 10.1.1.24.2571, 10.1.1.39.7652, 10.1.1.134.3493, 10.1.1.73.6284, 10.1.1.74.8804, 10.1.1.76.8401, 10.1.1.91.8094, 10.1.1.16.9589, 10.1.1.17.5110, 10.1.1.21.76, 10.1.1.23.6564, 10.1.1.30.1301, 10.1.1.38.8054, 10.1.1.48.3912, 10.1.1.48.507, 10.1.1.49.1980, 10.1.1.49.2095, 10.1.1.56.5728, 10.1.1.57.1954, 10.1.1.30.8180, 10.1.1.50.6496, 10.1.1.56.9070, 10.1.1.50.3347, 10.1.1.45.5005, 10.1.1.54.641, 10.1.1.55.62, 10.1.1.103.4746, 10.1.1.16.6837, 10.1.1.39.4194, 10.1.1.71.6381, 10.1.1.107.9736, 10.1.1.42.7369, 10.1.1.45.5316, 10.1.1.60.1081, 10.1.1.48.405, 10.1.1.100.965, 10.1.1.101.5131, 10.1.1.29.1639, 10.1.1.42.3056, 10.1.1.46.7306, 10.1.1.48.4737, 10.1.1.49.6218, 10.1.1.51.196, 10.1.1.7.8342, 10.1.1.86.1557, 10.1.1.88.2433, 10.1.1.48.6191, 10.1.1.54.6496, 10.1.1.43.8369, 10.1.1.60.5811, 10.1.1.36.927, 10.1.1.83.8703, 10.1.1.94.2366, 10.1.1.126.3491, 10.1.1.38.4654, 10.1.1.4.4632, 10.1.1.34.6453, 10.1.1.36.5442, 10.1.1.36.5923, 10.1.1.67.2087, 10.1.1.87.1079, 10.1.1.97.2228, 10.1.1.38.9696, 10.1.1.49.9209, 10.1.1.54.3028, 10.1.1.103.1078, 10.1.1.105.3714, 10.1.1.17.5526, 10.1.1.17.852, 10.1.1.18.8686, 10.1.1.29.1701, 10.1.1.41.8806, 10.1.1.47.1595, 10.1.1.49.4626, 10.1.1.41.5900, 10.1.1.58.8467, 10.1.1.67.5435, 10.1.1.8.1360, 10.1.1.83.4735, 10.1.1.99.2923, 10.1.1.45.9213, 10.1.1.132.3410, 10.1.1.49.3096, 10.1.1.41.2520, 10.1.1.41.2235, 10.1.1.41.1725, 10.1.1.42.3127, 10.1.1.43.828, 10.1.1.32.7331, 10.1.1.26.8044, 10.1.1.24.8057, 10.1.1.101.5236, 10.1.1.106.3979, 10.1.1.107.5741, 10.1.1.23.190, 10.1.1.39.6148, 10.1.1.41.8807, 10.1.1.89.7619, 10.1.1.42.8657, 10.1.1.43.9364, 10.1.1.47.7135, 10.1.1.50.9165, 10.1.1.52.3647, 10.1.1.6.7855, 10.1.1.62.1686, 10.1.1.62.6884, 10.1.1.63.3822, 10.1.1.65.4242, 10.1.1.69.1052, 10.1.1.73.7556, 10.1.1.76.7326, 10.1.1.78.227, 10.1.1.80.740, 10.1.1.35.6557, 10.1.1.84.8411, 10.1.1.91.8827, 10.1.1.118.6102, 10.1.1.129.2712, 10.1.1.31.2452, 10.1.1.52.2832, 10.1.1.47.3675, 10.1.1.18.3858, 10.1.1.41.3956, 10.1.1.35.8849, 10.1.1.37.6865, 10.1.1.32.9299, 10.1.1.28.4552, 10.1.1.22.2736, 10.1.1.23.3569, 10.1.1.18.4489, 10.1.1.18.7674, 10.1.1.12.4768, 10.1.1.6.4802, 10.1.1.6.4231, 10.1.1.140.1791, 10.1.1.10.9389, 10.1.1.100.143, 10.1.1.100.2189, 10.1.1.100.6496, 10.1.1.101.3697, 10.1.1.102.8561, 10.1.1.104.151, 10.1.1.104.1700, 10.1.1.104.4164, 10.1.1.104.4637, 10.1.1.104.6296, 10.1.1.105.5483, 10.1.1.105.8816, 10.1.1.106.2137, 10.1.1.101.527, 10.1.1.106.9522, 10.1.1.107.6863, 10.1.1.108.1555, 10.1.1.109.1178, 10.1.1.109.5796, 10.1.1.109.5812, 10.1.1.11.3148, 10.1.1.13.1911, 10.1.1.25.3119, 10.1.1.26.8084, 10.1.1.28.4193, 10.1.1.29.3449, 10.1.1.33.2346, 10.1.1.40.1863, 10.1.1.40.7897, 10.1.1.41.8510, 10.1.1.42.6228, 10.1.1.42.9134, 10.1.1.45.1781, 10.1.1.45.3834, 10.1.1.46.8942, 10.1.1.47.9633, 10.1.1.5.2600, 10.1.1.50.1473, 10.1.1.50.9499, 10.1.1.55.8324, 10.1.1.57.8626, 10.1.1.62.1509, 10.1.1.62.4176, 10.1.1.62.5248, 10.1.1.63.9566, 10.1.1.64.3557, 10.1.1.64.4423, 10.1.1.62.7488, 10.1.1.65.6345, 10.1.1.120.4925, 10.1.1.65.915, 10.1.1.66.2173, 10.1.1.66.3177, 10.1.1.66.4330, 10.1.1.66.5294, 10.1.1.66.5353, 10.1.1.66.8599, 10.1.1.67.4448, 10.1.1.67.5259, 10.1.1.67.6662, 10.1.1.67.706, 10.1.1.68.3223, 10.1.1.68.3864, 10.1.1.69.1924, 10.1.1.69.2821, 10.1.1.69.6398, 10.1.1.70.2977, 10.1.1.70.7716, 10.1.1.118.8371, 10.1.1.71.1420, 10.1.1.72.1182, 10.1.1.72.6217, 10.1.1.72.7609, 10.1.1.72.9979, 10.1.1.73.6313, 10.1.1.73.6513, 10.1.1.73.7070, 10.1.1.73.7450, 10.1.1.73.8914, 10.1.1.74.1999, 10.1.1.74.1309, 10.1.1.74.888, 10.1.1.67.3700, 10.1.1.116.3069, 10.1.1.75.6037, 10.1.1.76.3881, 10.1.1.76.890, 10.1.1.76.9923, 10.1.1.77.3611, 10.1.1.78.3711, 10.1.1.78.4316, 10.1.1.78.8391, 10.1.1.78.9047, 10.1.1.78.9605, 10.1.1.79.2232, 10.1.1.16.2639, 10.1.1.79.3334, 10.1.1.79.3422, 10.1.1.113.5467, 10.1.1.79.804, 10.1.1.80.1643, 10.1.1.80.7200, 10.1.1.81.1447, 10.1.1.83.2995, 10.1.1.83.7607, 10.1.1.84.5034, 10.1.1.84.5839, 10.1.1.84.6739, 10.1.1.84.7654, 10.1.1.85.5166, 10.1.1.85.6212, 10.1.1.85.883, 10.1.1.86.1718, 10.1.1.86.5710, 10.1.1.86.8580, 10.1.1.88.1928, 10.1.1.88.2143, 10.1.1.88.4026, 10.1.1.89.2401, 10.1.1.89.6121, 10.1.1.89.6455, 10.1.1.90.7093, 10.1.1.90.7903, 10.1.1.123.2504, 10.1.1.92.1878, 10.1.1.134.7115, 10.1.1.92.424, 10.1.1.92.8877, 10.1.1.93.6746, 10.1.1.94.7757, 10.1.1.94.9162, 10.1.1.94.9958, 10.1.1.95.4341, 10.1.1.95.4874, 10.1.1.95.4960, 10.1.1.95.914, 10.1.1.96.5461, 10.1.1.96.8219, 10.1.1.96.9966, 10.1.1.97.2119, 10.1.1.97.3740, 10.1.1.97.6710, 10.1.1.97.782, 10.1.1.98.3231, 10.1.1.98.5704, 10.1.1.98.6793, 10.1.1.99.4412, 10.1.1.99.6347, 10.1.1.99.9540, 10.1.1.111.6438, 10.1.1.112.9638, 10.1.1.113.260, 10.1.1.113.3645, 10.1.1.113.8214, 10.1.1.114.5570, 10.1.1.114.9190, 10.1.1.115.1357, 10.1.1.117.630, 10.1.1.117.2888, 10.1.1.120.2114, 10.1.1.120.2340, 10.1.1.120.3121, 10.1.1.121.9035, 10.1.1.121.9508, 10.1.1.122.644, 10.1.1.122.3048, 10.1.1.124.4402, 10.1.1.125.6058, 10.1.1.125.8409, 10.1.1.127.7028, 10.1.1.128.7086, 10.1.1.129.2737, 10.1.1.129.5476, 10.1.1.133.348, 10.1.1.133.1587, 10.1.1.134.6885, 10.1.1.135.2330, 10.1.1.136.7482, 10.1.1.137.904, 10.1.1.137.9576, 10.1.1.138.2888, 10.1.1.138.3195, 10.1.1.138.4932, 10.1.1.139.1282, 10.1.1.49.8402, 10.1.1.55.7231, 10.1.1.48.289, 10.1.1.53.9106, 10.1.1.54.268, 10.1.1.17.4987, 10.1.1.55.1843, 10.1.1.33.3182, 10.1.1.42.9746, 10.1.1.29.3063, 10.1.1.52.2212, 10.1.1.35.9507, 10.1.1.17.9886, 10.1.1.45.2067, 10.1.1.39.513, 10.1.1.46.4496, 10.1.1.46.6580, 10.1.1.46.8118, 10.1.1.39.3208, 10.1.1.39.2151, 10.1.1.40.3999, 10.1.1.40.5862, 10.1.1.40.6568, 10.1.1.40.9653, 10.1.1.41.2109, 10.1.1.41.3009, 10.1.1.41.4188, 10.1.1.41.9527, 10.1.1.34.7790, 10.1.1.35.1145, 10.1.1.35.8696, 10.1.1.36.6481, 10.1.1.37.6984, 10.1.1.38.3680, 10.1.1.29.9196, 10.1.1.30.613, 10.1.1.30.5137, 10.1.1.30.6653, 10.1.1.31.1921, 10.1.1.27.728, 10.1.1.27.1669, 10.1.1.27.2158, 10.1.1.22.9956, 10.1.1.16.9118, 10.1.1.16.9636, 10.1.1.17.2760, 10.1.1.20.4798, 10.1.1.15.7255, 10.1.1.4.3742, 10.1.1.4.7580, 10.1.1.5.6896, 10.1.1.6.183, 10.1.1.58.5672, 10.1.1.1.5393, 10.1.1.1.9297, 10.1.1.60.4307, 10.1.1.61.421, 10.1.1.61.5470, 10.1.1.61.5913, 10.1.1.140.3339