Приложения теории графов в компьютерных системах

1. 1.

   F. Харари, Теория графов (Addison-Wesley, 1969).

2. 2.

   С. Бердж, Теория графов и их приложения , (Wiley, New York, 1962).

   Google Scholar

3. 3.

   О. Ore, Графики и их использование (Random House, Нью-Йорк, 1963).

   Google Scholar

4. 4.

   Р. Дж. Бусакер и Т.Л. Саати, Конечные графы и сети: Введение в приложения (McGraw-Hill, New York, 1965).

   Google Scholar

5. 5.

   А. В. Ахо, Дж. Э. Хопкрофт и Дж. Д. Уллман, Дизайн и анализ компьютерных алгоритмов (Addison-Wesley, 1974).

6. 6.

   P. Д. Стигалл и О. Тасар, «Обзор ориентированных графов применительно к компьютерам», Computer 7 (10): 39–47 (1974). .

   Google Scholar

7. 7.

   S. Уоршалл, “Теорема о булевых матрицах”, J. ACM 9 (1): 11–12 (1962).

   Google Scholar

8. 8.

   Дж. Дж. Бейкер, «Замечание об умножении булевых матриц», Commun. ACM 5 (2): 102 (1962)..

   Google Scholar

9. 9.

   H. С. Уоррен младший, «Модификация алгоритма Уоршолла для транзитивного замыкания бинарных отношений», Commun. ACM 18 (4): 218–220 (1975).

   Google Scholar

10. 10.

    LE Торелли, «Алгоритм вычисления всех путей в графе», BIT 6 : 347–349 (1966).

    Google Scholar

11. 11.

    Стр. Пурдом, «Алгоритм транзитивного замыкания», BIT 10 (l): 76–94 (1970).

    Google Ученый

12. 12.

    I. Манро, “Эффективное определение транзитивного замыкания ориентированного графа”, Inf. Proc. Буквы 1 : 56–58 (1971).

    Google Scholar

13. 13.

    V. Штрассен, «Гауссово исключение не является оптимальным», Numerische Mathematik 13 : 354–356 (1969).

    Google Scholar

14. 14.

    Дж. К. Тирнан, «Эффективный алгоритм поиска для поиска элементарных схем графа», Commun. ACM 13 (12): 722–726 (1970).

    Google Scholar

15. 15.

    H. Вайнблатт, “Новый алгоритм поиска простых циклов конечного ориентированного графа”, J. ACM 19 (l): 43–56 (1972).

    Google Scholar

16. 16.

    Р. Э. Тарьян, «Перечисление элементарных схем ориентированного графа», SIAM J. Comp. 2 (3; сентябрь): 211–216 ( 1973).

    Google Scholar

17. 17.

    C. В. Рамамурти, «Анализ графов по соображениям связности», J. ACM 13 (2 апреля): 211–222 (1966).

    Google Scholar

18. 18.

    Р. Э. Тарьян, «Поиск в глубину и алгоритмы линейного графа», SIAM J. Comp. 1 (2; июнь): 146–160 (1972). .

    Google Scholar

19. 19.

    C. П. Эрнест, К. Г. Балке и Дж. Андерсон, «Анализ графов путем упорядочения узлов», J. ACM 19 (1): 23–42 (1972).

    Google Scholar

20. 20.

    D. Ф. Мартин и Г. Эстрин, «Модели вычислений и систем — оценка вероятностей вершин в графовых моделях вычислений», J. ACM 14 (2; апрель): 281–299 (1967).

    Google Scholar

21. 21.

    D. Ф. Мартин и Г. Эстрин, «Модели вычислений и систем — преобразования циклического графа в ациклический», IEEE Trans, on Electronic Computers EC-16 ( Февраль): 70–79 (1967).

    Google Scholar

22. 22.

    D. Ф. Мартин и Г. Эстрин, «Эксперименты на моделях вычислений и систем», IEEE Trans, on Electronic Computers EC-16 (февраль): 59 –69 (1967).

    Google Scholar

23. 23.

    D. Ф. Мартин и Г.. Эстрин, «Вычисления длины пути на графовых моделях вычислений», IEEE Trans, on Computers C-18 (июнь): 530–536 (1969).

    Google Scholar

