Будь ласка, використовуйте цей ідентифікатор, щоб цитувати або посилатися на цей матеріал:
http://elartu.tntu.edu.ua/handle/lib/29087
Повний запис метаданих
| Поле DC | Значення | Мова |
|---|---|---|
| dc.contributor.author | Скрильник, І. | |
| dc.contributor.author | Skrylnyk, I. | |
| dc.date.accessioned | 2019-11-01T12:44:57Z | - |
| dc.date.available | 2019-11-01T12:44:57Z | - |
| dc.date.created | 2007-05-22 | |
| dc.date.issued | 2007-05-22 | |
| dc.date.submitted | 2007-04-16 | |
| dc.identifier.citation | Скрильник І. Розв'язання NP-складних задач як пофарбування теоретико-графових моделей за допомогою генетичного алгоритму / І. Скрильник // Вісник ТДТУ. — Т. : ТДТУ, 2007. — Том 12. — № 2. — С. 166–176. — (Математичне моделювання. Математика. Фізика). | |
| dc.identifier.issn | 1727-7108 | |
| dc.identifier.uri | http://elartu.tntu.edu.ua/handle/lib/29087 | - |
| dc.description.abstract | У статті розглядається проблема пофарбування графів за допомогою генетичного алгоритму. Показано, що велика кількість NP-складних задач зводяться до проблеми пофарбування теоретико-графових моделей. На основі 0-1 програмування та лінійно-квадратичної оптимізації розроблено комбінований алгоритм, який дозволяє ефективно пофарбовувати графи зі 6*10306 вершинами у мінімальну кількість кольорів. | |
| dc.description.abstract | In this paper the graph coloring problem using the genetic algorithm is investigated. It is shown that a great majority of NP-hard problems can be converged to graph coloring problem. The combined algorithm is elaborated, basing on the 0-1 programming and linear-quadratic optimization. The designed algorithm enables to color graphs up to 6*10306 vertex in the minimal number of colors. | |
| dc.format.extent | 166-176 | |
| dc.language.iso | uk | |
| dc.publisher | ТДТУ | |
| dc.publisher | TSTU | |
| dc.relation.ispartof | Вісник Тернопільського державного технічного університету, 2 (12), 2007 | |
| dc.relation.ispartof | Scientific Journal of the Ternopil State Technical University, 2 (12), 2007 | |
| dc.relation.uri | ftp://dimacs.rutgers.edu/pub/challenge/graph | |
| dc.title | Розв'язання NP-складних задач як пофарбування теоретико-графових моделей за допомогою генетичного алгоритму | |
| dc.title.alternative | The NP-hard problems solving as a graph coloring task using the genetic algorithm | |
| dc.type | Article | |
| dc.rights.holder | © Тернопільський державний технічний університет імені Івана Пулюя, 2007 | |
| dc.format.pages | 11 | |
| dc.subject.udc | 519.876.5 | |
| dc.relation.references | 1. De Wera D. An introduction to timetabling // European Journal of Operations Research. – 1985. - № 19. – P. 151 – 162. | |
| dc.relation.references | 2. Fred C. Chow, John L. Hennesy. Register allocation by priority-based coloring. In Proceedings of the ACM SYGPLAN 84 Symposium on Compiler Construction. - New York: ACM, 1984. – P. 222 – 223. | |
| dc.relation.references | 3. Fred C. Chow, John L. Hennesy. The priority-based coloring approach to register allocation // ACM Transactions on Programming Languages and Systems. – 1990. – № 12(4). – P. 501 – 536. | |
| dc.relation.references | 4. Gamst A. Some lower bounds for a class of frequency assignment problems // IEEE Transactions of Vehicular Echnology. – 1986. - № 35(1). – P. 8 – 14. | |
| dc.relation.references | 5. Arkin M., Silverberg B. Scheduling jobs with fixed start and end times // Discrete Applied Mathematics. – 1987. – № 18. | |
| dc.relation.references | 6. Mikhail J. Atallan. Algorithms and Theory of Computation Handbook. U.S.A, New York: CRC Press, 1999. | |
| dc.relation.references | 7. Grotschel M., Junger M., Reinelt G. An application of combinatorial optimization to statistical physics and Circuit layout design // Operations Research. – 1988. - № 36(3). – P. 493 – 513. | |
| dc.relation.references | 8. Agarwal S., Belongie S. On the non-optimality of four color coding of image partitions // IEEE Proceedings of Int. Conf. Image Processing. – 2002. | |
| dc.relation.references | 9. Алексеев В.А., Носов В.А. NP-полные задачи и их полиномиальные варианты. Обзор. Обозрение промышленной и прикладной математики. - 1997. - т. 4, вып. 2. - С.165 – 193. | |
| dc.relation.references | 10. Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to NP-completeness, San Francisco: W.H. Freeman, CA. – 1979. | |
| dc.relation.references | 11. Craig A. Morgenstern, Harry D. Shapiro. Coloration neighborhood structures for general graph coloring. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, Jan. 1990. Society for Industrial and Applied Mathematics, Philadelphia. – 1990. | |
| dc.relation.references | 12. Carrahan R., Pardalos P. M. An exact algorithm for the maximum clique problem // Operations Research Letters. – 1990. - № 9. – P. 375 – 382. | |
| dc.relation.references | 13. Babel L. Finding maximum cliques in arbitrary and special graphs // Computing. – 1991. - № 46. – P. 321–341. | |
| dc.relation.references | 14. Babel L., Tinhofer G. A branch and bound algorithm for the maximum clique problem // Journal of Global Optimization. – 1994. - № 4. | |
| dc.relation.references | 15. Balas E., J. Xue. Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs // SIAM Journal on Computing. – 1991. - № 20(2). – P. 209 – 221. | |
| dc.relation.references | 16. Balas E., Chang Sung Yu. Finding a maximum clique in arbitrary graph // SIAM Journal on Computing. – 1986. - № 15(4). – P. 1054 – 1068. | |
| dc.relation.references | 17. Mannino C., Sassano A. An exact algorithm for the maximum cardinality stable set problem // Networks pages, ftp://dimacs.rutgers.edu/pub/challenge/graph. - 1993. | |
| dc.relation.references | 18. Nemhauser G. L., Sigismondi G. L. A strong cutting plane. Branch and bound algorithm for node packing // Journal of Operational Research Society. – 1992. - № 43(5). | |
| dc.relation.references | 19. de Klerk E., Pasechnik D. V. On approximate graph colouring and MAX-k-cut algorithms based on the 9-function // Journal of Combinatorial Optimization. – 2004. - № 8(2004). | |
| dc.relation.references | 20. Kochenberger G.A., Glover F., Alidaee B., Rego C., An Uncostrained quadratic binary programming approach to the vertex coloring problem // Annals of Operations Research. – 2005. - № 139. | |
| dc.relation.references | 21. David S. Johnson. Approximation algorithm for combinatorial problem // Journal of Computer and System Sciences. – 1974. - № 9. – P. 256 – 278. | |
| dc.relation.references | 22. David S. Johnson. Worst case behavior of graph coloring algorithms // In Proceedings of 5th Southeastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, Canada. – 1974. – P. 513 – 527. | |
| dc.relation.references | 23. Pittel B. On the probable behavior of some algorithm for finding the stability number of graph // Mathematical Proceedings of Cambridge Philosophical Society. – 1982. - № 92. – P. 511 – 526. | |
| dc.relation.references | 24. Boros E., Hammer P. Pseudo-Boolean optimization // Discrete Applied Mathematics. – 2002. – № 123 (1-3). | |
| dc.relation.references | 25. Mertz P., Freisleben B. Genetic algorithms for binary quadratic programming // In Proceedings of the 1999 International Genetic and Evolutionary Computational Conference (GECCO’99), Morgan Kaufmann. – 1999. | |
| dc.relation.referencesen | 1. De Wera D. An introduction to timetabling, European Journal of Operations Research, 1985, No 19, P. 151 – 162. | |
| dc.relation.referencesen | 2. Fred C. Chow, John L. Hennesy. Register allocation by priority-based coloring. In Proceedings of the ACM SYGPLAN 84 Symposium on Compiler Construction, New York: ACM, 1984, P. 222 – 223. | |
| dc.relation.referencesen | 3. Fred C. Chow, John L. Hennesy. The priority-based coloring approach to register allocation, ACM Transactions on Programming Languages and Systems, 1990, No 12(4), P. 501 – 536. | |
| dc.relation.referencesen | 4. Gamst A. Some lower bounds for a class of frequency assignment problems, IEEE Transactions of Vehicular Echnology, 1986, No 35(1), P. 8 – 14. | |
| dc.relation.referencesen | 5. Arkin M., Silverberg B. Scheduling jobs with fixed start and end times, Discrete Applied Mathematics, 1987, No 18. | |
| dc.relation.referencesen | 6. Mikhail J. Atallan. Algorithms and Theory of Computation Handbook. U.S.A, New York: CRC Press, 1999. | |
| dc.relation.referencesen | 7. Grotschel M., Junger M., Reinelt G. An application of combinatorial optimization to statistical physics and Circuit layout design, Operations Research, 1988, No 36(3), P. 493 – 513. | |
| dc.relation.referencesen | 8. Agarwal S., Belongie S. On the non-optimality of four color coding of image partitions, IEEE Proceedings of Int. Conf. Image Processing, 2002. | |
| dc.relation.referencesen | 9. Alekseev V.A., Nosov V.A. NP-polnye zadachi i ikh polinomialnye varianty. Obzor. Obozrenie promyshlennoi i prikladnoi matematiki, 1997, V. 4, Iss. 2, P.165 – 193. | |
| dc.relation.referencesen | 10. Michael R. Garey, David S. Johnson. Computers and Intractability: A Guide to NP-completeness, San Francisco: W.H. Freeman, CA, 1979. | |
| dc.relation.referencesen | 11. Craig A. Morgenstern, Harry D. Shapiro. Coloration neighborhood structures for general graph coloring. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, Jan. 1990. Society for Industrial and Applied Mathematics, Philadelphia, 1990. | |
| dc.relation.referencesen | 12. Carrahan R., Pardalos P. M. An exact algorithm for the maximum clique problem, Operations Research Letters, 1990, No 9, P. 375 – 382. | |
| dc.relation.referencesen | 13. Babel L. Finding maximum cliques in arbitrary and special graphs, Computing, 1991, No 46, P. 321–341. | |
| dc.relation.referencesen | 14. Babel L., Tinhofer G. A branch and bound algorithm for the maximum clique problem, Journal of Global Optimization, 1994, No 4. | |
| dc.relation.referencesen | 15. Balas E., J. Xue. Minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs, SIAM Journal on Computing, 1991, No 20(2), P. 209 – 221. | |
| dc.relation.referencesen | 16. Balas E., Chang Sung Yu. Finding a maximum clique in arbitrary graph, SIAM Journal on Computing, 1986, No 15(4), P. 1054 – 1068. | |
| dc.relation.referencesen | 17. Mannino C., Sassano A. An exact algorithm for the maximum cardinality stable set problem, Networks pages, ftp://dimacs.rutgers.edu/pub/challenge/graph, 1993. | |
| dc.relation.referencesen | 18. Nemhauser G. L., Sigismondi G. L. A strong cutting plane. Branch and bound algorithm for node packing, Journal of Operational Research Society, 1992, No 43(5). | |
| dc.relation.referencesen | 19. de Klerk E., Pasechnik D. V. On approximate graph colouring and MAX-k-cut algorithms based on the 9-function, Journal of Combinatorial Optimization, 2004, No 8(2004). | |
| dc.relation.referencesen | 20. Kochenberger G.A., Glover F., Alidaee B., Rego C., An Uncostrained quadratic binary programming approach to the vertex coloring problem, Annals of Operations Research, 2005, No 139. | |
| dc.relation.referencesen | 21. David S. Johnson. Approximation algorithm for combinatorial problem, Journal of Computer and System Sciences, 1974, No 9, P. 256 – 278. | |
| dc.relation.referencesen | 22. David S. Johnson. Worst case behavior of graph coloring algorithms, In Proceedings of 5th Southeastern Conference on Combinatorics, Graph Theory and Computing, Utilitas Mathematica, Winnipeg, Canada, 1974, P. 513 – 527. | |
| dc.relation.referencesen | 23. Pittel B. On the probable behavior of some algorithm for finding the stability number of graph, Mathematical Proceedings of Cambridge Philosophical Society, 1982, No 92, P. 511 – 526. | |
| dc.relation.referencesen | 24. Boros E., Hammer P. Pseudo-Boolean optimization, Discrete Applied Mathematics, 2002, No 123 (1-3). | |
| dc.relation.referencesen | 25. Mertz P., Freisleben B. Genetic algorithms for binary quadratic programming, In Proceedings of the 1999 International Genetic and Evolutionary Computational Conference (GECCO’99), Morgan Kaufmann, 1999. | |
| dc.identifier.citationen | Skrylnyk I. (2007) Rozv'iazannia NP-skladnikh zadach iak pofarbuvannia teoretiko-hrafovikh modelei za dopomohoiu henetichnoho alhoritmu [The NP-hard problems solving as a graph coloring task using the genetic algorithm]. Scientific Journal of TSTU (Tern.), vol. 12, no 2, pp. 166-176 [in Ukrainian]. | |
| dc.contributor.affiliation | Полтавський національний технічний університет імені Юрія Кондратюка | |
| dc.citation.journalTitle | Вісник Тернопільського державного технічного університету | |
| dc.citation.volume | 12 | |
| dc.citation.issue | 2 | |
| dc.citation.spage | 166 | |
| dc.citation.epage | 176 | |
| Розташовується у зібраннях: | Вісник ТДТУ, 2007, том 12, № 2 | |
Файли цього матеріалу:
| Файл | Опис | Розмір | Формат | |
|---|---|---|---|---|
| TSTUSJ_2007v12n2_Skrylnyk_I-The_NP_hard_problems_solving_166-176.pdf | 5,06 MB | Adobe PDF | Переглянути/відкрити | |
| TSTUSJ_2007v12n2_Skrylnyk_I-The_NP_hard_problems_solving_166-176.djvu | 233,76 kB | DjVu | Переглянути/відкрити | |
| TSTUSJ_2007v12n2_Skrylnyk_I-The_NP_hard_problems_solving_166-176__COVER.png | 254,58 kB | image/png | Переглянути/відкрити |
Усі матеріали в архіві електронних ресурсів захищені авторським правом, всі права збережені.