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

• Ерусалимский, Яков Михайлович
• доктор физико-математических наук
• 2012

Оглавление диссертации доктор физико-математических наук Ерусалимский, Яков Михайлович

Введение.4 стр.

Глава I. Нестандартная достижимость различных видов. Кратчайшие пути на графах с нестандартной достижимостью.18 стр.

§1.1. Основные определения.18 стр.

§ 1.2. Смешанная достижимость на орграфах.20 стр.

§ 1.3. Магнитная достижимость на орграфах.24 стр.

§ 1.4. Барьерная достижимость на графах.28 стр.

Список литературы диссертационного исследования доктор физико-математических наук Ерусалимский, Яков Михайлович, 2012 год

1. Адельсон-Вельский Г.М., Диниц Е.А., Карзанов A.B. Потоковые алгоритмы //М.: Наука. 1975

2. Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. // -М.: Мир, -1979, 536с.

3. Басакер Р. Конечные графы и сети / Р. Басакер, Т. Саати; пер. с англ.// -М.:Наука, 1973.-368с.

4. Басангова Е.О. Алгоритм нахождения максимального потока в частично-ориентированной сети / Е.О. Басангова, Я.М. Ерусалимский // Дискретные структуры и их приложения. -Элиста: КГУ, -1988. С.23-28.

5. Басангова Е.О. Различные виды смешанной достижимости / Е.О. Басангова, Я.М. Ерусалимский // Алгебра и дискретная математика: сб. -Элиста: КГУ. -1985. С.70-75.

6. Басангова Е.О. Смешанная достижимость на частично-ориентированных графах / Е.О. Басангова, Я.М. Ерусалимский // Вычислительные системы и алгоритмы: сб. -Ростов-на-Дону: РГУ, -1983. С.135-140.

7. Басангова Е. О. Смешанная достижимость на частично-ориентированных графах./Е.О. Басангова, Я.М. Ерусалимский// Деп. в ВИНИТИ. -1982. №5892-82.

8. Водолазов H.H. Об особенностях потока в сетях с барьерной достижимостью // Вестник ДГТУ. -2008 -Т.8. -№2 (37). С. 127-136.

9. Водолазов H.H. Об особенностях потока в сетях с барьерной достижимостью // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения-XIX». Воронеж: ВГУ, 2008. - С.64-66.

10. Диниц Е.А. Метод поразрядного сокращения невязок и транспортные задачи.// Исследования по дискретной математике. -М.:Наука, -1973.

11. Евстигнеев В.А. Применение теории графов в программировании.//-М.: Наука, 1985.

12. Ерусалимский Я.М. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях. / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев-Кав. регион. Естественные науки. -2003. -№2. С.3-5.

13. Ерусалимский Я.М. Графы с нестандартной достижимостью. Задачи, приложения: моногр. / Я.М. Ерусалимский, В.А. Скороходов, М.В. Кузьминова, А.Г. Петросян// -Ростов-на-Дону: ЮФУ, 2009. 195с.

14. Ерусалимский Я.М. Динамические периодические графы / Я.М. Ерусалимский, М.В. Кузьминова. // Математическое моделирование и биомеханика в современном университете: тр. III-й всероссийской школы-семинара. Ростов-на-Дону: Терра Принт, 2007. - С.39-40.

15. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. 4-е издание. //-М.-Вузовская книга, 2001. 280с.

16. Ерусалимский Я.М. Достижимость на графах с условиями затухания и усиления / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев.-Кав. регион. Естественные науки. -2004. Спецвыпуск. Математика и механика. С. 110-112.

17. Ерусалимский Я.М. Многопродуктовые потоки в сетях с нестандартной достижимостью. / Ерусалимский Я.М., Петросян А.Г. // Изв. вузов. Сев.-Кав. регион. Естественные науки. Прил. -2005. -№6. С.8-16.

18. Ерусалимский Я.М. Некоторые задачи достижимости на графах с ограничениями. / Я.М. Ерусалимский, С.Ю. Логвинов // Изв. вузов. Сев.-Кав. регион. Естественные науки. -1996. -№2. С.14-17.-L