24. 24.

    Дж. Л. Баер, «Обзор некоторых теоретических аспектов многопроцессорной обработки», Computing Surveys 5 (1; March): 31–80 (1973).

    Google Scholar

25. 25.

    Дж. Л. Бэр и Дж. Эстрин, «Границы максимального параллелизма в модели вычислений на билогическом графе», IEEE Trans, on Computers C-18 (11 ): 1012–1014 (1969).

    Google Scholar

26. 26.

    Дж. Л. Баер, Д. П. Бове и Г. Эстрин, «Законность и другие свойства графовых моделей вычислений», J. ACM 17 (3; июль): 543–554 (1970).

    Google Scholar

27. 27.

    Дж. Л. Бэр и Г. Эстрин, «Априорное планирование моделей вычислений на билогическом графе», в Project Planning by Network Analysis (North-Holland, 1969).

28. 28.

    Дж. Л. Баер и Э. К. Рассел, «Подготовка и оценка компьютерных программ для систем параллельной обработки», В Параллельные процессорные системы, технологии и приложения , LC Hobbs et al. , ред. (Spartan Books, New York 1970), стр. 375–415.

    Google Scholar

29. 29.

    Дж. Л. Баер, «Графические модели вычислений», Отчет отдела электротехники Калифорнийского университета в Лос-Анджелесе 6846 (1968).

30. 30.

    Р. М. Карп и Р. А. Миллер, «Свойства модели для параллельных вычислений: детерминированность, завершение, организация очереди», SIAM J. Appl. Математика. 14 (11): 1390–1411 (1966).

    Google Scholar

31. 31.

    Y. Э. Чен и Д. Л. Эпли, «Требования к памяти в многопроцессорной среде», J. ACM 19 (1): 57–69 (1972).

    Google Scholar

32. 32.

    Р. Проссер Т. Применение булевых матриц к анализу блок-схем// Proc. Eeastern Joint Computer Conf. (1960), Vol. 16, pp. 133–138.

    Google Scholar

33. 33.

    A . Шурманн, «Применение графов к анализу распределения циклов в программе», Информация и управление 7 (3): 275–282 (1964). ).

    Google Scholar

34. 34.

    А. Т. Берцтисс, «Заметка о сегментации компьютерных программ», Информация и управление 12 (1): 21–22 (1968).

    Google Scholar

35. 35.

    C. В. Рамамурти, «Аналитический дизайн системы динамического прогнозирования и сегментации программ для многопрограммных компьютеров», в Proc. 21-й ACM Nat. Conf. (1966), pp. 229–239.

36. 36.

    Т. К. Лоу, «Анализ моделей логических программ для сред с разделением времени и разбиением по страницам», Commun. ACM 12 (4): 199–205 (1969).

    Google Scholar

37. 37.

    Т. C. Лоу, «Автоматическая сегментация циклических программных структур на основе возможности подключения и синхронизации процессора», Commun. ACM 13 (l): 3–6 (1970).

    Google Scholar

38. 38.

    К. Саттли и Р. Миллстайн, «Комментарии к статье Лоу», Commun. ACM 13 (7): 450–451 (1970).

    Google Scholar

39. 39.

    E. W. Ver Hoef, «Автоматическая сегментация программ на основе логической связи», в Proc. AFIPS SJCC (1971), Vol. 38 , pp. 491–495.

    Google Scholar

40. 40.

    Дж. Л. Бэр и Р. Кауги, «Сегментация и оптимизация программ на основе анализа циклической структуры», в Proc. AFIPS SJCC (1972), Vol. 40 , pp. 23–36.

    Google Scholar

41. 41.

    B. В. Керниган, “Оптимальные последовательные разбиения графов”, J. ACM 18 (1): 34–40 (1971).

    Google Scholar

42. 42.

    С. Эрнест, «Некоторые темы по оптимизации кода», J. ACM 21 (1): 76–102 (1974).

    Google Scholar

43. 43.

    Дж. Кок и Р. Э. Миллер, «Некоторые методы анализа для оптимизации компьютерных программ», в Proc. 2-я Международная конференция по системным наукам, Гавайи (1969).

