Диссертация (1149246), страница 12
Текст из файла (страница 12)
конф. аспирантов и студентов/Под ред. Н.В. Смирнова, Г. Ш. Тамасяна - СПб.: Издат. Дом С.-Петерб. гос.ун-та, 2009. C. 73–78.[20] Фирюлина О. С., Олемской И. В. Алгоритм решения задачи онаибольшемуправления:рождениянезависимоммножествеВсероссийскаяВ.И.Зубова.конф.,//Устойчивостьпосвящ.Санкт-Петербург,1-2и80-летиюиюляпроцессысо2010дняг.–С.-Петербург: ВВМ, 2010. С. 212.[21] Фирюлина О. С. Метод построения максимальных независимых множеств// Процессы управления и устойчивость: Труды 41-й межд. научн. конф.аспирантов и студентов / Под ред. Н. В.
Смирнова, Г. Ш. Тамасяна. СПб.:Издат. Дом С.-Петерб. гос. ун-та, 2010. С. 68–72.[22] Фирюлина О. С. Вычисление неплотности квадратных (0,1)-матриц //Процессы управления и устойчивость: Труды 43-й межд. научн. конф.аспирантов и студентов / Под ред. А. С. Ерёмина, Н. В. Смирнова.
СПб.:Издат. Дом С.-Петерб. гос. ун-та, 2012. С. 55–60.[23] Фирюлина О. С. Нахождение всех максимальных независимых множествнеориентированного графа // Вестн. С.-Петерб. ун-та. Сер. 10: Прикладнаяматематика, информатика, процессы управления. 2013. Вып. 1. С. 63–69.[24] Akkoyunlu E. A. The enumeration of maximal cliques of large graphs // SIAMJournal on Computing. 1973.
Vol. 2. P. 1–6.[25] Auguston J. G., Minker J. An analysis of some graph theoretical clusteringtechniques // J. ACM. 1970. Vol. 17. №4. P. 571–588.[26] Bahadur D. K. C., Akutsu T., Tomita E., Seki T., Fujiyama A. Point matchingunder non-uniform distortions and protein side chain packing based on efficientmaximum clique algorithms // Genome Inform. 2002. Vol. 13. P. 143–152.97[27] Bron C., Kerbosch J. Algorithm 457: Finding All Cliques of an UndirectedGraph // Comm. of ACM. 1973. Vol. 16. P. 575–577.[28] Buratti E., Baralle F. E. Influence of RNA secondary structure on the premRNA splicing process // Mol.
Cell. Biol. 2004. Vol. 24. P. 10505–10514.[29] Butenko S., Wilhelm W. E. Clique-detection models in computational biochemistry and genomics // European Journal of Operational Research. 2006. Vol. 173.P. 1–17.[30] Carr R. D., Lancia G., Istrail S. Branch-and-cut algorithms for independentset problems: integrality gap and application to protein structure alignment.Technical report, Sandia National Laboratories, Albuquerque, NM (US); SandiaNational Laboratories, Livermore, CA (US), September 2000.[31] Cazals F., Karande C. A note on the problem of reporting maximal cliques //Theoretical Computer Science. 2008. Vol. 407. №1.
P. 564–568.[32] Cook S. C. The complexity of theorem–proving procedures // Third ACMSymposium on Theory of Computing. – ACM, New York, 1971, p.151–158.[33] Diestel R. Graph Theory. Heidelberg: Springer-Verlag, 2005. – 312 p.[34] Fahle T. Simple and fast: Improving a branch-and-bound algorithm for maximum clique. ESA 2002, 10th Annual European Symposium, P. 485–498.[35] Fomin F. V., Grandoni F., Kratsch D. Measure and Conquer: Domination A Case Study // Proc.
of the 32nd Inter. Colloquium on Automata, Languagesand Programming (ICALP 2005), Springer LNCS Vol. 3580. P. 191–203.[36] Fomin F. V., Grandoni F., Kratsch D. Measure and conquer: a simpleO(20.288n ) independent set algorithm. Proc. of the 17th Annual ACM-SIAMSymp. on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 2226, 2006, P.
18–25. ACM Press, 2006.98[37] Fortnow L. The status of the P versus NP problem. – ACM, 2009. Vol. 52. №9.P. 78–86.[38] Gasarch W. I. The P=?NP poll. – SIGACT News, 2002. Vol. 33. №2. P. 34–47.[39] Gutell R. R., Larsen N., Woese C. R. Lessons from an evolving rRNA: 16S and23S rRNA structures from a comparative perspective // Microbiol Rev. 1994.Vol.
58. P. 10–26.[40] Harary F., Ross I. C. A Procedure for Clique Detection Using the Group Matrix// Sociometry. 1957. Vol. 20. P. 205–215.[41] Harley E R. Comparison of Clique-Listing Algorithms // Proc. of the Inter.Conf. on Modeling, Simulation and Visualization Methods (MSV’04), Las Vegas,Nevada, USA, June 21-24, 2004, pages 433–438. CSREA Press.[42] Harley E., Bonner A., Goodman N. Uniform integration of genome mappingdata using intersection graphs // Bioinformatics.
2001. Vol. 17. P. 487–494.[43] Horaud R, Skordas T. Stereo correspondence through feature grouping andmaximal cliques // IEEE Trans. Pattern Anal. Mach. Intell. 1989. Vol. 11. №11.[44] Houck D. J., Vetnuganti R. R. An Algorithm for the Vertex Packing Problem// Operations Research. 1977. Vol. 25. P. 773–787.[45] Johnson D. S., Yannakakis M., Papadimitriou C. H. On Generating All Maximal Independent Sets // Information Processing Letters.
1988. Vol. 27. P. 119–123.[46] Johnston H. C. Cliques of a graph – variations on the Bron-Kerbosch algorithm// International Journal of Computer and Information Sciences. 1976. Vol. 5.№ 3. P. 209–238.[47] Koch I. Enumerating all connected maximal common subgraphs in two graphs.Theoretical Computer Science.
2001. Vol. 250. P. 1–30.99[48] Lopez-Lastra M., Rivas A., Barria M. I. Protein synthesis in eukaryotes: thegrowing biological relevance of cap-independent translation initiation // Biol.Res. 2005. Vol. 38. P. 121–146.[49] Loukakis E., Tsouros C. A Depth First Search Algorithm to Generate the Family of Maximal Independent Sets of a Graph Lexicographically // Computing.1981. Vol. 27.
P. 249–266.[50] Meeusen W., Cuyvers L. Clique Detection in Directed Graphs: a New Algorithm // J. of Comp. and Appl. Math. 1975. Vol. 1. P. 185–193.[51] Mironov А. S. The riboswitch control of bacterial metabolism // TRENDS inBiochemical Sciences. 2004. Vol. 29. № 1. P. 11–17.[52] Moon J. W., Moser L. On cliques in graphs // Israel J. Math. 1965.
Vol. 3. P.23–28.[53] Mulligan G. D., Corneil D. G. Corrections to Bierston’s algorithm for generating cliques // J. Assoc. Comput. Mach. 1972. Vol. 19. P. 244–247.[54] Osteen R.E. Clique Detection Algorithms Based on Line Addition and LineRemoval, SlAM J. Appl. Math. 1974. Vol. 26.
P. 126–135.[55] Ostergard P. R. J. A fast algorithm for the maximum clique problem. DiscreteAppl. Math. 2002. Vol. 120. P. 197–207.[56] Pardalos P. M., Phillips A. T. A Global Optimization Approach for Solvingthe Maximum Clique Problem // Intern. J.
Computer Math. 1990. Vol. 33. P.209–216.[57] Pardalos P. M., Xue J. The maximum clique problem // Journal of GlobalOptimization. 1994. Vol. 4. P. 301–328.100[58] Pelillo M., Siddiqi K., Zucker S. W. Matching hierarchical structures usingassociation graphs // IEEE Trans. Pattern Anal. Mach. Intell. 1999. Vol.
21.№11.[59] Raymond J. W., Willett P. Maximum common subgraph isomorphism algorithms matching chemical structures // Journal of Computer-Aided MolecularDesign. 2002. Vol. 16. P. 521–533.[60] Robson J. M. Algorithms for maximum independent set // Journal of Algorithms. 1986. Vol. 7. № 3. P. 425–440.[61] Robson J.
M. Finding a maximum independent set in time O(2n/4 ). Technicalreport, LaBRI, Universite Bordeaux I, Talence, 2001.[62] Samudrala R., Moult J. A graph-theoretic algorithm for comparative modelingof protein structure // J. Mol. Biol. 1998. Vol. 279. P. 287–302.[63] Scott W. G., Klug A. Ribozymes: structure and mechanism in RNA catalysis// Trends Biochem. Sci. 1996. Vol. 21.
P. 220–224.[64] Shearer K., Bunke H., Venkatesh S. Video indexing and similarity retrieval bylargest common subgraph detection using decision trees. IDIAP-RR 00-15, DalleMolle Institute for Perceptual Artificial Intelligence, Martigny, Valais, Switzerland, 2000.[65] Shirinivas S. G., Vetrivel S., Elango N. M. Application of graph theory incomputer science an overview // International Journal of Engineering Scienceand Technology. 2010.
Vol. 2. №9. P. 4610–4621.[66] Tarjan R. E., Trojanowski A. E. Finding a Maximum Independent Set // SIAMJournal on Computing. 1977. Vol. 6. P. 537–546.101[67] Tomita E., Akutsu T., Hayashida M., Suzuki J., Horimoto K. Algorithms forcomputing an optimal protein threading with profiles and distance restraints //Genome Informatics. 2003. Vol. 14. P. 480–481.[68] Bahadur D.
K. C., Tomita E., Suzuki J., Horimoto K., Akutsu T. Protein sidechain packing problem: a maximum edge-weight clique algorithmic approach //J. Bioinform Comput. Biol. 2005. Vol. 3. P. 103–126.[69] Tomita E., Tanaka A., Takahashi H. The worst-case time complexity for generating all maximal cliques and computational experiments // Theoretical Computer Science. 2006. Vol. 363.
P. 28–42.[70] Tomita E., Kameda T. An efficient branch-and-bound algorithm for finding amaximum clique with computational experiments // J. Glob. Optim. 2007. Vol.37. P. 95–111.[71] Tomita E., Sutani Y., Higashi T., Takahashi S., Wakatsuki M. A simple andfaster branch-and-bound algorithm for finding a maximum clique // WALCOM:Algorithms and Complexity, Lecture Notes in Computer Science. 2010. P. 191–203.[72] Varmuza K., Penchev P.
N., Scsibrany H.Maximum common substructures oforganic compounds exhibiting similar infrared spectra // J. Chem. Inf. Comput.Sci. 1998. Vol. 38. P. 420–427.102ПРИЛОЖЕНИЕ 1. ПРОГРАММНАЯ РЕАЛИЗАЦИЯМЕТОДА ПОЛНОГО ПЕРЕБОРА ДЛЯ ПОИСКАНАИБОЛЬШЕГО НЕЗАВИСИМОГО МНОЖЕСТВА> restart;> Matching:=proc(M) #формируем n*(n-1)/2 пар из вершин множества Mlocal S,n,i,j;S:=[];n:=nops(M);for i from 1 to n-1 dofor j from i+1 to n doS:=[op(S),[M[i],M[j]]];end do;end do;return S;end proc:> Independent_check:=proc(A,M) #проверка на независимость множества Mlocal n,kol,independent,i,S;S:=Matching(M);n:=nops(S);kol:=0;independent:=false;for i from 1 to n doif A[S[i][1],S[i][2]]=0 then kol:=kol+1; end if;end do;if nops(S)=kol then independent:=true; end if;return independent;end proc:> Bin_System:=proc(N,n) #генерируем двоичную последовательность:103#0...0, 0...1, 0...10, 0...11 и т.д.local p1,p2,x,kol,i,j,position,l,S;p1:=N;kol:=1;while p1<>0 and p1<>1 dop2:=trunc(p1/2);x[kol]:=p1-p2*2;kol:=kol+1;p1:=p2;end do;position:=n-(kol);S:=[];for i from 1 to position doS:=[op(S),0];end do;S:=[op(S),p1];l:=1;for j from position+2 to n doS:=[op(S),x[kol-l]];l:=l+1;end do;return S;end proc:> SubSet:=proc(Sett,n,N) #строим N-e подмножествоlocal S, sub_Sett, i;S:=Bin_System(N,n):sub_Sett:={};for i from 1 to n doif S[n-i+1]=1 then sub_Sett:={op(sub_Sett),Sett[i]}; end if;104end do;return sub_Sett;end proc:> Total_Max:=proc(G,A) #G - множество вершин графа,#А - его матрица смежностиlocal Qmax,Q,N,m,n;Qmax:={}; #текущее наибольшее независимое множествоm:=0; #текущее наилучшее известное значение мощности ННМn:=nops(G):for N from 1 to 2^n-1 do #всего подмножеств будет 2^n-1#(без учета пустого множества)Q:=SubSet(G,n,N);if Independent_check(A,Q)=true thenif nops(Q)>m then m:=nops(Q); Qmax:=Q;end if;end if;end do;return Qmax,m;end proc:105ПРИЛОЖЕНИЕ 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
