644:
757:. The time it takes to render the object is dependent on the rate at which the input is received, meaning the larger the input the longer the rendering time. For triangle meshes, however, the rendering time can be decreased by up to a factor of three. This is done through "ordering the triangles so that consecutive triangles share a face." That way, only one vertex changes between each consecutive triangle. This ordering exists if the
771:
368:
proceeds, a set of decision rules classifies the undecided edges, and determines whether to halt or continue the search. Edges that cannot be in the path can be eliminated, so the search gets continually smaller. The algorithm also divides the graph into components that can be solved separately, greatly reducing the search size. In practice, this algorithm is still the fastest.
520:
An optical solution to the
Hamiltonian problem has been proposed as well. The idea is to create a graph-like structure made from optical cables and beam splitters which are traversed by light in order to construct a solution for the problem. The weak point of this approach is the required amount of
367:
An early exact algorithm for finding a
Hamiltonian cycle on a directed graph was the enumerative algorithm of Martello. A search procedure by Frank Rubin divides the edges of the graph into three classes: those that must be in the path, those that cannot be in the path, and undecided. As the search
681:
To decide this, the algorithm first verifies that all of the vertices in G appear exactly once in c. If this check passes, next, the algorithm will ensure that the first vertex in c is equal to s and the last vertex is equal to t. Lastly, to verify that c is a valid path, the algorithm must check
685:
The algorithm can check in polynomial time if the vertices in G appear once in c. Additionally, it takes polynomial time to check the start and end vertices, as well as the edges between vertices. Therefore, the algorithm is a polynomial time verifier for the
Hamiltonian path problem.
606:
Tutte proved this result by showing that every 2-connected planar graph contains a Tutte path. Tutte paths in turn can be computed in quadratic time even for 2-connected planar graphs, which may be used to find
Hamiltonian cycles and long cycles in generalizations of planar
456:
to reduce the problem of counting the number of
Hamiltonian cycles to a simpler counting problem, of counting cycle covers, which can be solved by computing certain matrix determinants. Using this method, he showed how to solve the Hamiltonian cycle problem in arbitrary
517:. Exploiting the parallelism inherent in chemical reactions, the problem may be solved using a number of chemical reaction steps linear in the number of vertices of the graph; however, it requires a factorial number of DNA molecules to participate in the reaction.
623:
shows that the number of
Hamiltonian cycles through any fixed edge is always even, so if one Hamiltonian cycle is given, then a second one must also exist. However, finding this second cycle does not seem to be an easy computational task.
611:
Putting all of these conditions together, it remains open whether 3-connected 3-regular bipartite planar graphs must always contain a
Hamiltonian cycle, in which case the problem restricted to those graphs could not be NP-complete; see
509:
Because of the difficulty of solving the
Hamiltonian path and cycle problems on conventional computers, they have also been studied in unconventional models of computing. For instance,
263:
321:
19:
This article is about the specific problem of determining whether a
Hamiltonian path or cycle exists in a given graph. For the general graph theory concepts, see
80:, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to
155:. Thus, finding a Hamiltonian path cannot be significantly slower (in the worst case, as a function of the number of vertices) than finding a Hamiltonian cycle.
666:
for
Hamiltonian path will take as input a graph G, starting vertex s, and ending vertex t. Additionally, verifiers require a potential solution known as a
57:, a path that visits every vertex in the graph exactly once. The problem may specify the start and end of the path, in which case the starting vertex
1707:
682:
that every edge between vertices in c is indeed an edge in G. If any of these checks fail, the algorithm will reject. Otherwise, it will accept.
674:
of vertices where the first vertex is the start of the proposed path and the last is the end. The algorithm will determine if c is a valid
600:
599:, and the computational task of finding a Hamiltonian cycle in these graphs can be carried out in linear time by computing a so-called
775:
1411:
Chiba, Norishige; Nishizeki, Takao (1989), "The Hamiltonian cycle problem is linear-time solvable for 4-connected planar graphs",
1503:
481:
For graphs of maximum degree three, a careful backtracking search can find a Hamiltonian cycle (if one exists) in time O(1.251).
1645:
Bahrebar, P.; Stroobandt, D. (2014). "Improving hamiltonian-based routing methods for on-chip networks: A turn model approach".
1712:
1629:
1395:
1069:
1032:
537:
is to test whether a Hamiltonian cycle or path exists. The directed and undirected Hamiltonian cycle problems were two of
339:
To decide if a graph has a Hamiltonian path, one would have to check each possible path in the input graph G. There are
1056:, Lecture Notes in Computer Science, vol. 4598, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 108–117,
1474:
538:
453:
108:
706:
serving as communication for on-chip components. The performance of NoC is determined by the method it uses to move
501:. As a result, finding a solution to the Hamiltonian Path problem is equivalent to finding a solution for 3-SAT.
31:
1264:
76:. This problem may also specify the start of the cycle. The Hamiltonian cycle problem is a special case of the
1439:
Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), to appear.
1702:
738:
100:
46:
207:
723:
77:
1554:
276:
1295:; Saito, Nobuji (1980–1981), "NP-completeness of the Hamiltonian cycle problem for bipartite graphs",
1324:
671:
1517:
1338:
1256:
722:
to each end node and send packets across the corresponding path. Utilizing this strategy guarantees
1378:
1117:
667:
613:
592:
183:
1609:
1322:
Itai, Alon; Papadimitriou, Christos; Szwarcfiter, Jayme (1982), "Hamilton Paths in Grid Graphs",
750:
470:
1458:
1452:
1512:
1498:
1373:
1333:
1257:"The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two"
1112:
718:. Path-based multicast algorithms will determine if there is a Hamiltonian path from the start
625:
578:
1501:(1994), "On the complexity of the parity argument and other inefficient proofs of existence",
124:
The problems of finding a Hamiltonian path and a Hamiltonian cycle can be related as follows:
1572:
703:
462:
167:
1676:
1534:
1484:
1363:"Simple Amazons endgames and their connection to Hamilton circuits in cubic subgrid graphs"
1308:
1104:
588:
However, for some special classes of graphs, the problem can be solved in polynomial time:
494:
1590:
1454:
Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977)
8:
381:
377:
1108:
1049:
1237:
1161:
1130:
1010:
944:
896:
877:
356:
72:
is similar to the Hamiltonian path problem, except it asks if a given graph contains a
1526:
1466:
87:
The Hamiltonian path problem and the Hamiltonian cycle problem belong to the class of
1625:
1470:
1424:
1391:
1277:
1241:
1138:
1095:
1065:
1028:
983:
936:
846:
746:
719:
715:
699:
620:
73:
948:
444:), which can be looked up from already-computed information in the dynamic program.
1617:
1522:
1462:
1420:
1383:
1343:
1273:
1229:
1221:
1217:
1171:
1122:
1057:
1020:
975:
926:
900:
886:
838:
711:
675:
632:
629:
561:
534:
530:
141:
96:
54:
43:
20:
1451:
Thomason, A. G. (1978), "Hamiltonian cycles and uniquely edge colourable graphs",
1621:
1530:
1480:
1304:
1292:
1190:"Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete"
1093:(November 1994), "Molecular computation of solutions to combinatorial problems",
1090:
1061:
656:
652:
568:
545:
510:
466:
104:
88:
647:
The proposed solution {s,w,v,u,t} forms a valid Hamiltonian Path in the graph G.
707:
352:
39:
1696:
1387:
1213:
987:
940:
850:
565:
514:
92:
1616:. Lecture Notes in Electrical Engineering. Vol. 790. pp. 431–440.
1126:
963:
714:. The Hamiltonian Path problem can be implemented as a path-based method in
619:
In graphs in which all vertices have odd degree, an argument related to the
1614:
Emerging Research in Computing, Information, Communication and Applications
1610:"Comparative Performance Analysis of Routing Topology for NoC Architecture"
875:
Rubin, Frank (1974), "A Search Procedure for Hamilton Paths and Circuits",
863:
754:
643:
552:
35:
1675:
Arkin, Esther M.; Mitchell, Joseph S. B.; Held, Martin; Skiena, Steven S.
1362:
1233:
1142:
1002:
931:
914:
891:
1024:
596:
1647:
2014 Design, Automation & Test in Europe Conference & Exhibition
1175:
826:
1372:, Lecture Notes in Computer Science, vol. 2063, pp. 250–261,
1189:
1134:
842:
758:
490:
119:
809:
Computers and Intractability: A Guide to the Theory of NP-Completeness
101:
Computers and Intractability: A Guide to the Theory of NP-Completeness
663:
541:. They remain NP-complete even for special kinds of graphs, such as:
1347:
979:
1661:
1437:
Schmid, Andreas; Schmidt, Jens M. (2018), "Computing Tutte Paths",
742:
727:
1166:
1160:. Unconventional Computing. Springer LNCS 4135. pp. 217–227.
1015:
1007:
2010 IEEE 51st Annual Symposium on Foundations of Computer Science
915:"Dynamic Programming Treatment of the Travelling Salesman Problem"
158:
In the other direction, the Hamiltonian cycle problem for a graph
359:
algorithm that tests all possible sequences would be very slow.
770:
558:
directed planar graphs with indegree and outdegree at most two,
513:
showed that the Hamiltonian path problem may be solved using a
400:, whether there is a path that covers exactly the vertices in
1158:
A light-based device for solving the Hamiltonian path problem
968:
Journal of the Society for Industrial and Applied Mathematics
827:"The construction of discrete dynamic programming algorithms"
498:
452:
Andreas Björklund provided an alternative approach using the
1321:
670:, c. For the Hamiltonian Path problem, c would consist of a
1048:
Iwama, Kazuo; Nakashima, Takuya (2007), Lin, Guohui (ed.),
162:
is equivalent to the Hamiltonian path problem in the graph
132:
can be related to the Hamiltonian cycle problem in a graph
1290:
16:
Problem of finding a cycle through all vertices of a graph
1226:
Proc. 6th ACM Symposium on Theory of Computing (STOC '74)
529:
The problem of finding a Hamiltonian cycle or path is in
128:
In one direction, the Hamiltonian path problem for graph
1457:, Annals of Discrete Mathematics, vol. 3, pp.
595:
planar graphs are always Hamiltonian by a result due to
493:. The Hamiltonian path is NP-Complete meaning it can be
964:"A Dynamic Programming Approach to Sequencing Problems"
1212:
753:
graphics rendering, a common input to the engine is a
1684:
Department of Computer Science Stony Brook University
279:
210:
864:
Reduction from Hamiltonian cycle to Hamiltonian path
761:
of the triangular mesh contains a Hamiltonian path.
730:
free routing, increasing the efficiency of the NoC.
521:
energy which is exponential in the number of nodes.
120:
Reduction from the path problem to the cycle problem
1674:
1573:"University of Toronto CSCC63 Week 7 Lecture Notes"
1149:
820:
818:
796:(3rd ed.). Cengage Learning. pp. 292–314.
1644:
749:to generate images or models from input data. In
315:
257:
1050:"An Improved Exact Algorithm for Cubic Graph TSP"
388:2). In this method, one determines, for each set
1694:
1224:(1974), "Some simplified NP-complete problems",
815:
178:attached respectively to a vertex v of G and to
1677:"Hamiltonian Triangulations for Fast Rendering"
1003:"Determinant Sums for Undirected Hamiltonicity"
655:meaning a proposed solution can be verified in
469:this algorithm can be further improved to time
1410:
1047:
962:Held, Michael; Karp, Richard M. (March 1962).
1660:Garsiel, Tali; Irish, Paul (August 5, 2011).
1497:
1436:
1659:
1155:
807:Garey, Michael R; Johnson, David S. (1979).
806:
638:
384:can be used to solve the problem in time O(
635:to encapsulate problems such as this one.
1570:
1555:"Boston University Theory of Computation"
1516:
1377:
1337:
1165:
1116:
1014:
1000:
930:
890:
794:Introduction to the Theory of Computation
584:cubic subgraphs of the square grid graph.
504:
484:
84:If so, the route is a Hamiltonian cycle.
1450:
961:
824:
811:. W. H. Freeman and Company. p. 60.
642:
267:corresponds to the Hamiltonian cycle in
1504:Journal of Computer and System Sciences
1254:
1089:
912:
702:(NoC) are used in computer systems and
574:3-connected 3-regular bipartite graphs,
489:Hamiltonian paths can be found using a
343:! different sequences of vertices that
1708:Computational problems in graph theory
1695:
1607:
791:
371:
30:is a topic discussed in the fields of
1548:
1546:
1544:
874:
787:
785:
1360:
733:
258:{\displaystyle s-v-x-\cdots -y-v'-t}
1552:
1001:Bjorklund, Andreas (October 2010).
694:
13:
1541:
782:
14:
1724:
1571:Bretscher, A (February 5, 2021).
1297:Journal of Information Processing
913:Bellman, Richard (January 1962).
316:{\displaystyle v-x-\cdots -y(-v)}
1588:
769:
651:The Hamiltonian path problem is
362:
347:be Hamiltonian paths in a given
1668:
1653:
1638:
1601:
1595:University Of California Irvine
1582:
1564:
1491:
1444:
1430:
1404:
1354:
1315:
1284:
1248:
1206:
1194:Computer Science Stack Exchange
1182:
1083:
689:
476:
1265:Information Processing Letters
1041:
994:
955:
906:
868:
857:
825:Held, M.; Karp, R. M. (1965).
800:
539:Karp's 21 NP-complete problems
447:
334:
310:
301:
1:
1591:"Overview of Network-on-Chip"
1527:10.1016/S0022-0000(05)80063-7
1467:10.1016/S0167-5060(08)70511-9
764:
524:
454:inclusion–exclusion principle
432:such that a path exists for (
351:-vertex graph (and are, in a
329:
166:obtained by adding terminal (
114:
1713:Hamiltonian paths and cycles
1622:10.1007/978-981-16-1342-5_34
1425:10.1016/0196-6774(89)90012-6
1278:10.1016/0020-0190(79)90023-1
1062:10.1007/978-3-540-73545-8_13
392:of vertices and each vertex
7:
1553:Bun, Mark (November 2022).
1054:Computing and Combinatorics
78:travelling salesman problem
10:
1729:
1499:Papadimitriou, Christos H.
1009:. IEEE. pp. 173–182.
198:. The Hamiltonian path in
194:the same neighbourhood as
18:
1325:SIAM Journal on Computing
202:running through vertices
70:Hamiltonian cycle problem
1388:10.1007/3-540-45579-5_17
792:Sipser, Michael (2013).
776:Hamiltonian path problem
678:in G and if so, accept.
639:Polynomial time verifier
555:of maximum degree three,
28:Hamiltonian path problem
1649:: 1–4 – via IEEE.
1127:10.1126/science.7973651
382:Bellman, Held, and Karp
109:21 NP-complete problems
1608:Satish, E. G. (2022).
1361:Buro, Michael (2001),
741:engines are a form of
648:
505:Unconventional methods
485:Boolean satisfiability
465:in time O(1.657); for
317:
259:
91:problems, as shown in
1634:– via Springer.
1413:Journal of Algorithms
1234:10.1145/800119.803884
1156:Mihai Oltean (2006).
932:10.1145/321105.321111
892:10.1145/321850.321854
778:at Wikimedia Commons
646:
614:Barnette's conjecture
463:Monte Carlo algorithm
416:, a path exists for (
408:. For each choice of
318:
260:
1703:NP-complete problems
1255:Plesńik, J. (1979),
1025:10.1109/focs.2010.24
564:undirected planar 3-
461:-vertex graphs by a
277:
208:
65:must be identified.
1662:"How Browsers Work"
1370:Computers and Games
1291:Akiyama, Takanori;
1176:10.1007/11839132_18
1109:1994Sci...266.1021A
1103:(5187): 1021–1024,
831:IBM Systems Journal
378:dynamic programming
372:Dynamic programming
151:to all vertices of
1228:, pp. 47–63,
919:Journal of the ACM
878:Journal of the ACM
843:10.1147/sj.42.0136
649:
357:brute force search
313:
255:
97:David S. Johnson's
61:and ending vertex
38:. It decides if a
1631:978-981-16-1341-8
1397:978-3-540-43080-3
1071:978-3-540-73544-1
1034:978-1-4244-8525-3
774:Media related to
751:three dimensional
747:computer graphics
734:Computer graphics
716:multicast routing
710:of data across a
621:handshaking lemma
579:square grid graph
577:subgraphs of the
424:) if and only if
74:Hamiltonian cycle
32:complexity theory
1720:
1688:
1687:
1681:
1672:
1666:
1665:
1657:
1651:
1650:
1642:
1636:
1635:
1605:
1599:
1598:
1586:
1580:
1579:
1577:
1568:
1562:
1561:
1559:
1550:
1539:
1537:
1520:
1495:
1489:
1487:
1448:
1442:
1441:
1434:
1428:
1427:
1408:
1402:
1400:
1381:
1367:
1358:
1352:
1350:
1341:
1319:
1313:
1311:
1293:Nishizeki, Takao
1288:
1282:
1280:
1261:
1252:
1246:
1244:
1210:
1204:
1203:
1201:
1200:
1186:
1180:
1179:
1169:
1153:
1147:
1145:
1120:
1091:Adleman, Leonard
1087:
1081:
1080:
1079:
1078:
1045:
1039:
1038:
1018:
998:
992:
991:
959:
953:
952:
934:
910:
904:
903:
894:
872:
866:
861:
855:
854:
822:
813:
812:
804:
798:
797:
789:
773:
700:Networks on chip
695:Networks on chip
676:Hamiltonian Path
630:complexity class
569:bipartite graphs
546:bipartite graphs
535:decision problem
533:; the analogous
467:bipartite graphs
324:
322:
320:
319:
314:
271:running through
266:
264:
262:
261:
256:
248:
142:universal vertex
140:by adding a new
55:Hamiltonian path
21:Hamiltonian path
1728:
1727:
1723:
1722:
1721:
1719:
1718:
1717:
1693:
1692:
1691:
1679:
1673:
1669:
1658:
1654:
1643:
1639:
1632:
1606:
1602:
1587:
1583:
1575:
1569:
1565:
1557:
1551:
1542:
1518:10.1.1.321.7008
1496:
1492:
1477:
1449:
1445:
1435:
1431:
1409:
1405:
1398:
1365:
1359:
1355:
1348:10.1137/0211056
1339:10.1.1.383.1078
1332:(11): 676–686,
1320:
1316:
1289:
1285:
1259:
1253:
1249:
1211:
1207:
1198:
1196:
1188:
1187:
1183:
1154:
1150:
1088:
1084:
1076:
1074:
1072:
1046:
1042:
1035:
999:
995:
980:10.1137/0110015
960:
956:
911:
907:
873:
869:
862:
858:
823:
816:
805:
801:
790:
783:
767:
736:
697:
692:
657:polynomial time
641:
527:
511:Leonard Adleman
507:
495:mapping reduced
487:
479:
450:
428:has a neighbor
374:
365:
337:
332:
278:
275:
274:
272:
241:
209:
206:
205:
203:
170:-one) vertices
122:
117:
24:
17:
12:
11:
5:
1726:
1716:
1715:
1710:
1705:
1690:
1689:
1667:
1652:
1637:
1630:
1600:
1589:Bahn, Jun Ho.
1581:
1563:
1540:
1511:(3): 498–532,
1490:
1475:
1443:
1429:
1419:(2): 187–211,
1403:
1396:
1379:10.1.1.40.9731
1353:
1314:
1283:
1272:(4): 199–201,
1247:
1222:Stockmeyer, L.
1218:Johnson, D. S.
1205:
1181:
1148:
1118:10.1.1.54.2565
1082:
1070:
1040:
1033:
993:
974:(1): 196–210.
954:
905:
867:
856:
837:(2): 136–147.
814:
799:
780:
766:
763:
735:
732:
696:
693:
691:
688:
640:
637:
609:
608:
604:
586:
585:
582:
575:
572:
559:
556:
549:
526:
523:
506:
503:
486:
483:
478:
475:
449:
446:
373:
370:
364:
361:
353:complete graph
336:
333:
331:
328:
327:
326:
312:
309:
306:
303:
300:
297:
294:
291:
288:
285:
282:
254:
251:
247:
244:
240:
237:
234:
231:
228:
225:
222:
219:
216:
213:
156:
136:obtained from
121:
118:
116:
113:
105:Richard Karp's
15:
9:
6:
4:
3:
2:
1725:
1714:
1711:
1709:
1706:
1704:
1701:
1700:
1698:
1685:
1678:
1671:
1663:
1656:
1648:
1641:
1633:
1627:
1623:
1619:
1615:
1611:
1604:
1596:
1592:
1585:
1574:
1567:
1556:
1549:
1547:
1545:
1536:
1532:
1528:
1524:
1519:
1514:
1510:
1506:
1505:
1500:
1494:
1486:
1482:
1478:
1476:9780720408430
1472:
1468:
1464:
1460:
1456:
1455:
1447:
1440:
1433:
1426:
1422:
1418:
1414:
1407:
1399:
1393:
1389:
1385:
1380:
1375:
1371:
1364:
1357:
1349:
1345:
1340:
1335:
1331:
1327:
1326:
1318:
1310:
1306:
1302:
1298:
1294:
1287:
1279:
1275:
1271:
1267:
1266:
1258:
1251:
1243:
1239:
1235:
1231:
1227:
1223:
1219:
1215:
1209:
1195:
1191:
1185:
1177:
1173:
1168:
1163:
1159:
1152:
1144:
1140:
1136:
1132:
1128:
1124:
1119:
1114:
1110:
1106:
1102:
1098:
1097:
1092:
1086:
1073:
1067:
1063:
1059:
1055:
1051:
1044:
1036:
1030:
1026:
1022:
1017:
1012:
1008:
1004:
997:
989:
985:
981:
977:
973:
969:
965:
958:
950:
946:
942:
938:
933:
928:
924:
920:
916:
909:
902:
898:
893:
888:
885:(4): 576–80,
884:
880:
879:
871:
865:
860:
852:
848:
844:
840:
836:
832:
828:
821:
819:
810:
803:
795:
788:
786:
781:
779:
777:
772:
762:
760:
756:
752:
748:
744:
740:
731:
729:
725:
721:
717:
713:
709:
705:
701:
687:
683:
679:
677:
673:
669:
665:
660:
658:
654:
645:
636:
634:
631:
627:
626:Papadimitriou
622:
617:
615:
605:
602:
598:
594:
591:
590:
589:
583:
580:
576:
573:
570:
567:
563:
560:
557:
554:
553:planar graphs
550:
547:
544:
543:
542:
540:
536:
532:
522:
518:
516:
512:
502:
500:
499:3-SAT problem
496:
492:
482:
474:
472:
468:
464:
460:
455:
445:
443:
439:
435:
431:
427:
423:
419:
415:
411:
407:
403:
399:
395:
391:
387:
383:
380:algorithm of
379:
369:
363:Partial paths
360:
358:
354:
350:
346:
342:
307:
304:
298:
295:
292:
289:
286:
283:
280:
270:
252:
249:
245:
242:
238:
235:
232:
229:
226:
223:
220:
217:
214:
211:
201:
197:
193:
189:
185:
181:
177:
173:
169:
165:
161:
157:
154:
150:
147:, connecting
146:
143:
139:
135:
131:
127:
126:
125:
112:
110:
106:
102:
98:
94:
93:Michael Garey
90:
85:
83:
79:
75:
71:
66:
64:
60:
56:
53:, contains a
52:
48:
45:
41:
37:
33:
29:
22:
1683:
1670:
1655:
1646:
1640:
1613:
1603:
1594:
1584:
1566:
1508:
1502:
1493:
1453:
1446:
1438:
1432:
1416:
1412:
1406:
1369:
1356:
1329:
1323:
1317:
1303:(2): 73–76,
1300:
1296:
1286:
1269:
1263:
1250:
1225:
1214:Garey, M. R.
1208:
1197:. Retrieved
1193:
1184:
1157:
1151:
1100:
1094:
1085:
1075:, retrieved
1053:
1043:
1006:
996:
971:
967:
957:
925:(1): 61–63.
922:
918:
908:
882:
876:
870:
859:
834:
830:
808:
802:
793:
768:
755:polygon mesh
737:
698:
690:Applications
684:
680:
661:
650:
628:defined the
618:
610:
587:
528:
519:
515:DNA computer
508:
488:
480:
477:Backtracking
458:
451:
441:
437:
433:
429:
425:
421:
417:
413:
409:
405:
404:and ends at
401:
397:
393:
389:
385:
375:
366:
348:
344:
340:
338:
268:
199:
195:
191:
190:which gives
187:
184:cleaved copy
179:
175:
171:
163:
159:
152:
148:
144:
137:
133:
129:
123:
86:
81:
69:
67:
62:
58:
50:
36:graph theory
27:
25:
668:certificate
662:A verifier
653:NP-Complete
593:4-connected
551:undirected
448:Monte Carlo
335:Brute force
89:NP-complete
1697:Categories
1199:2019-03-18
1077:2023-10-07
765:References
759:dual graph
704:processors
601:Tutte path
562:bridgeless
525:Complexity
491:SAT solver
330:Algorithms
115:Reductions
44:undirected
1513:CiteSeerX
1374:CiteSeerX
1334:CiteSeerX
1242:207693360
1167:0708.1496
1113:CiteSeerX
1016:1008.0541
988:0368-4245
941:0004-5411
851:0018-8670
739:Rendering
664:algorithm
473:(1.415).
305:−
296:−
293:⋯
290:−
284:−
250:−
239:−
233:−
230:⋯
227:−
221:−
215:−
949:15649582
745:used in
743:software
728:livelock
724:deadlock
376:Also, a
355:), so a
246:′
107:list of
40:directed
1535:1279412
1485:0499124
1459:259–268
1309:0596313
1143:7973651
1135:2885489
1105:Bibcode
1096:Science
901:7132716
712:network
708:packets
607:graphs.
566:regular
497:to the
323:
273:
265:
204:
1628:
1533:
1515:
1483:
1473:
1394:
1376:
1336:
1307:
1240:
1141:
1133:
1115:
1068:
1031:
986:
947:
939:
899:
849:
672:string
168:degree
1680:(PDF)
1576:(PDF)
1558:(PDF)
1366:(PDF)
1260:(PDF)
1238:S2CID
1162:arXiv
1131:JSTOR
1011:arXiv
945:S2CID
897:S2CID
597:Tutte
345:might
99:book
47:graph
1626:ISBN
1471:ISBN
1392:ISBN
1139:PMID
1066:ISBN
1029:ISBN
984:ISSN
937:ISSN
847:ISSN
726:and
720:node
412:and
174:and
103:and
95:and
68:The
34:and
26:The
1618:doi
1523:doi
1463:doi
1421:doi
1384:doi
1344:doi
1274:doi
1230:doi
1172:doi
1123:doi
1101:266
1058:doi
1021:doi
976:doi
927:doi
887:doi
839:doi
633:PPA
531:FNP
396:in
192:v'
186:of
180:v',
42:or
1699::
1682:.
1624:.
1612:.
1593:.
1543:^
1531:MR
1529:,
1521:,
1509:48
1507:,
1481:MR
1479:,
1469:,
1461:,
1417:10
1415:,
1390:,
1382:,
1368:,
1342:,
1328:,
1305:MR
1299:,
1268:,
1262:,
1236:,
1220:;
1216:;
1192:.
1170:.
1137:,
1129:,
1121:,
1111:,
1099:,
1064:,
1052:,
1027:.
1019:.
1005:.
982:.
972:10
970:.
966:.
943:.
935:.
921:.
917:.
895:,
883:21
881:,
845:.
833:.
829:.
817:^
784:^
659:.
616:.
436:−
182:a
111:.
82:n.
49:,
1686:.
1664:.
1620::
1597:.
1578:.
1560:.
1538:.
1525::
1488:.
1465::
1423::
1401:.
1386::
1351:.
1346::
1330:4
1312:.
1301:3
1281:.
1276::
1270:8
1245:.
1232::
1202:.
1178:.
1174::
1164::
1146:.
1125::
1107::
1060::
1037:.
1023::
1013::
990:.
978::
951:.
929::
923:9
889::
853:.
841::
835:4
603:.
581:,
571:,
548:,
471:O
459:n
442:w
440:,
438:v
434:S
430:w
426:v
422:v
420:,
418:S
414:v
410:S
406:v
402:S
398:S
394:v
390:S
386:n
349:n
341:n
325:.
311:)
308:v
302:(
299:y
287:x
281:v
269:G
253:t
243:v
236:y
224:x
218:v
212:s
200:H
196:v
188:v
176:t
172:s
164:H
160:G
153:G
149:x
145:x
138:G
134:H
130:G
63:t
59:s
51:G
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.