Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения
Розглянуто вплив транзитивних дуг на оптимальність паралельного упорядкування, побудованого за алгоритмом, що базується на лексикографічному принципі. Запропоновано достатню умову, при якій транзитивні дуги не впливатимуть на оптимальність розв’язку, отриманого за цим алгоритмом. Досліджено клас гра...
Saved in:
| Published in: | Проблемы управления и информатики |
|---|---|
| Date: | 2012 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/207448 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения / В.А. Турчина, Н.К. Федоренко // Проблемы управления и информатики. — 2012. — № 1. — С. 62–71. — Бібліогр.: 3 назв. - рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862616329793568768 |
|---|---|
| author | Турчина, В.А. Федоренко, Н.К. |
| author_facet | Турчина, В.А. Федоренко, Н.К. |
| citation_txt | Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения / В.А. Турчина, Н.К. Федоренко // Проблемы управления и информатики. — 2012. — № 1. — С. 62–71. — Бібліогр.: 3 назв. - рос. |
| collection | DSpace DC |
| container_title | Проблемы управления и информатики |
| description | Розглянуто вплив транзитивних дуг на оптимальність паралельного упорядкування, побудованого за алгоритмом, що базується на лексикографічному принципі. Запропоновано достатню умову, при якій транзитивні дуги не впливатимуть на оптимальність розв’язку, отриманого за цим алгоритмом. Досліджено клас графів, які задають нерозгалужені арифметичні вирази, та доведено, що для цих графів наявність транзитивних дуг також не впливатиме на оптимальність отриманого за алгоритмом розв’язку.
Transitive edges influence on the optimality of the scheduler built by the algorithm based on the lexicographic principle is considered. The sufficient condition when transitive edges don’t influence the optimality of the solution is given. Besides the class of graphs describing not branching arithmetic expressions is studied and it’s proved that transitive edges don’t influence optimality of the schedule for such graphs with transitive edges.
|
| first_indexed | 2025-12-07T13:09:20Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-207448 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Russian |
| last_indexed | 2025-12-07T13:09:20Z |
| publishDate | 2012 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Турчина, В.А. Федоренко, Н.К. 2025-10-07T16:16:56Z 2012 Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения / В.А. Турчина, Н.К. Федоренко // Проблемы управления и информатики. — 2012. — № 1. — С. 62–71. — Бібліогр.: 3 назв. - рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/207448 519.8 10.1615/JAutomatInfScien.v44.i2.40 Розглянуто вплив транзитивних дуг на оптимальність паралельного упорядкування, побудованого за алгоритмом, що базується на лексикографічному принципі. Запропоновано достатню умову, при якій транзитивні дуги не впливатимуть на оптимальність розв’язку, отриманого за цим алгоритмом. Досліджено клас графів, які задають нерозгалужені арифметичні вирази, та доведено, що для цих графів наявність транзитивних дуг також не впливатиме на оптимальність отриманого за алгоритмом розв’язку. Transitive edges influence on the optimality of the scheduler built by the algorithm based on the lexicographic principle is considered. The sufficient condition when transitive edges don’t influence the optimality of the solution is given. Besides the class of graphs describing not branching arithmetic expressions is studied and it’s proved that transitive edges don’t influence optimality of the schedule for such graphs with transitive edges. ru Інститут кібернетики ім. В.М. Глушкова НАН України Проблемы управления и информатики Оптимальное управление и методы оптимизации Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения Дослідження впливу транзитивних дуг на оптимальність деяких алгоритмів паралельного упорядкування Research of the Transitive Edges Influence on the Optimality of Some Scheduling Algorithms Article published earlier |
| spellingShingle | Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения Турчина, В.А. Федоренко, Н.К. Оптимальное управление и методы оптимизации |
| title | Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения |
| title_alt | Дослідження впливу транзитивних дуг на оптимальність деяких алгоритмів паралельного упорядкування Research of the Transitive Edges Influence on the Optimality of Some Scheduling Algorithms |
| title_full | Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения |
| title_fullStr | Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения |
| title_full_unstemmed | Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения |
| title_short | Исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения |
| title_sort | исследование влияния транзитивных дуг на оптимальность некоторых алгоритмов параллельного упорядочения |
| topic | Оптимальное управление и методы оптимизации |
| topic_facet | Оптимальное управление и методы оптимизации |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/207448 |
| work_keys_str_mv | AT turčinava issledovanievliâniâtranzitivnyhdugnaoptimalʹnostʹnekotoryhalgoritmovparallelʹnogouporâdočeniâ AT fedorenkonk issledovanievliâniâtranzitivnyhdugnaoptimalʹnostʹnekotoryhalgoritmovparallelʹnogouporâdočeniâ AT turčinava doslídžennâvplivutranzitivnihdugnaoptimalʹnístʹdeâkihalgoritmívparalelʹnogouporâdkuvannâ AT fedorenkonk doslídžennâvplivutranzitivnihdugnaoptimalʹnístʹdeâkihalgoritmívparalelʹnogouporâdkuvannâ AT turčinava researchofthetransitiveedgesinfluenceontheoptimalityofsomeschedulingalgorithms AT fedorenkonk researchofthetransitiveedgesinfluenceontheoptimalityofsomeschedulingalgorithms |