19. Ерусалимский Я.М. Бимосты, библоки, точки бисочленения орграфов /Ерусалимский Я.М., Светлов Г.Г.//Кибернетика №1(1980), стр.37-39

20. Ерусалимский Я.М. Графы мостов, блоков и точек сочленения. Графы бимостов, библоков и точек бисочленения/Ерусалимский Я.М., Натанзон Л.^//Известия вузов.Северо-Кавказский регион. Ест.науки, 1998, №4, с

21. Ерусалимский Я.М. Нестационарный и случайный поток в сети/ Я.М. Ерусалимский, H.H. Водолазов // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения-ХХ». -Воронеж: ВГУ, 2009. С.56-57.

22. Ерусалимский Я.М. Нестационарный поток в сети / Я.М. Ерусалимский, H.H. Водолазов // Вестник ДГТУ. -2009. -Т. 9. -№3(42). С.402-409.

23. Ерусалимский Я.М. Потоки в сетях со связанными дугами / Я.М. Ерусалимский, В.А. Скороходов //Изв. вузов. Сев.-Кав. регион. Естественные науки. -2003; прил. № 8. с.9-12.

24. Ерусалимский Я.М. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость / Я.М. Ерусалимский, В.А. Скороходов // Изв. вузов. Сев.-Кав. регион. Естественные науки. Прил. -2003. -№8. -С.3-8.

25. Ерусалимский Я.М. Случайные процессы в сетях с биполярной магнитностью / Я.М. Ерусалимский, А.Г. Петросян // Изв. вузов. Сев.-Кав. регион. Естественные науки. Прил. -2005. -№11. С. 10-16.

26. Ерусалимский Я.М. Эйлеровость графов со смешанной достижимостью // Модели, графы и алгебраические структуры: сб. -Элиста, -1989. С.45-48.eí ib int in ti ■■ iiiiii h i на i in tm n ■■ ■■ i ■ ■ i

27. Ерусалимский Я. M. Дискретная математика: теория, задачи, приложения//М.: Вузовская книга, 4-е издание. 2001.- 280с.

28. Ерусалимский Я.М. Дискретная математика для биоинформа-тиков//Ростов н/Д: Изд-во ЮФУ. 2011, 122с.

29. Зыков A.A. Основы теории графов. //-М.: Вузовская книга , 2004. -664 с.

30. Кристофидес Н. Теория графов. Алгоритмический подход// -М.:Мир, 1978.-432с.

31. Кузьминова М.В. Динамические периодические графы. / М.В. Кузьминова // Современные методы теории краевых задач: материалы Воронежской весенней математической школы «Понтрягинские чтения XVIII». -Воронеж, -2007. С.97-98.

32. Кузьминова М.В. Ограниченные магнитные достижимости на ориентированных графах // Изв. вузов. Сев.-Кав. регион. Естественные науки. Прил. -2006. -№6. с.12-26.

33. Ope О. Теория графов. 2-е изд. // -М.: Наука, 1980. 336с.

34. Петросян А.Г. Многопродуктовые потоки в сетях с ограничениями на достижимость // Математические методы в современных и классических моделях экономики и естествознания: сб. -Ростов-на-Дону, -2005.С.136-138.

35. Петросян А.Г. Потоковая задача в многопродуктовых сетях с нестандартной достижимостью // Современные проблемы математического моделирования: сб. -Ростов-на-Дону, -2005. С.334-340.

36. Петросян А.Г. Потоки в сетях с биполярной достижимостью// Изв. вузов. Сев.-Кав. регион. Естественные науки. Прил. -2006. -№3. С.32-37.

37. Применение теории графов в химии/под ред. Н.С. Зефирова и С.И. Кучанова/'/Новосибирск: Наука, 1988

38. Рейнгольд Э., Нивергельд Ю., Део Н. Комбинаторные алгоритмы. Теория и практика// -М.: Мир, 1980

39. Самуйлов К.Е., Чукарин A.B. К расчету плана маршрутизации сети системы сигнализации №7 // Системы телекоммуникаций и моделирование сложных систем. -М.: ПАИМС, 2001

40. Свами М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман/ пер. с англ. М.:Мир, 1984. - 455с.

