Раскраска инциденторов и другие задачи на графах: алгоритмический аспект тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Пяткин, Артем Валерьевич

• Пяткин, Артем Валерьевич
• доктор физико-математических наук
• 2009

Оглавление диссертации доктор физико-математических наук Пяткин, Артем Валерьевич

Введение

Глава 1. Раскраска инциденторов: происхождение и приложения

1.1. Раскраска инциденторов: происхождение и приложения

1.2. Содержательная постановка исходной задачи.

1.3. Математическая модель исходной задачи и алгоритмы сё решения.

1.4. Приближённый алгоритм меньшей трудоёмкости.

1.5. Случай произвольных пропускных способностей

1.6. Задача с двумя сеансами передачи сообщений.

1.7. Задача с ограниченной памятью.

1.8. Доказательство гипотезы Визинга-Мельникова в двух частных случаях.

1.9. Передача сообщений в двухуровневой сети.

1.9.1. Случай большой пропускной способности каналов связи верхнего уровня.

1.9.2. Случай двух центральных ЭВМ, соединённых шиной пропускной способности 1.

Глава 2. Раскраска инциденторов: исследование модели

2.1. Задача взвешенной раскраски инциденторов.

2.1.1. Доказательство МР-полноты.

2.1.2. Свойства минимальной раскраски.

2.1.3. Паросочетание наименьшей мощности, покрывающее заданные вершины мультиграфа.

2.1.4. Верхние оценки для инциденторного хроматического числа.

2.2. (к, I)-раскраска инциденторов.•.

2.2.1. (0,1)-раскраска инциденторов.

2.2.2. (1,1)-раскраска инциденторов.

2.2.3. Общий случай (к, ¿)-раскраски инциденторов.

2.3. Предписанная раскраска инциденторов.

2.4. Раскраска инциденторов взвешенного неориентированного мультиграфа.

Глава 3. Вершинная и рёберная раскраски графов

3.1. Интервальная раскраска (3,4)-бирегулярного графа

3.2. Графы Эрдёша и Дирака.

3.2.1. Первый пример 6-регулярного 4-критического графа

3.2.2. Метод поиска графов Эрдёша и Дирака

3.2.3. Циркулянты Эрдёша pi Дирака чётной степени г,

4 < г < 16.

3.3. Покрывающая вырожденность и хроматическое число

Глава 4. Нумерации графов

4.1. Предписанная радио-нумерация.

4.2. Суммируемые и целочисленно суммируемые графы.

4.2.1. Число суммируемости полного двудольного графа

4.2.2. О целочисленной суммируемости некоторых классов деревьев и унициклических графов.

4.2.3. Однородные целочисленно суммируемые графы

4.3. Графы, представимые в виде слов.

Глава 5. Точные экспоненциальные алгоритмы на графах

5.1. Доминирущие множества и доматическое число.

5.1.1. Алгоритм, перечисляющий все минимальные доминирующие множества.

5.1.2. Алгоритм для поиска доматического числа.

5.2. Множества, разрезающие циклы.

5.2.1. Алгоритм для поиска максимального по мощности индуцированного леса.

5.2.2. Оценка для числа максимальных по включению индуцированных лесов.

Введение диссертации (часть автореферата) на тему «Раскраска инциденторов и другие задачи на графах: алгоритмический аспект»

Характерной особенностью дискретной математики является то, что в этой области многие доказательства являются конструктивными, позволяющими непосредственно построить искомый объект или выделить его часть, обладающую некоторыми интересными с точки зрения исследователя свойствами. Возможно это связано с тем, что большинство задач дискретной математики возникло из приложений, где требуется не только доказать возможность достижения цели, но и предъявить алгоритм, позволяющий это сделать. Так называемые «теоремы существования», которые только доказывают, что объект существует, но не дают при этом никаких идей, как его можно построить, встречаются в дискретной математике довольно редко. И даже если такие теоремы появляются, то исследователи, как правило, продолжают работать над поиском конструктивных доказательств. Классическим примером вышесказанного может служить знаменитая теорема Эрдёша 1959 года о существовании графа с произвольными наперёд заданными охватом и хроматическим числом. Доказательство П. Эрдёша [38] было вероятностным; оно не позволяло непосредственно построить такой граф. Поэтому позднее было найдено несколько конструктивных доказательств этой теоремы. Их предложили Л. Ловас ([69], 1968), Й. Нешетрил и В. Рёдль ([78], 1979) и А. Любоцкий, Р. Филипс и П. Сарнак ([72], 1988). Другим примером является доказанная Л. Ловасом ([70], 1978) гипотеза М. Кнезера ([60], 1955) о хроматическом числе графов Кнезера. Доказательство Ловаса (равно как и более простые доказательства, полученные позднее И. Барани ([28], 1978),

К. С. Саркария ([85], 1990) и В. Л. Дольниковым ([18], 1993)) опиралось на некоторые топологические результаты и было неконструктивным, т. е. из него нельзя было получить алгоритм построения раскраски графов Кнезера в требуемое число цветов. И лишь в 2004 году И. Матушеку [75] удалось найти комбинаторное доказательство гипотезы Кнезера.