44. 44.

    Дж. Кок и Дж. Т. Шварц, «Языки программирования и их компиляторы», Предварительные заметки, Courant Inst, of Math. Наук, Нью-Йоркский университет, Нью-Йорк (1970).

    Google Scholar

45. 45.

    К. Кеннеди, «Алгоритм анализа глобального потока», Int. J. Comp. Математика. 3 (1): 5–15 (1971).

    Google Scholar

46. 46.

    F. Э. Аллен, «Оптимизация программ», в Annual Review in Automatic Programming (1969), Vol. 5.

47. 47.

    F. Э. Аллен, «Анализ потока управления», ACM SIGPLAN Notices 5 , 7 (июль 1970 г.), стр. 1–19.

    Google Scholar

48. 48.

    F. Э. Чужой, «Основа для оптимизации программы», в Proc. Конгресс ИФИП 1971 г. (Северная Голландия).

49. 49.

    М. С. Хехт, Дж. Д. Ульман, “Характеризации приводимых потоковых графов”, J. ACM 21 (3; июль): 367–375 (1974).

    Google Scholar

50. 50.

    Р. Э. Тарьян, “Проверка сводимости потокового графа”, в Proc. 5-й ежегодный симпозиум ACM. по теории вычислений , стр. 96–107.

51. 51.

    M. S. Hecht и JD Ullman, «Сводимость потокового графа», SIAM J. Comp. 1 (2; июнь): 188–202 (1972).

    Google Scholar

52. 52.

    Дж. Кок, «Глобальное исключение общих подвыражений», ACM SIGPLAN Notices, 5, 7 (июль 1970), стр. 20–24.

    Google Scholar

53. 53.

    Дж. Д. Ульман, «Быстрые алгоритмы исключения общих подвыражений», Acta Informatica 2 (3; декабрь): 191–213 (1973)..

    Google Scholar

54. 54.

    D. Х. Р. Хакстейбл, «О написании оптимизирующего транслятора для АЛГОЛА 60», в Introduction to System Programming , P. Wegner, ed. (Academic Press, 1964), стр. 137–155.

55. 55.

    E. Н. Хокинс и Д. Х. Р. Хакстейбл, «Схема многопроходного перевода для АЛГОЛА 60», в Annual Review in Automatic Programming (1962), Vol. 3. С. 163–205.

    Google Scholar

56. 56.

    E . С. Лоури и К. В. Медлок, «Оптимизация объектного кода», Commun. ACM 12 (1): 13–22 (1969).

    Google Scholar

57. 57.

    Р. Л. Клейр и К. В. Рамамурти, «Стратегии оптимизации для микропрограмм», Trans. IEEE на компьютерах C-20 (7): 783–794 (1971).

    Google Scholar

58. 58.

    С. Рамамурти В. и Клейр Р. Л., «Обзор методов оптимизации микропрограмм», в Proc. 3-й ежегодный семинар по микропрограммированию, Буффало, Нью-Йорк (1970).

59. 59.

    Дж. Л. Шварцфитер и П. Э. Лауэр, «Нахождение элементарных циклов ориентированного графа в O (N + M) за цикл», Tech. Представитель № 60, Лаборатория вычислительной техники. Univ. Ньюкасл-апон-Тайн, Англия (май 1974 г.).

    Google Scholar

60. 60. С. В. Рамамурти и М. Дж. Гонсалес, «Обзор методов распознавания параллельных обрабатываемых потоков в компьютерных программах», в Proc. AFIPS FJCC (1969), Vol. 35, стр. 1–15.

    Google Scholar

61. 61.

    C. В. Рамамурти и М. Дж. Гонсалес, «Распознавание и представление параллельных обрабатываемых потоков в компьютерных программах II (параллелизм задачи/процесса)», в Proc. 24-й ACM Nat. Conf. (1969), pp. 387–397.

62. 62.

    E. К. Рассел, «Автоматический анализ программ», Ph.D. Диссертация, кафедра электр. Eng., UCLA (1969).

63. 63.

    Дж. М. С. Симоэс-Перейра, «О булевом матричном уравнении M ′ = U _{i = 1} ^∞ M ′», Дж. ACM 12 (3; июль): 376–382 (1965).

    Google Scholar