41. Скороходов В.А. Устойчивость и стационарное распределение на графах с нестандартной достижимостью // Изв. вузов. Сев.-Кав. регион. Естественные науки. -2007. -№4. С. 17-21.

42. Скороходов В.А. Графы с магнитной достижимостью. Марковские процессы и потоки в сетях//Деп. в ВИНИТИ. -2003. №410-В2003.

43. Скороходов В.А. Случайные блуждания и потоки в сетях с магнитной достижимостью // Модели и дискретные структуры: сб. -Элиста, -2002. -С.93-100.

44. Солтан П.С., Замбицкий Д.К., Присакару К.Ф. Экстремальные задачи на графах и алгоритмы их решения//Кишинев: Штиинца, 1973

45. Форд Л. Р. Потоки в сетях. / JI. Р. Форд, Д.Р. Фалкерсон//; пер. с англ. -М.:Мир, 1966.-276с.

46. Харари Ф. Теория графов. //—М.: Мир, 1973. 300с.

47. Химические приложения топологии и теории графов/под. ред. Р.Кинга, пер. на русск. под ред. Ю.А.Жданова//М.: Мир, 1978

48. Ahuja R. K. A fast and simple algorithm for the maximum flow problem. / R.K. Ahuja, J.B. Orlin. // Oper. Res. -1989. -No.37. pp.748-759.

49. Ahuja R. K. Improved time bounds for the maximum flow problem. / R.K. Ahuja, J.B. Orlin, R.E. Tarjan. // SIAM J. Copmut. -1989. -No. 18. pp.939954.

50. AlonN. Generating pseudo-random permutations and maximum flow algorithms. / N. Alon // Inf. Proc. Lett. -1990. -No.35. pp.201-204.

51. Aronson J.E. A survey of dynamic network flows. / J.E. Aronson // Annals of Operations Research. -No. 20. -1989. pp.1-66.

52. Bang-Jensen J., Gutin G. Digraphs: Theory, Algoritms and Applications//London; Berlin; Heidelberg; New York; Barcelona; Hong Kong; Milan; Singapore; Tokyo: Springer, 2000

53. Dantzig G.B. Application of the simplex method to a transportation problem. / G.B. Dantzig // In Activity Analysis and Production and Allocation. -New York: Wiley, 1951.-pp. 359-373.

54. Dijkstra E.W. A Note in two problems in connection with graphs, Numtrische Mathematic ,1959, #1, p.269

55. Dinic E.A. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. / E.A. Dinic // Sov. Math. Dokl. -1970. -Noll, -pp.1277-1280.

56. Edmonds J. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. / J. Edmonds, R.M. Karp //Journal of the Association for Computing Machinery. Vol. 19. - No. 2, -1972. - pp.248-264.

57. Even S. On the Complexity of Timetable and Multicommodity Flow Problems. / S. Even, A. Itai, A. Shamir. // SIAM J. Comput. -Vol. 5. -No. 4. -1976. pp.691-703.

58. Ford Jr. L.R. Maximal flow through a network. / L.R. Ford Jr., D.R. Fulkerson. // Canad. J. Math. -1956. -No. 8. pp.399-404.

59. Ford L.R. Constructing Maximal Dynamic Flows from Static Flows. / L.R. Ford, D.R. Fulkerson // Operations Research. -1958 -Vol.6 pp.419-433.

60. Gabow H.N. Scaling algorithms for network problems. / H.N. Gabow // J. Comput. Syst. Sei. -1985. -No.31. -pp.148-168.

61. Galiil Z. An 0(EV log2 V) algorithm for the maximal flow problem. / Z. Galiil, A. Naamad. // J. Comput. Syst. Sei. -1980. -No.21. pp.203-217.5 2

62. Galil Z. An 0(F3£3) algorithm for the maximal flow problem. / Z. Galil // Acta Inf. -1980. -No.14. -pp.221-242.

63. Goldberg A. V. A new approach to the maximum-flow problem. / A.V. Goldberg, R.E. Tarjan. //J. ACM. -1988. -Vol.35. -No.4. pp.921-940.

64. Goldberg A. V. A New Approach to the Maximum-Flow Problem. / A.V. Goldberg, R.E. Tarjan // Journal of the Association for Computing Machinery. -Vol.35. -No. 4. -1988. pp.921-940.