В данной диссертации все предлагаемые доказательства являются конструктивными. Даже если упор делается на теоретический результат — доказательство существования того или иного объекта — приводимое доказательство всегда можно превратить в алгоритм, строящий искомый объект. Другими словами, в работе основное внимание уделяется возможности непосредственно построить искомый объект, будь то раскраска графа или некоторый граф, обладающий требуемыми свойствами. Также исследуются вопросы алгоритмической сложности решения рассматриваемых задач; доказывается КР-трудность некоторых из них.

Теория алгоритмической сложности возникла в 70-х годах прошлого века, когда впервые появилось понятие NP-тpyдныx задач, т. е. таких задач, для которых скорее всего (если Р не равно КР; далее в диссертации будем всюду придерживаться этой гипотезы) не существует алгоритма решения, время работы которого ограничено полиномом от длины входных данных задачи. В связи с этим первоочередным вопросом при анализе дискретной экстремальной задачи является определение её сложностного статуса. Либо она принадлежит классу Р полиномиально разрешимых задач, либо к классу КР-трудных задач. В последнем случае приходится либо использовать быстрые приближённые, либо точные экспоненциальные алгоритмы решения. При этом хотелось бы иметь некоторую оценку качества работы таких алгоритмов. В первом случае это оценка точности получаемого решения, а во втором — оценка времени работы (пусть экспоненциальная, но существенно лучшая чем при полном переборе всех допустимых решений).

Отметим, что для доказательства полиномиальной разрешимости задачи распознавания как правило требуется найти хорошую характеризацию (легко проверяемое условие) для примеров как с положительным, так и с отрицательным ответами. С другой стороны, для доказательства КР-полноты некоторой задачи зачастую приходится строить примеры объектов, обладающих теми или иными свойствами. Впоследствии эти объекты используются как «кирпичики» при построении сведения известной NP-пoлнoй задачи к исследуемой. Таким образом, в обоих случаях определение сложностного статуса задачи базируется на изучении структурных свойств исследуемых объектов или построении примеров с определёнными свойствами.

Объектом изучения диссертации являются комбинаторные задачи на графах. Предметом изучения являются задачи инциденторной, вершинной и рёберной раскраски графов, задачи нумерации графов, а также вопросы алгоритмической сложности и построения точных или приближённых алгоритмов решения комбинаторных задач на графах. Целью работы является изучение структурных свойств различных классов графов, позволяющих определить сложностной статус и найти алгоритмы решения вышеуказанных задач, а также построение примеров графов, обладающих заданными свойствами.

Основным предметом изучения в диссертации являются различные задачи раскраски мультиграфов и прежде всего — раскраска инцидеп-торов. Под ипцидентором в ориентированном мультиграфе понимается упорядоченная пара, состоящая из вершины и инцидентной ей дуги. Его удобно трактовать как половину дуги, примыкающую к данной вершине. В задаче раскраски инциденторов требуется найти минимальное число цветов, в которое можно раскрасить все инцидеиторы мультиграфа с соблюдением заданных условий на цвета смежных (примыкающих к одной и той же вершине) и сопряжённых (имеющих общую дугу) инциденторов. Это новый, введённый автором [104], класс задач, включающий в себя, в частности, классические задачи вершинной и рёберной раскраски. Модель инциденторной раскраски оказывается удобной при исследовании задачи передачи сообщений в локальной сети связи. С её помощью можно выразить различные ограничения на параметры каналов связи, способы передачи сообщений и структуру сети. При этом варьируются лишь ограничения на цвета сопряжённых инциденторов и структуру мультиграфа, сама же задача остаётся в рамках инциденторной раскраски.

