2311:
Alon, N., Yuster, R., and Zwick, U. 1994. Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs. In
Proceedings of the Twenty-Sixth Annual ACM Symposium on theory of Computing (Montreal, Quebec, Canada, May 23–25, 1994). STOC '94. ACM, New York, NY,
579:. Here, a graph is colorful if every vertex in it is colored with a distinct color. This method works by repeating (1) random coloring a graph and (2) finding colorful copy of the target subgraph, and eventually the target subgraph can be found if the process is repeated a sufficient number of times.
2400:
Naor, J. and Naor, M. 1990. Small-bias probability spaces: efficient constructions and applications. In
Proceedings of the Twenty-Second Annual ACM Symposium on theory of Computing (Baltimore, Maryland, United States, May 13–17, 1990). H. Ortiz, Ed. STOC '90. ACM, New York, NY, 213-223. DOI=
2413:
Alon, N., Goldreich, O., Hastad, J., and
Peralta, R. 1990. Simple construction of almost k-wise independent random variables. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science (October 22–24, 1990). SFCS. IEEE Computer Society, Washington, DC, 544-553 vol.2.
2360:
Naor, M., Schulman, L. J., and
Srinivasan, A. 1995. Splitters and near-optimal derandomization. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science (October 23–25, 1995). FOCS. IEEE Computer Society, Washington, DC,
2157:
Due to the huge amount of gene data that can be collected, searching for pathways or motifs can be highly time consuming. However, by exploiting the color-coding method, the motifs or signaling pathways with
2350:
Alon, N. and Naor, M. 1994 Derandomization, Witnesses for
Boolean Matrix Multiplication and Construction of Perfect Hash Functions. Technical Report. UMI Order Number: CS94-11., Weizmann Science Press of
1686:
1392:
1441:
1015:
253:
1755:
684:
522:
852:
761:
2117:
1978:
1875:
1443:. Although this algorithm finds only the end points of the colorful path, another algorithm by Alon and Naor that finds colorful paths themselves can be incorporated into it.
186:
431:
946:
2197:
1316:
569:
1915:
966:
1553:
1200:
879:
1108:
906:
1692:
1610:
1614:
770:, it is possible to develop an algorithm that finds well-colored cycles. Here, a cycle is well-colored if its vertices are colored by consecutive colors.
98:
2207:
vertices can be found very efficiently in polynomial time. Thus, this enables us to explore more complex or larger structures in PPI networks.
2154:
allows a deeper understanding of the similarities and differences of many biological functions, processes, and structures among organisms.
2260:
Hüffner, F.; Wernicke, S.; Zichner, T. (2008). "Algorithm
Engineering for Color-Coding with Applications to Signaling Pathway Detection".
766:
Sometimes it is also desirable to use a more restricted version of colorfulness. For example, in the context of finding cycles in
908:
colorful occurrences. Then an algorithm (described next) can be used to find colorful cycles in the randomly colored graph
1688:
can be obtained. This construction does not require the target subgraph to exist in the original subgraph finding problem.
2339:
288:
16:
This article is about a technique in the design of graph algorithms. For the use of color to display information, see
2134:
Recently, color-coding has attracted much attention in the field of bioinformatics. One example is the detection of
2040:
can be constructed in a way similar to the approach 3 above (the first step). In particular, it is done by using
1620:
1332:
1397:
971:
193:
2000:
In the case of derandomizing well-coloring, where each vertex on the subgraph is colored consecutively, a
1698:
2139:
621:
459:
21:
803:
728:
2067:
1928:
1825:
145:
2436:
1877:. In the second step, it has been shown by Jeanette P. Schmidt and Alan Siegel that the size of such
384:
915:
2274:
1822:-wise independent, and the sample space needed for generating those random bits can be as small as
1039:, and then checking whether the two vertices in each pair are connected. Given a coloring function
60:
2374:
Schmidt, J. P.; Siegel, A. (1990). "The spatial complexity of oblivious k-probe Hash functions".
2161:
1281:
64:
2327:
Alon, N., Yuster, R., and Zwick, U. 1995. Color-coding. J. ACM 42, 4 (Jul. 1995), 844–856. DOI=
2269:
531:
1884:
2147:
2135:
951:
690:
is only polynomially small. Suppose again there exists an algorithm such that, given a graph
260:
40:
1522:
1171:
857:
75:
71:
2122:
The derandomization of color-coding method can be easily parallelized, yielding efficient
8:
1085:
48:
888:
2287:
2243:
2218:
2248:
1028:
The colorful cycle-finding algorithm works by first finding all pairs of vertices in
2234:
2415:
2383:
2279:
2238:
2230:
2151:
2143:
1471:
to be discoverable, the enumeration has to include at least one instance where the
28:
2291:
2123:
1452:
369:
83:
2217:
Alon, N.; Dao, P.; Hajirasouliha, I.; Hormozdiari, F.; Sahinalp, S. C. (2008).
2283:
2430:
767:
44:
2419:
614:
times, then this copy is expected to become colorful once. Note that though
2402:
2328:
2313:
2252:
1579:
800:
By applying random coloring method, each simple cycle has a probability of
292:
56:
32:
2142:(PPI) networks. Another example is to discover and to count the number of
113:
The following results can be obtained through the method of color-coding:
79:
524:, the method of color-coding begins by randomly coloring each vertex of
17:
1761:
1606:
1260:
be the matrix describing the adjacency relations between vertices of
453:
354:
102:
94:
87:
2387:
2219:"Biomolecular network motif counting and discovery by color coding"
1455:
of color-coding involves enumerating possible colorings of a graph
86:
when the subgraph pattern that it is trying to detect has bounded
1804:
In the first step, it is possible to construct such a family with
594:. It immediately follows that if the random coloring is repeated
2216:
1168:
respectively. Then, recursively find colorful paths of length
93:
The color-coding method was proposed and analyzed in 1994 by
1329:. Thus, the recursive relation of matrix multiplications is
1760:
Another construction that appears in the original paper of
968:
is the matrix multiplication constant. Therefore, it takes
74:
of a given length, and more generally it applies to the
1238:
represent the connectivity of each pair of vertices in
2259:
1582:. In other words, there must exist a hash function in
739:
2164:
2070:
1931:
1887:
1828:
1701:
1623:
1525:
1400:
1335:
1284:
1174:
1088:
974:
954:
918:
891:
860:
806:
778:
An example would be finding a simple cycle of length
731:
624:
534:
462:
387:
196:
148:
2191:
2111:
1972:
1909:
1869:
1749:
1680:
1547:
1435:
1386:
1310:
1194:
1102:
1009:
960:
940:
900:
873:
846:
755:
678:
571:colors, and then tries to find a colorful copy of
563:
516:
425:
247:
180:
1597:There are several approaches to construct such a
2428:
1322:that are connected by a colorful path of length
590:becomes colorful with some non-zero probability
1463:is no longer required. For the target subgraph
368:vertices, then such a subgraph can be found in
1032:that are connected by a simple path of length
1017:overall time to find a simple cycle of length
70:Color-coding also applies to the detection of
2373:
885:vertices on the cycle, among which there are
1475:is colorful. To achieve this, enumerating a
1058:, enumerate all partitions of the color set
353:contains a subgraph isomorphic to a bounded
67:without much overhead in the running time.
59:. The traditional color-coding algorithm is
2060:independent, and the size of the resulting
1764:et al. can be obtained by first building a
717:. Then the expected time to find a copy of
381:To solve the problem of finding a subgraph
1681:{\displaystyle e^{k}k^{O(\log k)}\log |V|}
1387:{\displaystyle t(k)\leq 2^{k}\cdot t(k/2)}
1256:by a colorful path, respectively, and let
47:. For example, it can be used to detect a
2273:
2242:
1436:{\displaystyle 2^{O(k)}\cdot V^{\omega }}
1010:{\displaystyle e^{k}\cdot O(V^{\omega })}
694:and a coloring which maps each vertex of
2403:http://doi.acm.org/10.1145/100216.100244
2329:http://doi.acm.org/10.1145/210332.210337
2314:http://doi.acm.org/10.1145/195058.195179
1695:and Alan Siegel yields a family of size
248:{\displaystyle O(|V|^{\omega }\log |V|)}
2004:-perfect family of hash functions from
1459:, such that the randomness of coloring
452:can be a path, a cycle, or any bounded
2429:
2369:
2367:
2323:
2321:
1921:-perfect families from both steps, a
1605:The best explicit construction is by
706:, if one exists, within some runtime
140:, then such a cycle can be found in:
1750:{\displaystyle 2^{O(k)}\log ^{2}|V|}
854:to become colorful, since there are
702:colors, it finds a copy of colorful
43:which is useful in the discovery of
2364:
2318:
679:{\displaystyle |V_{H}|=O(\log |V|)}
517:{\displaystyle |V_{H}|=O(\log |V|)}
303:, then such cycle can be found in:
13:
2210:
1446:
847:{\displaystyle k!/k^{k}>e^{-k}}
756:{\displaystyle O({\tfrac {r}{p}})}
14:
2448:
1917:. Consequently, by composing the
1691:Another explicit construction by
2112:{\displaystyle k^{O(k)}\log |V|}
2024:-perfect family which maps from
1973:{\displaystyle 2^{O(k)}\log |V|}
1870:{\displaystyle k^{O(1)}\log |V|}
1150:denote the subgraphs induced by
299:contains a simple cycle of size
181:{\displaystyle O(|V|^{\omega })}
136:contains a simple cycle of size
2146:in PPI networks. Studying both
2129:
1555:, there exists a hash function
1318:gives all pairs of vertices in
426:{\displaystyle H=(V_{H},E_{H})}
2407:
2394:
2354:
2344:
2340:Coppersmith–Winograd Algorithm
2333:
2305:
2186:
2174:
2105:
2097:
2085:
2079:
1966:
1958:
1946:
1940:
1902:
1896:
1863:
1855:
1843:
1837:
1743:
1735:
1716:
1710:
1674:
1666:
1654:
1642:
1535:
1527:
1499:is sufficient. By definition,
1415:
1409:
1381:
1367:
1345:
1339:
1004:
991:
941:{\displaystyle O(V^{\omega })}
935:
922:
750:
735:
673:
669:
661:
651:
641:
626:
618:is small, it is shown that if
557:
542:
511:
507:
499:
489:
479:
464:
420:
394:
242:
238:
230:
213:
204:
200:
175:
165:
156:
152:
1:
2299:
2235:10.1093/bioinformatics/btn163
1784:followed by building another
1507:-perfect if for every subset
1220:. Suppose the boolean matrix
376:
2050:random bits that are almost
1815:random bits that are almost
1394:, which yields a runtime of
76:subgraph isomorphism problem
7:
2192:{\displaystyle k=O(\log n)}
2140:protein-protein interaction
1311:{\displaystyle A_{1}BA_{2}}
22:Color code (disambiguation)
10:
2453:
1788:-perfect family that maps
1768:-perfect family that maps
773:
287:that is in any nontrivial
108:
84:polynomial time algorithms
82:problem), where it yields
15:
2284:10.1007/s00453-007-9008-7
1617:, where a family of size
564:{\displaystyle k=|V_{H}|}
289:minor-closed graph family
268:For every fixed constant
117:For every fixed constant
2064:-perfect family will be
2020:is needed. A sufficient
1925:-perfect family of size
1910:{\displaystyle 2^{O(k)}}
2420:10.1109/FSCS.1990.89575
1881:-perfect family can be
1483:of hash functions from
961:{\displaystyle \omega }
255:worst-case time, where
2199:vertices in a network
2193:
2113:
1974:
1911:
1871:
1751:
1682:
1601:-perfect hash family:
1586:that colors any given
1549:
1437:
1388:
1312:
1278:, the boolean product
1196:
1104:
1011:
962:
942:
902:
875:
848:
757:
680:
565:
518:
427:
249:
182:
20:. For other uses, see
2194:
2114:
1975:
1912:
1872:
1752:
1683:
1550:
1548:{\displaystyle |S|=k}
1438:
1389:
1313:
1197:
1195:{\displaystyle k/2-1}
1132:accordingly, and let
1105:
1012:
963:
943:
903:
881:ways of coloring the
876:
874:{\displaystyle k^{k}}
849:
758:
681:
566:
519:
428:
261:matrix multiplication
250:
183:
41:algorithmic technique
2162:
2068:
1929:
1885:
1826:
1699:
1621:
1523:
1398:
1333:
1282:
1172:
1114:can be divided into
1086:
972:
952:
916:
889:
858:
804:
729:
725:, if one exists, is
622:
532:
460:
385:
194:
146:
1693:Jeanette P. Schmidt
1611:Leonard J. Schulman
1103:{\displaystyle k/2}
259:is the exponent of
2189:
2148:signaling pathways
2136:signaling pathways
2109:
1970:
1907:
1867:
1747:
1678:
1615:Aravind Srinivasan
1545:
1433:
1384:
1308:
1192:
1100:
1007:
958:
938:
901:{\displaystyle k!}
898:
871:
844:
753:
748:
676:
582:Suppose a copy of
561:
514:
423:
272:, and every graph
245:
178:
2229:(13): i241–i249.
1594:distinct colors.
1066:into two subsets
747:
433:in a given graph
316:expected time, or
188:expected time, or
2444:
2437:Graph algorithms
2422:
2411:
2405:
2398:
2392:
2391:
2371:
2362:
2358:
2352:
2348:
2342:
2337:
2331:
2325:
2316:
2309:
2295:
2277:
2256:
2246:
2206:
2202:
2198:
2196:
2195:
2190:
2118:
2116:
2115:
2110:
2108:
2100:
2089:
2088:
2063:
2059:
2049:
2039:
2031:
2023:
2019:
2011:
2003:
1996:can be obtained.
1995:
1987:
1979:
1977:
1976:
1971:
1969:
1961:
1950:
1949:
1924:
1920:
1916:
1914:
1913:
1908:
1906:
1905:
1880:
1876:
1874:
1873:
1868:
1866:
1858:
1847:
1846:
1821:
1814:
1803:
1795:
1787:
1783:
1775:
1767:
1756:
1754:
1753:
1748:
1746:
1738:
1730:
1729:
1720:
1719:
1687:
1685:
1684:
1679:
1677:
1669:
1658:
1657:
1633:
1632:
1600:
1593:
1589:
1585:
1577:
1562:
1558:
1554:
1552:
1551:
1546:
1538:
1530:
1518:
1510:
1506:
1502:
1498:
1490:
1482:
1479:-perfect family
1478:
1474:
1470:
1466:
1462:
1458:
1442:
1440:
1439:
1434:
1432:
1431:
1419:
1418:
1393:
1391:
1390:
1385:
1377:
1360:
1359:
1328:
1321:
1317:
1315:
1314:
1309:
1307:
1306:
1294:
1293:
1277:
1268:
1259:
1255:
1246:
1237:
1228:
1219:
1210:
1201:
1199:
1198:
1193:
1182:
1167:
1158:
1149:
1140:
1131:
1122:
1113:
1110:each. Note that
1109:
1107:
1106:
1101:
1096:
1081:
1065:
1057:
1053:
1038:
1031:
1024:
1020:
1016:
1014:
1013:
1008:
1003:
1002:
984:
983:
967:
965:
964:
959:
947:
945:
944:
939:
934:
933:
911:
907:
905:
904:
899:
884:
880:
878:
877:
872:
870:
869:
853:
851:
850:
845:
843:
842:
827:
826:
817:
796:
781:
762:
760:
759:
754:
749:
740:
724:
720:
716:
705:
701:
697:
693:
689:
685:
683:
682:
677:
672:
664:
644:
639:
638:
629:
617:
613:
612:
610:
609:
604:
601:
593:
589:
585:
578:
574:
570:
568:
567:
562:
560:
555:
554:
545:
527:
523:
521:
520:
515:
510:
502:
482:
477:
476:
467:
451:
447:
432:
430:
429:
424:
419:
418:
406:
405:
367:
357:graph which has
352:
333:worst-case time.
332:
315:
302:
298:
286:
271:
258:
254:
252:
251:
246:
241:
233:
222:
221:
216:
207:
187:
185:
184:
179:
174:
173:
168:
159:
139:
135:
120:
63:, but it can be
54:
29:computer science
2452:
2451:
2447:
2446:
2445:
2443:
2442:
2441:
2427:
2426:
2425:
2412:
2408:
2399:
2395:
2388:10.1137/0219054
2372:
2365:
2359:
2355:
2349:
2345:
2338:
2334:
2326:
2319:
2310:
2306:
2302:
2213:
2211:Further reading
2204:
2200:
2163:
2160:
2159:
2132:
2104:
2096:
2075:
2071:
2069:
2066:
2065:
2061:
2051:
2041:
2033:
2025:
2021:
2013:
2005:
2001:
1989:
1981:
1980:that maps from
1965:
1957:
1936:
1932:
1930:
1927:
1926:
1922:
1918:
1892:
1888:
1886:
1883:
1882:
1878:
1862:
1854:
1833:
1829:
1827:
1824:
1823:
1816:
1805:
1797:
1789:
1785:
1777:
1769:
1765:
1742:
1734:
1725:
1721:
1706:
1702:
1700:
1697:
1696:
1673:
1665:
1638:
1634:
1628:
1624:
1622:
1619:
1618:
1598:
1591:
1587:
1583:
1564:
1560:
1556:
1534:
1526:
1524:
1521:
1520:
1512:
1508:
1504:
1500:
1492:
1484:
1480:
1476:
1472:
1468:
1464:
1460:
1456:
1453:derandomization
1449:
1447:Derandomization
1427:
1423:
1405:
1401:
1399:
1396:
1395:
1373:
1355:
1351:
1334:
1331:
1330:
1323:
1319:
1302:
1298:
1289:
1285:
1283:
1280:
1279:
1276:
1270:
1267:
1261:
1257:
1254:
1248:
1245:
1239:
1236:
1230:
1227:
1221:
1218:
1212:
1209:
1203:
1178:
1173:
1170:
1169:
1166:
1160:
1157:
1151:
1148:
1142:
1139:
1133:
1130:
1124:
1121:
1115:
1111:
1092:
1087:
1084:
1083:
1080:
1073:
1067:
1059:
1055:
1054:to color graph
1040:
1033:
1029:
1022:
1018:
998:
994:
979:
975:
973:
970:
969:
953:
950:
949:
929:
925:
917:
914:
913:
909:
890:
887:
886:
882:
865:
861:
859:
856:
855:
835:
831:
822:
818:
813:
805:
802:
801:
783:
779:
776:
738:
730:
727:
726:
722:
718:
707:
703:
699:
695:
691:
687:
668:
660:
640:
634:
630:
625:
623:
620:
619:
615:
605:
602:
599:
598:
596:
595:
591:
587:
583:
576:
572:
556:
550:
546:
541:
533:
530:
529:
525:
506:
498:
478:
472:
468:
463:
461:
458:
457:
449:
434:
414:
410:
401:
397:
386:
383:
382:
379:
370:polynomial time
358:
339:
319:
306:
300:
296:
273:
269:
256:
237:
229:
217:
212:
211:
203:
195:
192:
191:
169:
164:
163:
155:
147:
144:
143:
137:
122:
118:
111:
52:
25:
12:
11:
5:
2450:
2440:
2439:
2424:
2423:
2406:
2393:
2382:(5): 775–786.
2376:SIAM J. Comput
2363:
2353:
2343:
2332:
2317:
2312:326–335. DOI=
2303:
2301:
2298:
2297:
2296:
2275:10.1.1.68.9469
2268:(2): 114–132.
2257:
2223:Bioinformatics
2212:
2209:
2188:
2185:
2182:
2179:
2176:
2173:
2170:
2167:
2131:
2128:
2107:
2103:
2099:
2095:
2092:
2087:
2084:
2081:
2078:
2074:
1998:
1997:
1968:
1964:
1960:
1956:
1953:
1948:
1945:
1942:
1939:
1935:
1904:
1901:
1898:
1895:
1891:
1865:
1861:
1857:
1853:
1850:
1845:
1842:
1839:
1836:
1832:
1758:
1745:
1741:
1737:
1733:
1728:
1724:
1718:
1715:
1712:
1709:
1705:
1689:
1676:
1672:
1668:
1664:
1661:
1656:
1653:
1650:
1647:
1644:
1641:
1637:
1631:
1627:
1590:vertices with
1544:
1541:
1537:
1533:
1529:
1448:
1445:
1430:
1426:
1422:
1417:
1414:
1411:
1408:
1404:
1383:
1380:
1376:
1372:
1369:
1366:
1363:
1358:
1354:
1350:
1347:
1344:
1341:
1338:
1305:
1301:
1297:
1292:
1288:
1274:
1265:
1252:
1243:
1234:
1225:
1216:
1207:
1191:
1188:
1185:
1181:
1177:
1164:
1155:
1146:
1137:
1128:
1119:
1099:
1095:
1091:
1078:
1071:
1006:
1001:
997:
993:
990:
987:
982:
978:
957:
937:
932:
928:
924:
921:
897:
894:
868:
864:
841:
838:
834:
830:
825:
821:
816:
812:
809:
775:
772:
752:
746:
743:
737:
734:
698:to one of the
675:
671:
667:
663:
659:
656:
653:
650:
647:
643:
637:
633:
628:
559:
553:
549:
544:
540:
537:
513:
509:
505:
501:
497:
494:
491:
488:
485:
481:
475:
471:
466:
422:
417:
413:
409:
404:
400:
396:
393:
390:
378:
375:
374:
373:
336:
335:
334:
317:
266:
265:
264:
244:
240:
236:
232:
228:
225:
220:
215:
210:
206:
202:
199:
189:
177:
172:
167:
162:
158:
154:
151:
110:
107:
99:Raphael Yuster
45:network motifs
9:
6:
4:
3:
2:
2449:
2438:
2435:
2434:
2432:
2421:
2417:
2410:
2404:
2397:
2389:
2385:
2381:
2377:
2370:
2368:
2357:
2347:
2341:
2336:
2330:
2324:
2322:
2315:
2308:
2304:
2293:
2289:
2285:
2281:
2276:
2271:
2267:
2263:
2258:
2254:
2250:
2245:
2240:
2236:
2232:
2228:
2224:
2220:
2215:
2214:
2208:
2183:
2180:
2177:
2171:
2168:
2165:
2155:
2153:
2149:
2145:
2141:
2137:
2127:
2125:
2120:
2101:
2093:
2090:
2082:
2076:
2072:
2058:
2054:
2048:
2044:
2037:
2029:
2017:
2009:
1993:
1985:
1962:
1954:
1951:
1943:
1937:
1933:
1899:
1893:
1889:
1859:
1851:
1848:
1840:
1834:
1830:
1820:
1813:
1809:
1801:
1793:
1781:
1773:
1763:
1759:
1739:
1731:
1726:
1722:
1713:
1707:
1703:
1694:
1690:
1670:
1662:
1659:
1651:
1648:
1645:
1639:
1635:
1629:
1625:
1616:
1612:
1608:
1604:
1603:
1602:
1595:
1581:
1575:
1571:
1567:
1542:
1539:
1531:
1516:
1496:
1488:
1454:
1444:
1428:
1424:
1420:
1412:
1406:
1402:
1378:
1374:
1370:
1364:
1361:
1356:
1352:
1348:
1342:
1336:
1326:
1303:
1299:
1295:
1290:
1286:
1273:
1269:and those of
1264:
1251:
1242:
1233:
1224:
1215:
1206:
1189:
1186:
1183:
1179:
1175:
1163:
1154:
1145:
1136:
1127:
1118:
1097:
1093:
1089:
1077:
1070:
1063:
1051:
1047:
1043:
1036:
1026:
999:
995:
988:
985:
980:
976:
955:
930:
926:
919:
895:
892:
866:
862:
839:
836:
832:
828:
823:
819:
814:
810:
807:
798:
794:
790:
786:
771:
769:
768:planar graphs
764:
744:
741:
732:
714:
710:
665:
657:
654:
648:
645:
635:
631:
608:
580:
551:
547:
538:
535:
503:
495:
492:
486:
483:
473:
469:
455:
445:
441:
437:
415:
411:
407:
402:
398:
391:
388:
371:
365:
361:
356:
350:
346:
342:
337:
330:
326:
322:
318:
313:
309:
305:
304:
294:
290:
284:
280:
276:
267:
262:
234:
226:
223:
218:
208:
197:
190:
170:
160:
149:
142:
141:
133:
129:
125:
121:, if a graph
116:
115:
114:
106:
104:
100:
96:
91:
89:
85:
81:
77:
73:
68:
66:
62:
61:probabilistic
58:
50:
46:
42:
39:refers to an
38:
34:
30:
23:
19:
2409:
2396:
2379:
2375:
2356:
2346:
2335:
2307:
2265:
2262:Algorithmica
2261:
2226:
2222:
2156:
2133:
2130:Applications
2126:algorithms.
2121:
2056:
2052:
2046:
2042:
2035:
2027:
2015:
2007:
1999:
1991:
1983:
1818:
1811:
1807:
1799:
1791:
1779:
1771:
1596:
1573:
1569:
1565:
1514:
1494:
1486:
1450:
1324:
1271:
1262:
1249:
1240:
1231:
1222:
1213:
1204:
1161:
1152:
1143:
1134:
1125:
1116:
1075:
1068:
1061:
1049:
1045:
1041:
1034:
1027:
799:
792:
788:
784:
777:
765:
712:
708:
606:
581:
456:graph where
443:
439:
435:
380:
363:
359:
348:
344:
340:
328:
324:
320:
311:
307:
293:planar graph
282:
278:
274:
131:
127:
123:
112:
92:
69:
65:derandomized
37:color-coding
36:
33:graph theory
26:
1572:→ {1, ...,
1202:in each of
1048:→ {1, ...,
575:in colored
338:If a graph
80:NP-complete
55:in a given
49:simple path
35:, the term
2300:References
2026:{1, ..., |
2006:{1, ..., |
1982:{1, ..., |
1770:{1, ..., |
1563:such that
1513:{1, ..., |
1485:{1, ..., |
377:The method
51:of length
18:color code
2270:CiteSeerX
2181:
2094:
2034:{1, ...,
2014:{1, ...,
1990:{1, ...,
1955:
1852:
1798:{1, ...,
1790:{1, ...,
1778:{1, ...,
1762:Noga Alon
1732:
1663:
1649:
1607:Moni Naor
1493:{1, ...,
1429:ω
1421:⋅
1362:⋅
1349:≤
1187:−
1060:{1, ...,
1000:ω
986:⋅
956:ω
931:ω
837:−
782:in graph
658:
496:
454:treewidth
355:treewidth
291:(e.g., a
227:
219:ω
171:ω
103:Uri Zwick
95:Noga Alon
88:treewidth
2431:Category
2253:18586721
1568: :
1082:of size
1044: :
948:, where
912:in time
448:, where
2351:Israel.
2244:2718641
1580:perfect
774:Example
611:
597:
109:Results
2290:
2272:
2251:
2241:
2152:motifs
2144:motifs
1613:, and
1519:where
295:), if
101:, and
72:cycles
2292:81069
2288:S2CID
2203:with
1817:2log
528:with
362:(log
57:graph
2361:182.
2249:PMID
2150:and
2055:log
2045:log
1810:log
1451:The
1247:and
1229:and
1211:and
1159:and
1141:and
1123:and
829:>
327:log
78:(an
31:and
2416:doi
2384:doi
2280:doi
2239:PMC
2231:doi
2178:log
2138:in
2091:log
2032:to
2030:|}
2018:!}
2012:to
2010:|}
1988:to
1986:|}
1952:log
1849:log
1796:to
1776:to
1774:|}
1723:log
1660:log
1646:log
1578:is
1559:in
1517:|}
1511:of
1503:is
1491:to
1489:|}
1467:in
1327:− 1
1037:− 1
1021:in
787:= (
721:in
655:log
586:in
493:log
438:= (
343:= (
277:= (
224:log
126:= (
27:In
2433::
2380:19
2378:.
2366:^
2320:^
2286:.
2278:.
2266:52
2264:.
2247:.
2237:.
2227:24
2225:.
2221:.
2124:NC
2119:.
2043:nk
2038:}
1994:}
1802:}.
1794:}
1782:},
1609:,
1576:}
1497:}
1074:,
1064:}
1052:}
1025:.
797:.
791:,
763:.
686:,
442:,
347:,
281:,
130:,
105:.
97:,
90:.
2418::
2390:.
2386::
2294:.
2282::
2255:.
2233::
2205:n
2201:G
2187:)
2184:n
2175:(
2172:O
2169:=
2166:k
2106:|
2102:V
2098:|
2086:)
2083:k
2080:(
2077:O
2073:k
2062:k
2057:k
2053:k
2047:k
2036:k
2028:V
2022:k
2016:k
2008:V
2002:k
1992:k
1984:V
1967:|
1963:V
1959:|
1947:)
1944:k
1941:(
1938:O
1934:2
1923:k
1919:k
1903:)
1900:k
1897:(
1894:O
1890:2
1879:k
1864:|
1860:V
1856:|
1844:)
1841:1
1838:(
1835:O
1831:k
1819:k
1812:k
1808:n
1806:2
1800:k
1792:k
1786:k
1780:k
1772:V
1766:k
1757:.
1744:|
1740:V
1736:|
1727:2
1717:)
1714:k
1711:(
1708:O
1704:2
1675:|
1671:V
1667:|
1655:)
1652:k
1643:(
1640:O
1636:k
1630:k
1626:e
1599:k
1592:k
1588:k
1584:F
1574:k
1570:S
1566:h
1561:F
1557:h
1543:k
1540:=
1536:|
1532:S
1528:|
1515:V
1509:S
1505:k
1501:F
1495:k
1487:V
1481:F
1477:k
1473:H
1469:G
1465:H
1461:G
1457:G
1425:V
1416:)
1413:k
1410:(
1407:O
1403:2
1382:)
1379:2
1375:/
1371:k
1368:(
1365:t
1357:k
1353:2
1346:)
1343:k
1340:(
1337:t
1325:k
1320:V
1304:2
1300:A
1296:B
1291:1
1287:A
1275:2
1272:V
1266:1
1263:V
1258:B
1253:2
1250:G
1244:1
1241:G
1235:2
1232:A
1226:1
1223:A
1217:2
1214:G
1208:1
1205:G
1190:1
1184:2
1180:/
1176:k
1165:2
1162:V
1156:1
1153:V
1147:2
1144:G
1138:1
1135:G
1129:2
1126:V
1120:1
1117:V
1112:V
1098:2
1094:/
1090:k
1079:2
1076:C
1072:1
1069:C
1062:k
1056:G
1050:k
1046:V
1042:c
1035:k
1030:V
1023:G
1019:k
1005:)
996:V
992:(
989:O
981:k
977:e
936:)
927:V
923:(
920:O
910:G
896:!
893:k
883:k
867:k
863:k
840:k
833:e
824:k
820:k
815:/
811:!
808:k
795:)
793:E
789:V
785:G
780:k
751:)
745:p
742:r
736:(
733:O
723:G
719:H
715:)
713:r
711:(
709:O
704:H
700:k
696:G
692:G
688:p
674:)
670:|
666:V
662:|
652:(
649:O
646:=
642:|
636:H
632:V
627:|
616:p
607:p
603:/
600:1
592:p
588:G
584:H
577:G
573:H
558:|
552:H
548:V
543:|
539:=
536:k
526:G
512:)
508:|
504:V
500:|
490:(
487:O
484:=
480:|
474:H
470:V
465:|
450:H
446:)
444:E
440:V
436:G
421:)
416:H
412:E
408:,
403:H
399:V
395:(
392:=
389:H
372:.
366:)
364:V
360:O
351:)
349:E
345:V
341:G
331:)
329:V
325:V
323:(
321:O
314:)
312:V
310:(
308:O
301:k
297:G
285:)
283:E
279:V
275:G
270:k
263:.
257:ω
243:)
239:|
235:V
231:|
214:|
209:V
205:|
201:(
198:O
176:)
166:|
161:V
157:|
153:(
150:O
138:k
134:)
132:E
128:V
124:G
119:k
53:k
24:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.