4488
правок
Цветовое кодирование: различия между версиями
Перейти к навигации
Перейти к поиску
→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 43: | Строка 43: | ||
== Применение == | == Применение == | ||
Исходная цель заключалась в разработке эффективных алгоритмов для нахождения простых путей и циклов в графах. Однако впоследствии оказалось, что потенциальная область применения метода цветового кодирования значительно шире. Линейные временные границы (2O( • \E\ для ориентированных графов и 2O ( k ■ \V\ - для неориентированных) для простых путей фактически применимы к любому лесу с k вершинами. Граница 2O( • \V\W для простых циклов фактически применима к любому серийно-параллельному графу с k вершинами. В общем случае, если граф G = (V, E) сдержит подграф, изоморфный графу H = (VH, EH), древесная ширина которого не превышает t, то такой подграф можно найти за ожидаемое время 2O(k) • \V\t+1, где k = JVHJ. Это улучшает результаты алгоритма Плена и Войта [14], время выполнения которого составляет | Vjt+1. В качестве специального случая можно сделать вывод, что задача LOG PATH входит в P. Таким образом, на гипотезу Пападимитриу и Яннакакиса [13] можно дать положительный ответ. От экспоненциальной зависимости от k в вышеприведенных границах, вероятно, избавиться не получится, поскольку задача является NP-полной при наличии k во входных данных. | |||
Метод цветового кодирования оказался плодотворным в изучении параметризованных алгоритмов и параметризованной сложности [7, 8]. Недавно этот метод нашел перспективное применение в вычислительной биологии, в частности, в выявлении сигнальных путей в сетях белковых взаимодействий, см. [10, 17, 18, 19]. | |||
== Открытые вопросы == | |||
Перечисленные ниже задачи все еще остаются нерешенными. | |||
• Существует ли (детерминированный или рандомизированный) алгоритм с полиномиальным временем выполнения, определяющий, содержит ли заданный граф G = (V, E) путь длины, скажем, log2 |V|? (Это маловероятно, поскольку в таком случае должен был бы существовать алгоритм, за время 2°^"' определяющий, является ли заданный граф с n вершинами Гамильтоновым). | |||
• Можно ли отбросить коэффициент log |V|, появляющийся в процессе дерандомизации? | |||
• Имеют ли задача определения, содержит ли заданный граф G = (V, E) треугольник, и задача будева умножения двух матриц | V x | V | равными по сложности? | |||
== Экспериментальные результаты == | |||
Результаты выполнения базового алгоритма на биологических данных представлены в работах [17, 19]. | |||
== См. также == | |||
* [[Схемы аппроксимации для задач с планарными графами]] | |||
* [[Изоморфизм графов]] | |||
* [[Древесная ширина графа]] | |||
== Литература == | |||
1. Alon, N., Goldreich, O., Hastad, J., Peralta, R.: Simple constructions of almost k-wise independent random variables. Random Struct. Algorithms 3(3), 289-304 (1992) | |||
2. Alon, N., Yuster, R., Zwick, U.: Color coding. J. ACM 42,844-856 (1995) | |||
3. Alon, N., Yuster, R., Zwick, U.: Finding and counting given length cycles. Algorithmica 17(3), 209-223 (1997) | |||
4. Bjorklund, A., Husfeldt, T.: Finding a path of superlogarithmic length. SIAM J. Comput. 32(6), 1395-1402 (2003) | |||
5. Chen, J., Lu, S., Sze, S., Zhang, F.: Improved algorithms for path, matching, and packing problems. Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 298-307 (2007) | |||
6. Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3), 1 -27 (1999) | |||
7. Fellows, M.R.: New Directions and new challenges in algorithm design and complexity, parameterized. In: Lecture Notes in Computer Science, vol. 2748, p. 505-519 (2003) | |||
8. Flum, J., Grohe, M.: The Parameterized complexity of counting problems. SIAM J. Comput. 33(4), 892-922 (2004) | |||
9. Fredman, M.L., J.Komlos, Szemeredi, E.: Storing a sparse table with O(1) worst case access time. J. ACM 31, 538-544 (1984) | |||
10. HCiffner, F., Wernicke, S., Zichner, T.: Algorithm engineering for Color Coding to facilitate Signaling Pathway Detection. In: Proceedings of the 5th Asia-Pacific Bioinformatics Conference (APBC), pp. 277-286 (2007) | |||
11. Monien, B.: How to find long paths efficiently. Ann. Discret. Math. 25,239-254 (1985) | |||
12. Naor, J., Naor, M.: Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput. Comput. 22(4), 838-856(1993) | |||
13. Papadimitriou, C.H., Yannakakis, M.: On limited nondeterminism and the complexity of the V-C dimension. J. Comput. Syst. Sci. 53(2), 161-170(1996) | |||
14. Plehn, J., Voigt, B.: Finding minimally weighted subgraphs. Lect. Notes Comput. Sci. 484,18-29 (1990) | |||
15. Robertson, N., Seymour, P.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 309-322 (1986) | |||
16. Schmidt, J.P., Siegel, A.: The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput. 19(5), 775-786 (1990) | |||
17. Scott, J., Ideker, T., Karp, R.M., Sharan, R.: Efficient Algorithms for Detecting Signaling Pathways in Protein Interaction Networks. J. Comput. Biol. 13(2), 133-144 (2006) | |||
18. Sharan, R., Ideker, T.: Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24, 427-433 (2006) | |||
19. Shlomi,T., Segal, D., Ruppin, E., Sharan, R.:QPath: a method for querying pathways in a protein-protein interaction network. ВМС Bioinform. 7,199 (2006) | |||