64. 64.

    L. У. Джексон и С. Дасгупта, «Идентификация параллельных микроопераций», Inf. Proc. Письма 2 : 180–184 (1974).

    Google Scholar

65. 65.

    Р. М. Карп, «Заметка о применении теории графов к программированию цифровых компьютеров», Информация и управление 3 (6): 179–190 (1960). ).

    Google Scholar

66. 66.

    C. Рамамурти В. Дискретный марковский анализ компьютерных программ// Proc. 20-й ACM Nat. Conf. (1965), pp. 386–392.

67. 67.

    J. Д. Фоли, «Марковская модель исполнительной системы Мичиганского университета», Commun. ACM 10 (9): 584–589 (1967).

    Google Scholar

68. 68.

    W. С. Боуи, «К распределенной архитектуре для OS/360», Ph.. Докторская диссертация, кафедра прикладного анализа и компьютерных наук, Univ. Ватерлоо, Ватерлоо, Онтарио, Канада (1974).

    Google Scholar

69. 69.

    W. С. Боуи, Дж. Г. Линдерс и У. Раштон, «Программа отслеживания трассировки для OS/360», в Proc. Canadian Inf. Proc. Soc. Конф. Регина, Саскачеван, Канада (июнь 1975 г.) .

70. 70.

    М. Дж. Гонсалес и К.В. Рамамурти, «Параллельное выполнение задач в децентрализованной системе», IEEE Trans, on Computers C-21 (12): 1310–1322 (1972).

    Google Scholar

71. 71.

    Дж. М. Фили, «Монитор производительности компьютера и марковский анализ для оценки многопроцессорной системы», в Statistical Computer Performance Evaluation , W. Frieberger, ed. (Academic Press, 1972), стр. 165–225.

72. 72.

    Т. К. Лоу, «Анализ модели информационной системы со штрафами за передачу», IEEE Trans, on Computers C-22 (5): 469–480 ( 1973).

    Google Scholar

73. 73.

    Р. К. Холт, «Некоторые тупиковые свойства компьютерных систем», Computing Surveys 4 (3; сентябрь): 179–196 (1972).

    Google Scholar

74. 74.

    Дж. Э. Мерфи, «Распределение ресурсов с обнаружением блокировки в многозадачной системе», в Proc. AFIPS FJCC (1968), том 33 , часть 2, стр. 1169–1176.

    Google Scholar

75. 75.

    стр. Г. Хебалкар, “Графическая модель для анализа предотвращения тупиковых ситуаций в системах с параллельными вычислениями”, в Proc. Конгресс ИФИП, 1971 , стр. 498–503.

76. 76.

    E. Дж. Коффман, MJ Элфик и А. Шошани, «Системные тупики», Computing Surveys 3 (2; июнь): 67–78 (1971). .

    Google Scholar

77. 77.

    К. М. Чанди и К.В. Рамамурти, «Стратегии отката и восстановления для компьютерных программ», IEEE Trans, on Computers C-21 (6): 546–556 (1972).

    Google Scholar

78. 78.

    W. Майеда и К.В. Рамамурти, «Критерии различимости ориентированных графов и их применение в компьютерной диагностике — I», IEEE Trans, по теории цепей CT-16 (ноябрь ): 448–454 (1969).

    Google Scholar

79. 79.

    С. Рамамурти В. Структурная теория машинной диагностики// Proc. AFIPS SJCC (1967), Vol. 30 , pp. 743–756.

    Google Scholar

80. 80.

    C. В. Рамамурти и Л. К. Чанг, «Системное моделирование и процедуры тестирования для микродиагностики», IEEE Trans, on Computers C-21 (11): 1169–1183 (1972).

    Google Scholar

81. 81.

    С. В. Рамамурти и Л. К. Чанг, «Системная сегментация для параллельной диагностики компьютеров», IEEE Trans, on Computers C-20 (3): 261– 270 (1971).

    Google Scholar

Загрузить ссылки

1. Уильям С. Боуи
   Просмотреть публикации автора

   Вы также можете выполнить поиск этого автора в PubMed Google Scholar