Задачи раскраски инциденторов находят себе применение и в теории расписаний. Так классическая задача JOB SHOP с единичными длительностями операций и с двумя операциями каждой работы эквивалентна задаче (1, оо)-раскраски инциденторов. А более общая задача (к,1)~ раскраски инцденторов эквивалентна вышеописанному варианту задачи JOB SHOP с дополнительными условиями на длительность интервала между двумя операциями каждой работы. Результаты по раскраске инциденторов тем самым помогают решить некоторые варианты задачи JOB SHOP (см. [27]).

Однако задача раскраски, инциденторов представляет интерес и сама по себе. Различными исследователями рассматривались вопросы её алгоритмической сложности [100, 101], обобщения на случай неориентированных и частично ориентированных графов [6, 9, 10, 13, 14, 101] и гиперграфов [12], интервальная [4, 6], тотальная [3, 14] и предписанная [2, 110] инциденторная раскраски и многие другие. Задачи раскраски инциденторов являются новым направлением в теории графов.

Заметим, что инциденторы встречались в работах по теории графов и ранее, но только как вспомогательный инструмент, а не как основной объект для изучения. Например, в работе [31] показано, что один из частных случаев задачи о сильной рёберной раскраске мультиграфа сводится к задаче раскраске инциденторов неориентированного графа, в которой (в терминах настоящей диссертации) смежные, сопряжённые и смежные к сопряжённым инциденторы должны получать разные цвета. Этой задаче был впоследствиР1 посвящёно несколько работ [46, 37, 66, 90]. Отметим, однако, что такая инциденторная раскраска является слишком специфической и из неё нельзя получить класс задач инциденторной раскраски, исследуемых в диссертации.

Диссертация состоит из введения, пяти глав и списка литературы, состоящего из 145 наименований.

Список литературы диссертационного исследования доктор физико-математических наук Пяткин, Артем Валерьевич, 2009 год

1. Асратян А. С., Камалян Р. Р. Интервальные раскраски ребер муль-тиграфа // Прикладная математика. Вып. 5. Ереван: Изд-во Ереван, ун-та, 1987. С. 25-34

2. Визинг В. Г. Раскраска инциденторов мультиграфа в предписанные цвета // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7. № 1. С. 32-39.

3. Визинг В. Г. Раскраска инциденторов и вершин ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7. № 3. С. 6-16.

4. Визинг В. Г. Интервальная раскраска инциденторов ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2001. Т. 8. № 2. С. 40-51.

5. Визинг В. Г. Двудольная интерпретация ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2002. Т. 9. № 1. С. 27-41.

6. Визинг В. Г. Интервальная раскраска инциденторов неориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10. № 1. С. 14-40.

7. Визинг В. Г. О линейных факторах мультиграфов // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10. № 4. С. 3-7.

8. Визинг В. Г. Факторная раскраска ребер мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2004. Т. 11. № 2. С. 18—31.

9. Визинг В. Г. Жёсткая раскраска инциденторов в неориентированных мулътиграфах // Дискрет, анализ и исслед. операций. Сер. 1. 2005. Т. 12. № 3. С. 48-53.