65. Goldberg A. V. A new max-flow algorithm. / A.V. Goldberg // Tech. Rep. MIT/LCS/TM-291, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass., Jan. 1985.

66. Goldberg A. V. Beyond the Flow Decomposition Barrier., A.V. Goldberg, S. Rao, // Journal of the ACM. -Vol.45. -No. 5. -1998. pp.783-797.

67. Golombic M.C. Algorithmic Graph Theory and Perfect Graphs//New York: Academic Press, 1980

68. Grady L., Polimeni J. Discrete Calculus: Applied analysis on Graphs for Computational Science// Springer Publishig Company, Inc., NY, 2010, p. 366

69. Graves S.C. A Minimum Concave-Cost Dynamic Network Flow Problem with an Application to Lot-Sizing. / S.C. Graves, J. B. Orlin // Networks -Vol.15. -1985 -pp.59-71.

70. Helmberg C. Network Models with Convex Cost Structure like Bundle Methods. / C. Helmberg // Models and Algorithms for Optimization in Logistics, Dagstuhl Seminar Proceedings. http://drops.dagstuhl.de/opus/volltexte/2009/2190

71. Karp R.M. Reducibility among Combinatorial Problems. / Karp R.M. // Complexity of Computer Computations; R. E. Miller and J. W. Thatcher (editors). -New York: Plenum, 1972. pp.85-103.

72. Karzanov, A. V. Determining the maximal flow in a network by the method of preflows. / A.V. Karzanov // Sov. Math. Dokl. -1974. -No. 15. pp.434-474.

73. King V. A faster deterministic maximum flow algorithm. / V. King, S. Rao, R. Tarjan. // In Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms (Orlando, Fla., Jan. 27-29). ACM, New York, 1992. -pp. 157-164.

74. King V. A faster deterministic maximum flow algorithm. / V. King, S. Rao, R. Tarjan. //J. Algorithms. -1994. -No. 17. -pp.447-474.

75. Kruskal J.B. On the shortes spannig subtree of a graph and the traveling salesman problem, Proc. American Mathematical Soc., 1956, #7, p. 48

76. Lewis T. Network Science: Theory and Applications// Wiley Publ., Hoboken, NJ, 2009. p. 524

77. Lawler E.L. Combinatorial optimization: networks and matroids. / Lawler E.L. -New York: Holt, Rinehart and Winston, 1976. -p.374.

78. Malhorta V.M. An 0(\ V |3) algorithm for finding maximum flows in networks. / V.M. Malhorta, Pramodh Kumar M., S.N. Maheshwari // Inf. Process. Lett. -1978. -No.7. pp.277-278.

79. Newman M. Networks: an Introduction//Oxford University Press, Inc., New York, NY,2010. p.720

80. NingXuanxi. The Blocking Flow Theory and its Application to Hamiltonian Graph Problems. / Ning Xuanxi, Ning Angelika. -Germany, Aachen: Shaker Verlag GmbH, 2006. 249p.

81. Orlin J.B. Maximum-throughput dynamic network flows. / J.B. Orlin // Math. Progr. -1983. -Vol.27, -pp.214-231.

82. Phillips S. Online load balancing and network flow. / S. Phillips, J. Westbrook. // In Proceedings of the 25th Annual ACM Symposium on Theoryof Computing (San Diego, Calif., May 16-18). ACM, New York, 1993. -pp.402-411.

83. Skutella M. An Introduction to Network Flows Over Time. / M. Skutella / Research Trends in Combinatorial Optimization. Berlin: Springer Berlin Heidelberg, -2009. pp.451-482.

84. Sleator D.D. A data structure for dynamic trees. / D.D. Sleator, R.E. Tarjan. / J. Comput. Syst. Sci. -1983. -No.26. pp.362-391.

85. Tarjan R.E. A simple version of Karzanov's blocking flow algorithm // Oper. Res. Lett. -1984. -No.2. -pp.265-268.

86. Ерусалимский Я.М. О функции Гранди орграфов и ядрах его подграфов /Гаряева С.А./ Модели и дискретные структуры, Элиста,93, с.32-37132