10. Визинг В. Г. О (р, -раскраске инциденторов неориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2005. Т. 12. № 4. С. 23—39.

11. Визинг В. Г. Об оценках инциденторного хроматического числа взвешенного ориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2006. Т. 13. № 4. С. 18-25.

12. Визинг В. Г. О раскраске инциденторов в гиперграфе // Дискрет, анализ и исслед. операций. Сер. 1. 2007. Т. 14. № 3. С. 40-45.

13. Визинг В. Г. О раскраске инциденторов в частично ориентированном мультиграфе // Дискрет, анализ и исслед. операций. 2008. Т. 15. № 1. С. 17-22.

14. Визинг В. Г., Тофт Б. Раскраска инциденторов и вершин неориентированного мультиграфа // Дискрет, анализ и исслед. операций. Сер. 1. 2001. Т. 8. № 3. С. 3-14.

15. Витавер Л. М. Нахождение минимальных раскрасок вершин графа с помощью булевых степеней матрицы смежности // Докл. АН СССР, 1962. Т. 147. № 4. С. 758-759.

16. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир. 1982.

17. Дистель Р. Теория графов. Новосибирск. Изд-во Института математики, 2002.

18. Дольников В. Л. Трансверсали семейств множеств в Мп и связь между теоремами Хелли и Борсука // Матем. сб., 1993. Т. 184. № 5. С. 111-132.

19. Евстигнеев В. А., Мельников JL С. Задачи и упражнения по теории графов и комбинаторике. Новосибирск: НГУ, 1981.

20. Севастьянов С. В. Об интервальной раскрашиваемости ребер двудольного графа // Методы дискретного анализа. Вып 50. Новосибирск, 1990. С. 61-72.

21. Amit A., Linian N., Matousek J. Random lifts of graphs III: Independence and chromatic number / / Random Structures &; Algorithms, 2002. V. 20. № 1. P. 1-22.

22. Asratian A. S., Casselgren C. J. On interval edge colorings of (a,{3)~ biregular bipartite graphs // Discrete Math., 2007. V. 307. № 15. P. 19511956.

23. Asratian A. S., Casselgren C. J. On path factors of (3,4)-biregular bigraphs // Graphs & Combinatorics, 2008. V. 24. P. 405-411.

24. Asratian A. S., Casselgren C. J., Vandenbussche J., West D. B. Proper path-factors and interval edge-coloring of (3,4:)-biregular bigraphs //J. Graph Theory (to appear).

25. Asratian A. S., Kamalian R. R. Investigation on interval edge-coloring of graphs // J. of Combinatorial Theory. Ser. B. 1994. V. 62. № 1. P. 34-43.

26. Bafna V., Berman P., Fujito Т. A 2-approximation algorithm for the undirected feedback vertex set problem // SIAM J. on Discrete Math., 1999. V. 12. № 3. P. 289-297.

27. Bansal N., Mahdian M., Sviridenko M. Minimizing makespan in no-wait job shops // Mathematics of Operations Research. 2006. V. 30. № 4. P. 817-831.

28. Barany I. A short proof of Knes er's conjecture //J. Combin. Theory. Ser. A. 1978. V. 25. № 3. P. 325-326.

29. Bodlaender H. L., Kloks T., Tan R. B., van Leeuwen J. A-coloring of graphs // STACS 2000: 17th annual symposium on theoretical aspects of computer science. Proc. Berlin: Springer, 2000. P. 395-406. (Lecture Notes in Computer Sei. V. 1770).

30. Brooks R. L. On coloring the nodes of a network // Proc. Cambridge Phil. Soc. 1941. V. 37. P. 194-197.

31. Brualdi R. A., Massey J. J. Q. Incidence and strong edge coloring of graphs // Discrete Math. 1993. V. 122. № 1-3. P. 51-58.

32. Chang G. J., Kuo D. The L(2,1 )-labeling problem on graphs // SIAM J. Discrete Math. 1996. V. 9. № 2. P. 309-316.

33. Chen Z. Integral sum graphs from identification// Discrete Math. 1998. V. 181. № 1-3. P. 77-90.

34. Damaschke P., Deogun J. S., Kratsch D., Steiner G. Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm // Order. 1992. V. 8. № 4. P. 383-391.

35. Dirac G. A. 4-chrome Graphen Trennende und vollständige A-Graphen // Math. Nachr. 1960. V. 22. № 1-2. P. 51-60.

36. Dirac G. A. In abstrakten Graphen vorhandene vollständige A-Graphen und ihre Unterteilungen // Math. Nachr. 1960. V. 22. № 1-2. P. 61-85.

37. Dolama M. H., Sopena E., Zhu X. Incidence coloring of k-degenera,te graphs // Discrete Math. 2004. V. 283. № 1-3. P. 121-128.

38. Erdös P. Graph theory and probability // Canad. J. Math. 1959. V. 11. P. 34-38.

39. Erdos P. On some aspects of my work with Gabriel Dirac // Graph Theory in Memory of G. A. Dirac. Amsterdam: North-Holland, 1989. P. 111-116. (Annals of Discrete Mathematics, V. 41).

40. Gabor C. P., Supowit K. J., Hsu W.-L. Recognizing circle graphs in polynomial time // J. of the ACM. 1989. V. 36. № 3. P. 435-473.

41. Gallai T. Kritische Graphen I. // Publ. Math. Inst. Hungar. Acad. Sci. 1963. V. 8. № 1-2. P. 165-192.

42. Gallian J. A. A dynamic survey of graph labeling http://www.combinatorics.org/Surveys/ds6.pdf

43. Graham R., Zang N. Enumerating split-pair arrangements //J. Combin. Theory. Ser. A. 2008. V. 115. № 2. P. 293-303.

44. Guiduli B. On incidence coloring and star arboricity of graphs // Discrete Math. 1997. V. 163. № 1-3. P. 275-278.

45. Hanson D., Loten C. O. M., Toft B. On interval colorings of bi-regular bipartite graphs // Ars Combinatoria. 1998. V. 50. P. 23-32.

46. Harary F. Sum graphs and difference graphs // Congr. Numer. 1990. V. 72. P. 101-108.

47. Harary F. Sum graphs over all integers // Discrete Math. 1994. V. 124. № 1-3. P. 99-105.

48. Hartsfield N., Smyth W. F. The sum number of complete bipartite graphs // Graphs, Matrices and Designs. New York: Marcel Dekker. 1993. P. 205211.

49. He W., Wang L., Mi H., Shen Y., Yu X. Integral sum graphs from a class of tree // Ars Combinatoria, 2004. V. 70. P. 197-205.

50. Holyer I. The NP-completeness of edge-coloring // SIAM J. Comput. 1981. V. 10. № 4. P. 718-720.

51. Jensen T. R. Dense critical and vertex-critical graphs // Discrete Math. 2002. V. 258. № 1-3. P. 63-84.

52. Jensen T. R., Royle G. F. Small graphs of chromatic number 5: a computer search // J. Graph Theory. 1995. V. 19. № 1. P. 107-116.

53. Jensen T. R., Toft B. Graph coloring problems. New York: John Wiley & Sons. 1995.

54. Karp R. M. Reducibility among combinatorial problems // Complexity of computer computations. New York: Plenum Press, 1972. P. 85-103.

55. Kitaev S. V., Seif S. Word problem of the Perkins semigroup via directed acyclic graphs // Order. 2008. V. 25. № 3. P. 177-194.

56. Kneser M. Aufgabe 360 // Jahresbericht der Deutschen MathematikerVereinigung, 1955. V. 2. № 58. P. 27.

57. König D. Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre // Math. Ann. 1916. V. 77. P. 453-465.

58. Koester G. Note to a problem of T. Gallai and G. A. Dirac // Combinatorica. 1985. V. 5. № 3. P. 227-228.

59. Koester G. 4-critical 4-valent planar graphs constructed with crowns // Math. Scand. 1990. V. 67. P. 15-22.

60. Lawler E. L. A note on the complexity of the chromatic number problem // Information Processing Letters. 1976. V. 5. № 3. P. 66-67.

61. Lenstra J. K., Hoogeveen H., Yu W. Minimizing makespan in a two-machine flow shop with delays and unit-time operations is NP-hard // J. of Scheduling, 2004. V. 7. № 5. P. 333-348.

62. Li D., Liu M. Incidence coloring of the squares of some graphs // Discrete Math. 2008. V. 308. № 22. P. 6569-6574.

63. Liaw S.-C., Kuo D., Chang G. Integral sum numbers of graphs // Ars Combinatoria. 2000. V. 54. P. 259-268.

64. Lothaire M. Algebraic Combinatorics on Words. Cambridge, UK: Cambridge University Press, 2001.

65. Lovasz L. On chromatic number of finite set-systems // Acta Math. Acad. Sei. Hungar. 1968. V. 19. P. 59-67.

66. Lovasz L. Kneser's conjecture, chromatic number and homotopy // J. Combin. Theory. Ser. A, 1978. V. 25. № 3. P. 319-324.

67. Lovasz L., Plummer M. D. Matching theory. Budapest: Akademiai Kiado, 1986.

68. Lubotzky A., Philips R., Sarnak P. Ramanujan graphs // Combinatorica, 1988. V. 8. P. 261-277.

69. Mader W. Über den Zusammenhäng symmetrischer Graphen // Arch. Math. (Basel). 1970. V. 21. N. 3. P. 331-336.

70. Mader W. Eine Eigenschaft der Atome endlicher Graphen // Arch. Math. (Basel). 1971. V. 22. № 3. P. 333-336.

71. Matousek J. A combinatorial proof of Kneser's conjecture // Combinatorica, 2004. V. 24. № 1. P. 163-170.

72. Melnikov L. S., Vizing V. G. The edge-chromatic number of a directed/mixed multigraph //J. Graph Theory. 1999. V. 23. № 4. P. 267273.

73. Moon J. W., Moser L. On cliques in graphs // Israel J. of Mathematics. 1965. V. 3. P. 23-28.

74. Nesetril J., Rödl V. A short proof of the existence of highly chromatic hypergraphs without short cycles //J. Combin. Theory. Ser. B. 1979. V. 27. № 2. P. 225-227.

75. Nicholas T., Somasimdaram S. More results on integral sum graphs // Proc. of National Conference on Graph Theory and its Applications, Chennai. 2001.

76. Petersen J. Die theorie der regulären graphen // Acta Math. 1891. V. 15. P. 193-220.

77. Razgon I. Exact computation of maximum induced forest // SWAT 2006: 10th Scandinavian workshop on algorithm theory. Berlin: Springer-Verlag, 2006. P. 160-171. (Lecture Notes in Comput. Science. V. 4059)

78. Ringel G. Färbungsprobleme auf Flächen und Graphen. VEB Deutscher Verlag der Wissenschaphten, 1959.

79. Robson J. M. Algorithms for maximum independent sets // J. of Algorithms. 1986. V. 7. № 3. P. 425-440.

80. Sakai D. Labeling chordal graphs: distance two condition // SIAM J. Discrete Math., 1994. V. 7. № 1. P. 133-140.

81. Sarkaria K. S. A generalized Kneser conjecture // J. Combin. Theory. Ser. B. 1990. V. 49. № 2. P. 236-240.

82. Schwikowski B., Speckenmeyer E. On enumerating all minimal solutions of feedback problems // Discrete Applied Math. 2002. V. 117. № 1-3. P. 253-265.

83. Seif S. The Perkins semigroup has co-NP-complete term-equivalence problem // Internat. J. Algebra Comput. 2005. V. 15. № 2. P 317-326.

84. Shannon C. E. A theorem on coloring the lines of a networks //J. Math. Phys., 1949. V. 28, P. 148-151.

85. Sharary A. Integral sum graphs from complete graphs, cycles and wheelsH Arab Gulf J- Scient. Res. 1996. V. 14. № 1. P. 1-14.

86. Shiu W. C., Sun P. K. Invalid poofs on incidence coloring // Discrete Math. 2008. V. 308. № 22. P. 6575-6580.

87. Tarjan R. E., Trojanowski A. E. Finding a maximum independent set // SIAM J. on Computing. 1977. V. 6. № 3. P. 537-546.

88. Watkins M. E. Some classes of hypoconnected vertex-transitive graphs !/ Recent Progress in Combinatorics. New York: Academic Press, 1969. P. 323-328.

89. Watkins M. E. Connectivity of transitive graphs //J. Combin. Theory. 1970. V. 8. № 1. P. 23-29.

90. Woeginger G. Exact algorithms for NP-hard problems: A survey // Combinatorial optimization. 5th international workshop. Berlin: Springer, 2003. P. 185-207. ( Lecture Notes in Comput. Science. V. 2570.)

91. Wu J., Mao J., Li D. New types of integral sum graphs // Discrete Math. 2003. V. 260. № 1-3. P. 163-176.

92. Xu B. On integral sum graphs// Discrete Math. 1999. V. 194. № 1-3. P. 285-294.

93. Yannakakis M. The complexity of the partial order dimension problem // SIAM J. Algebraic Discrete Methods. 1982. V. 3 № 3. P. 351-358.

94. Youngs D. A. Gallai's problem on Dime's construction // Discrete Math. 1992. V. 101. № 1-3. P. 343-350.Публикации автора по теме диссертации Статьи в журналах

95. Визинг В. Г., Мельников JI. С., Пяткин А. В. О (к, I)-раскраске ии-циденторов // Дискрет, анализ и исслед. операций. Сер. 1. 2000. Т. 7. № 4. С. 29-37.

96. Визинг В. Г., Пяткин А. В. О раскраске инцидепторов в ориентированном взвешенном мультиграфе // Дискрет, анализ и исслед. операций. Сер. 1. 2006. Т. 13. № 1. С. 33-44.

97. Добрынин А. А., Мельников JI. С., Пяткин А. В. Критические графы Эрдёша и Дирака четной степени // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10. № 2. С. 12-22.

98. Плеханова H. С., Пяткин А. В. Передача сообщений в локальной сети с двумя центральными ЭВМ // Дискрет, анализ и исслед. операций. Сер. 1. 2002. Т. 9. № 2. С. 91-99.

99. Пяткин А. В. (k, l)-раскраска инциденторов кубических мульти-графов ¡I Дискрет, анализ и исслед. операций. Сер. 1. 2002. Т. 9. № 1. С. 49-53.

100. Пяткин А. В. Некоторые верхние оценки для инциденторного (k, I)-хроматического числа // Дискрет, анализ и исслед. операций. Сер. 1. 2003. Т. 10. № 2. С. 66-78.

101. Пяткин А. В. Верхние и нижние оценки для инциденторного (к, /)-хроматического числа // Дискрет, анализ и исслед. операций. Сер. 1. 2004. Т. 11. № 1. С. 93-102.

102. Пяткин А. В. Об (1,1)-раскраске инциденторов мультиграфов степени 4 // Дискрет, анализ и исслед. операций. Сер. 1. 2004. Т. 11. № 3. С. 59-62.

103. Пяткин А. В. Унициклические целочисленно несуммируемые графы II Дискрет, анализ и исслед. операций. Сер. 1. 2007. Т. 14. № 2. С. 16-24.Pyatkin А. V. Unicyclic nonintegral sum graphs // J. of Applied and Industrial Math. 2008. V. 2. № 3. P. 379-384.

104. Bodlaender H. L., Broersma H., Fomin F. V., Pyatkin A. V., Woeginger G. J. Radio labeling with preassigned frequencies // SIAM J. of Optimization. 2004. V. 15. № 1. P. 1-16.

105. Dobrynin A. A., Melnikov L. S., Pyatkin A. V. On 4-chromatic edge-critical regular graphs of high connectivity // Discrete Math. 2003. V. 260. № 1-3. P. 315-319.

106. Dobrynin A. A., Melnikov L. S., Pyatkin A. V. Regular 4-critical graphs of even degree // J. of Graph Theory. 2004. V. 46. № 2. P. 103-130.

107. Dobrynin A. A., Melnikov L. S., Pyatkin A. V. Erdos regular graphs of even degree // Discussiones Mathematicae Graph Theory. 2007. V. 27. № 2. P. 269-279.

108. Fomin F. V., Gaspers S., Pyatkin A. V., Razgon I. On the minimum feedback vertex set problem: exact and enumeration algorithms // Algorithmica, 2008. V. 52. № 2. P. 293-307.

109. Fomin F. V., Grandoni F., Pyatkin A. V., Stepanov A. A. Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications // ACM Transactions on Algorithms (TALG). 2008. V. 5. № 1. P. 9:1-9:17.

110. Kitaev S. V., Pyatkin A. V. On representable graphs // Journal of Automata, Languages and Combinatorics. 2008. V. 13. № 1. P. 45-54.

111. Melnikov L. S. , Pyatkin A. V. Regular integral sum graphs // Discrete Math. 2002. V. 252. № 1-3. P. 237-245.

112. Pyatkin A. V. Proof of Melnikov-Vizing conjecture for multigraphs with maximum degree at most 3// Discrete Math. 1998. V. 185. № 1-3. P. 275278.

113. Pyatkin A. V. New formula for the sum number for the complete biparitite graphs // Discrete Math. 2001. V. 239. № 1-3. P. 155-160.

114. Pyatkin A. V. A graph with cover degeneracy less than chromatic number // J. of Graph Theory. 2001. V. 37. № 4. P. 243-246.

115. Pyatkin A. V. The incidentor coloring of multigraphs and its applications // Discrete Applied Math. 2002. V. 120. № 1-3. P. 209-217.

116. Pyatkin A. V. 6-regular 4-critical graph // J. of Graph Theory. 2002. V. 41. № 4. P. 286-291.

117. Pyatkin A. V. Interval coloring of (3,4)-biregular bipartite graphs having large cubic subgraphs // J. of Graph Theory. 2004. V. 47. № 2. P. 122-128.

118. Pyatkin A. V. Subdivided trees are integral sum graphs // Discrete Math. 2008. V. 308. № 9. P. 1749-1750.Прочие публикации

119. Визинг В. Г., Мельников JI. С., Пяткин А. В. О (к, I)-раскраске инциденторов / / Международная конференция «Дискретный анализ и исследование операций» (DAOR-2000). Материалы конференции. Новосибирск, 2000. С. 94.

120. Визинг В. Г., Пяткин А. В. Задача раскраски инциденторов мулъ-тиграфа // Российская конференция «Дискретный анализ и исследование операций» (DAOR-2002). Материалы конференции. Новосибирск, 2004. С. 6-11.

121. Добрынин А. А., Мельников Л. С., Пяткин А. В. 4-хроматические реберно-критические регулярные графы с высокой связностью // Российская конференция «Дискретный анализ и исследование операций» (БАОЯ-2002). Новосибирск, 2002. С. 25-30.

122. Пяткин А. В. Задачи поиска оптимального расписания передачи данных в локальной сети связи // Второй Сибирский конгресс по прикладной и индустриальной математике (ШРШМ-96). Тезисы докладов. Новосибирск, 1996. С. 141.

123. Пяткин А. В. Задача окраски инциденторов //IX межгосударственная школа-семинар «Синтез и сложность управляющих систем». Тезисы докладов. Нижний Новгород, 1998. С. 72.

124. Пяткин А. В. О раскраске инциденторов и их применении в теории графов // Конференция молодых ученых, посвященная 100-летию М. А. Лаврентьева. Материалы конференции. Новосибирск, 2000. С. 27-28.

125. Пяткин А. В. (к, I)-раскраска инциденторов и применение инциденторов в теории графов // Конференция молодых ученых по математике, математическому моделированию и информатике. Материалы конференции. Новосибирск, 2001. С. 13-14.

126. Пяткин А. В. Некоторые оценки для максимального числа цветов в (к, I)-раскраске инциденторов // Российская конференция «Дискретный анализ и исследование операций» (БА011-2002). Материалы конференции. Новосибирск, 2002. С. 149.

127. Пяткин А. В. Получение оценок для инциденторного (к,1)-хроматического числа // Материалы III конференции молодых учёных, посвящённой М. А. Лаврентьеву. Новосибирск, 2003. С. 44-47.

128. Пяткин А. В. (к, I)-раскраска инциденторов: некоторые результаты // Российская конференция «Дискретный анализ и исследование операций» (DAOR-2002). Материалы конференции. Новосибирск, 2004. С. 114.

129. Fomin F. V., Gaspers S., Pyatkin A. V. Finding minimum feedback vertex set in time (9((1,7548)n) // Report № 324, Department of Informatics, University of Bergen, 2006. P. 1-7.

130. Fomin F. V., Grandoni F., Pyatkin A. V., Stepanov A. A. On maximum number of minimal dominating sets in graphs // Electronic Notes in Discrete Mathematics. 2005. V. 22. P. 157-162.

131. Fomin F. V., Pyatkin A. V. Finding minimum feedback vertex set in bipartite graph // Report № 291, Department of Informatics, University of Bergen, 2005. P. 1-7.

132. Halldorson M., Kitaev S. V., Pyatkin A. V. On representable graphs, semi-transitive orientations, and the representation numbers // http://arxiv.org/abs/0810.0310

133. Kitaev S. V., Pyatkin A. V. On representable graphs // Report № 312, Department of Informatics, University of Bergen, 2005. P. 1-8.

134. Pyatkin A. V. The incidentor coloring of multigraphs and its application in data networks // Extended Abstracts of the 6th Twenteworkshop on graphs and combinatorial optimization. Netherlands, 1999. P. 197-200.

135. Pyatkin A. V. Results on (k, I)-coloring of incidentors // Proceedings of 8th Nordic combinatorial conference. Aalborg, Denmark, 2004. P. 8386.

136. Pyatkin A. V., Vizing V. G. Incidentor coloring of weighted multigraph // Electronic Notes in Discrete Mathematics. 2006. V. 27. P. 103-104.