Можно ли решить проблему изоморфизма графов за полиномиальное время?
Проблема изоморфизма графов является вычислительной задачей определения , является ли две конечными графами являются изоморфными .
Проблема не решается за полиномиальное время и не является NP-полной , поэтому она может относиться к классу вычислительной сложности NP-промежуточного уровня . Известно , что проблема изоморфизма графов находится в низкой иерархии из класса NP , что означает , что он не является NP-полным , если полином иерархия времени не падает на ее второй уровень. [1] В то же время изоморфизм для многих специальных классов графов может быть решен за полиномиальное время, и на практике изоморфизм графов часто может быть решен эффективно. [2]
Эта проблема является частным случаем задачи подграфа изоморфизма , [3] , который спрашивает , может ли данный граф G содержит подграф, изоморфные другой данный граф Н ; эта проблема, как известно, является NP-полной. Также известно, что это частный случай проблемы неабелевых скрытых подгрупп над симметрической группой . [4]
В области распознавания изображений это известно как точное сопоставление графов . [5]
Уровень развития
В ноябре 2015 года Ласло Бабай анонсировал алгоритм квазиполиномиального времени для всех графов, то есть один со временем выполнения для некоторых фиксированных . [6] [7] [8] [9] 4 января 2017 года Бабай отозвал квазиполиномиальное утверждение и вместо этого указал субэкспоненциальную временную границу после того, как Харальд Хельфготт обнаружил ошибку в доказательстве. 9 января 2017 г. Бабай объявил об исправлении (полностью опубликован 19 января) и восстановил квазиполиномиальное утверждение, а Хельфготт подтвердил исправление. [10] [11] Хельфготт далее утверждает, что можно взять c = 3 , поэтому время выполнения равно 2 O ((log n ) 3 ) . [12] [13]
До этого лучший принятый в настоящее время теоретический алгоритм был разработан Бабаем и Луксом (1983) и основан на более ранней работе Люкса (1982) в сочетании с субфакторным алгоритмом В. Н. Земляченко ( Земляченко, Корнеенко и Тышкевич, 1985 ). Алгоритм имеет время выполнения 2 O ( √ n log n ) для графов с n вершинами и основан на классификации конечных простых групп . Без этой теоремы классификации, немного слабее связанно 2 O ( √ п войти 2 л ) был получен первым для сильно регулярных графов по Ласло Бабаям ( 1980 ), а затем распространяется на общие граф Бабая & Лукс (1983) . Улучшение показателя √ n - большая открытая проблема; для сильно регулярных графов это было сделано Спилманом (1996) . Для гиперграфов ограниченного ранга субэкспоненциальная оценка сверху, соответствующая случаю графов, была получена Бабаем и Коденотти (2008) .
Существует несколько конкурирующих практических алгоритмов изоморфизма графов, например, предложенных Маккеем (1981) , Шмидтом и Друффелем (1976) и Ульманом (1976) . Хотя кажется, что они хорошо работают на случайных графиках , основным недостатком этих алгоритмов является их экспоненциальная временная производительность в худшем случае . [14]
Проблема изоморфизма графов является вычислительно эквивалентна задачей вычисления группы автоморфизмов графа, [15] [16] и слабее , чем группа перестановок проблема изоморфизма и проблема пересечения группы перестановок. Для последних двух проблем Бабай, Кантор и Лукс (1983) получили оценки сложности, аналогичные оценкам для изоморфизма графов.
Решенные частные случаи
Ряд важных частных случаев проблемы изоморфизма графов имеет эффективные решения за полиномиальное время:
- Деревья [17] [18]
- Планарные графы [19] (Фактически, изоморфизм плоских графов находится в лог-пространстве , [20] класс, содержащийся в P )
- Графики интервалов [21]
- Графы перестановок [22]
- Циркулянтные графики [23]
- Графики с ограниченными параметрами
- Графы ограниченной ширины дерева [24]
- Графы ограниченного рода [25] (Планарные графы - это графы рода 0.)
- Графы ограниченной степени [26]
- Графы с ограниченной кратностью собственных значений [27]
- k -Стягиваемые графы (обобщение ограниченной степени и ограниченного рода) [28]
- Сохраняющий цвет изоморфизм цветных графов с ограниченной кратностью цвета (т. Е. Не более k вершин имеют один и тот же цвет при фиксированном k ) находится в классе NC , который является подклассом P [29]
Класс сложности GI
Поскольку не известно, что проблема изоморфизма графов является NP-полной и разрешима, исследователи стремились проникнуть в суть проблемы, определив новый класс GI , набор задач с полиномиальным сведением Тьюринга к изоморфизму графов. проблема. [30] Если на самом деле проблема изоморфизма графов разрешима за полиномиальное время, GI будет равна P . С другой стороны, если проблема NP-полная, GI будет равняться NP, и все проблемы в NP будут разрешимы за квазиполиномиальное время.
Как это обычно бывает для классов сложности в иерархии полиномиального времени , проблема называется GI-сложной, если существует полиномиальное сокращение по Тьюрингу от любой проблемы в GI к этой проблеме, т. Е. Решение за полиномиальное время для GI-сложной задачи. даст полиномиальное решение проблемы изоморфизма графов (и, следовательно, всех проблем в GI ). Проблеманазывается полным для GI или GI-полным , если он является одновременно GI-трудным и решение задачи GI за полиномиальное время дало бы решение за полиномиальное время для.
Проблема изоморфизма графов содержится как в NP, так и в co- AM . GI содержится в низком уровне для Parity P , а также содержится в потенциально гораздо меньшем классе SPP . [31] То, что он лежит в четности P, означает, что проблема изоморфизма графов не сложнее, чем определение того, имеет ли недетерминированная машина Тьюринга с полиномиальным временем четное или нечетное число принимающих путей. GI также содержится в низком уровне для ZPP NP . [32] По сути, это означает, что эффективный алгоритм Лас-Вегаса с доступом к NP- оракулу может решить изоморфизм графов так легко, что он не получит никакой мощности от предоставления возможности делать это в постоянное время.
Проблемы GI-complete и GI-hard
Изоморфизм других объектов
Существует ряд классов математических объектов, для которых проблема изоморфизма является GI-полной проблемой. Некоторые из них представляют собой графы, наделенные дополнительными свойствами или ограничениями: [33]
- орграфы [33]
- помеченные графы , при условии, что изоморфизм не требуется для сохранения меток [33], а только отношение эквивалентности, состоящее из пар вершин с одинаковой меткой
- «поляризованные графы» (состоящие из полного графа K m и пустого графа K n плюс некоторых ребер, соединяющих их; их изоморфизм должен сохранять разбиение) [33]
- 2- цветные графики [33]
- явно заданные конечные структуры [33]
- мультиграфы [33]
- гиперграфы [33]
- конечные автоматы [33]
- Марковские процессы принятия решений [34]
- коммутативные нильпотентные (т. е. xyz = 0 для любых элементов x , y , z ) класса 3 полугруппы [33]
- ассоциативные алгебры конечного ранга над фиксированным алгебраически замкнутым полем с нулевым квадратом радикала и коммутативным множителем над радикалом. [33] [35]
- контекстно-свободные грамматики [33]
- сбалансированные неполные блочные конструкции [33]
- Признавая комбинаторный изоморфизм из выпуклых многогранников , представленных вершинные фасеточных числом случаев. [36]
GI-полные классы графов
Класс графов называется GI-полным, если распознавание изоморфизма для графов из этого подкласса является GI-полной проблемой. Следующие классы являются GI-полными: [33]
- связные графы [33]
- графики диаметра 2 и радиуса 1 [33]
- ориентированные ациклические графы [33]
- регулярные графы [33]
- двудольные графы без нетривиальных сильно регулярных подграфов [33]
- двудольные эйлеровы графы [33]
- двудольные регулярные графы [33]
- линейные графики [33]
- разбиение графов [37]
- хордовые графы [33]
- регулярные самодополняемые графы [33]
- многогранники общих, простых и симплициальных выпуклых многогранников произвольной размерности. [38]
Многие классы орграфов также GI-полны.
Другие проблемы с GI-complete
Помимо проблем изоморфизма, существуют и другие нетривиальные GI-полные проблемы.
- Признание самодополняемости графа или орграфа. [39]
- Проблема клики для класса так называемых М -графов. Показано, что нахождение изоморфизма для n -вершинных графов эквивалентно нахождению n -клики в M -графе размера n 2 . Этот факт интересен тем, что задача нахождения ( n - ε ) -клики в M -графе размера n 2 является NP-полной для сколь угодно малого положительного ε. [40]
- Проблема гомеоморфизма 2-комплексов. [41]
GI-тяжелые проблемы
- Проблема подсчета количества изоморфизмов между двумя графами полиномиально эквивалентна проблеме определения того, существует ли хоть один. [42]
- Проблема определения того, являются ли два выпуклых многогранника, задаваемые V-описанием или H-описанием , проективно или аффинно изоморфными. Последнее означает существование проективного или аффинного отображения между пространствами, содержащими два многогранника (не обязательно одной размерности), которое индуцирует биекцию между многогранниками. [38]
Проверка программы
Мануэль Блюм и Сампат Каннан ( 1995 ) показали вероятностную программу проверки для программ на изоморфизм графов. Предположим, что P - заявленная процедура с полиномиальным временем, которая проверяет, изоморфны ли два графа, но ей не доверяют. Чтобы проверить , изоморфны ли G и H :
- Спросите P , изоморфны ли G и H.
- Если ответ «да»:
- Попытка построить изоморфизм, используя P в качестве подпрограммы. Отметьте вершину u в G и v в H и измените графы, чтобы сделать их отличительными (с небольшим локальным изменением). Спросите P , изоморфны ли модифицированные графы. Если нет, замените v на другую вершину. Продолжайте поиск.
- Либо изоморфизм будет найден (и его можно будет проверить), либо P будет противоречить самому себе.
- Если ответ «нет»:
- Выполните следующие 100 раз. Выберите случайным образом G или H и случайным образом переставьте его вершины. Задать P , если граф изоморфен G и H . (Как в протоколе AM для неизоморфизма графов).
- Если какой-либо из тестов не прошел, оцените P как недопустимую программу. В противном случае ответьте «нет».
- Если ответ «да»:
Эта процедура является полиномиальной и дает правильный ответ, если P - правильная программа для изоморфизма графов. Если P не является правильной программа, но правильно отвечает на G и H , то шашка будет либо дать правильный ответ, или обнаружить недопустимое поведение P . Если P неверная программа и неправильно отвечает на G и H , программа проверки обнаружит недопустимое поведение P с высокой вероятностью или ответит неверно с вероятностью 2 −100 .
Примечательно, что P используется только как черный ящик.
Приложения
Графики обычно используются для кодирования структурной информации во многих областях, включая компьютерное зрение и распознавание образов , а сопоставление графов , то есть идентификация сходства между графами, является важным инструментом в этих областях. В этих областях проблема изоморфизма графов известна как точное сопоставление графов. [43]
В хеминформатике и математической химии проверка изоморфизма графов используется для идентификации химического соединения в химической базе данных . [44] Кроме того, в органической математической химии проверка изоморфизма графов полезна для создания молекулярных графов и для компьютерного синтеза .
Поиск в химической базе данных является примером графического анализа данных , где часто используется подход канонизации графов . [45] В частности, количество идентификаторов для химических веществ , таких , как улыбками и InChI , предназначенных для обеспечения стандартного и удобочитаемый способ для кодирования молекулярной информации и облегчения поиска такой информации в базах данных и на веб, использование этап канонизации в их вычислениях, который по сути является канонизацией графа, представляющего молекулу.
В автоматизации проектирования электроники изоморфизм графов является основой этапа проектирования схемы « компоновка по сравнению со схемой» (LVS), который представляет собой проверку того, идентичны ли электрические цепи, представленные схемной схемой, и компоновкой интегральной схемы . [46]
Смотрите также
- Проблема автоморфизма графа
- Канонизация графа
Заметки
- ^ Шёнинг (1987) .
- ^ Маккей (1981) .
- ^ Ульман (1976) .
- ^ Мур, Рассел и Шульман (2008) .
- ^ Endika Bengoetxea, «неточный График соответствие Используя расчет распределения алгоритмов» , кандидатнаук, 2002,. Глава 2: Проблема граф соответствия (получен 28 июня 2017 года)
- ^ «Математик заявляет о прорыве в теории сложности» . Наука . 10 ноября 2015 года.
- ^ Бабай (2015)
- ↑ Видео первой лекции 2015 года, ссылка на которую есть на домашней странице Бабая.
- ^ «Проблема изоморфизма графов» . Коммуникации ACM . Дата обращения 4 мая 2021 .
- ^ Бабай, Ласло (9 января 2017 г.), Обновление изоморфизма графов
- ^ Erica Klarreich , Изоморфизм графов Побежденные - Опять , Quanta Magazine, 14 января 2017 смотрите здесь
- ^ Хельфготт, Харальд (16 января 2017 г.), Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler-Leman ...) , arXiv : 1701.04372 , Bibcode : 2017arXiv170104372A
- ^ Дона, Даниэле; Баджпай, Джитендра; Хельфготт, Харальд Андрес (12 октября 2017 г.). «Изоморфизмы графов за квазиполиномиальное время». Arxiv : 1710,04574 [ math.GR ].
- ^ Фоджа, Sansone & Vento (2001) .
- ^ Люкс, Евгений (1993-09-01). «Группы перестановок и вычисления за полиномиальное время». Серия DIMACS по дискретной математике и теоретической информатике . 11 . Провиденс, Род-Айленд: Американское математическое общество. С. 139–175. DOI : 10.1090 / dimacs / 011/11 . ISBN 978-0-8218-6599-6. ISSN 1052-1798 .
- ^ Algeboy ( https://cs.stackexchange.com/users/90177/algeboy ), Изоморфизм графа и группа автоморфизма, URL (версия: 2018-09-20): https://cs.stackexchange.com/q/ 97575
- ^ Келли (1957) .
- ↑ Aho, Hopcroft & Ullman (1974) , стр. 84-86.
- ^ Хопкрофт и Вонг (1974) .
- ^ Датта и др. (2009) .
- ^ Booth & Lueker (1979) .
- ^ Colbourn (1981) .
- ^ Музычук (2004) .
- ^ Bodlaender (1990) .
- ^ Миллер 1980 ; Филотти и Майер 1980 .
- ^ Лукс (1982) .
- Перейти ↑ Babai, Grigoryev & Mount (1982) .
- ^ Миллер (1983) .
- ^ Лукс (1986) .
- ↑ Бут и Колборн 1977 ; Кёблер, Шёнинг и Торан, 1993 .
- ^ Kobler, Schöning & Торан 1992 ; Арвинд и Курур 2006
- ^ Эрвинд & Kobler (2000) .
- ^ a b c d e f g h i j k l m n o p q r s t u v w x Земляченко, Корнеенко и Тышкевич (1985)
- ^ Narayanamurthy & Ravindran (2008) .
- ↑ Григорьев (1981) .
- ^ Джонсон (2005) ; Кайбель и Шварц (2003) .
- Перейти ↑ Chung (1985) .
- ^ a b Kaibel & Schwartz (2003) .
- ^ Colbourn & Colbourn (1978) .
- Перейти ↑ Kozen (1978) .
- ^ Shawe-Тейлор & Pisanski (1994) .
- ^ Матон (1979) ; Джонсон 2005 .
- ^ Endika Bengoetxea, доктор философии, абстрактные
- ^ Irniger (2005) .
- ^ Повар и держатель (2007) .
- Перейти ↑ Baird & Cho (1975) .
Рекомендации
- Ахо, Альфред В .; Хопкрофт, Джон ; Ульман, Джеффри Д. (1974), Дизайн и анализ компьютерных алгоритмов , чтение, Массачусетс: Аддисон-Уэсли.
- Арвинд, Викраман; Кёблер, Йоханнес (2000), «Изоморфизм графов низкий для результатов ZPP (NP) и других малых размеров», Труды 17-го ежегодного симпозиума по теоретическим аспектам информатики , Lecture Notes in Computer Science , 1770 , Springer-Verlag, pp. . 431-442 , DOI : 10.1007 / 3-540-46541-3_36 , ISBN 3-540-67141-2, MR 1781752.
- Арвинд, Викраман; Kurur, Piyush P. (2006), "Graph изоморфизм в SPP", информации и вычислений , 204 (5): 835-852, DOI : 10.1016 / j.ic.2006.02.002 , MR 2226371.
- Бабай, Ласло (1980), "О сложности канонической классификации сильно регулярных графов", SIAM журнал по вычислениям , 9 (1): 212-216, DOI : 10,1137 / 0209018 , MR 0557839.
- Бабай, Ласло ; Коденотти, Паоло (2008), «Изоморфизм гиперграфов низкого ранга в умеренно экспоненциальное время» (PDF) , Труды 49-го ежегодного симпозиума IEEE по основам компьютерных наук (FOCS 2008) , IEEE Computer Society, стр. 667–676, DOI : 10.1109 / FOCS.2008.80 , ISBN 978-0-7695-3436-7, S2CID 14025744.
- Бабай, Ласло ; Григорьев, Д.Ю. ; Mount, David M. (1982), «Изоморфизм графов с ограниченной собственным значением кратности», Труды 14 - й ежегодной ACM симпозиум по теории вычислений , С. 310-324,. Дои : 10,1145 / 800070,802206 , ISBN 0-89791-070-2, S2CID 12837287.
- Бабай, Ласло ; Кантор, Уильям ; Luks, Евгений (1983), «Вычислительная сложность и классификация конечных простых групп», Труды 24 - го ежегодного симпозиума Основы информатики (FOCS) , стр 162-171,. DOI : 10,1109 / SFCS.1983.10 , S2CID 6670135.
- Бабай, Ласло ; Luks, Евгений М. (1983), «Каноническое маркировка графов», Труды Пятнадцатый ежегодный ACM симпозиум по теории вычислений (STOC '83) , стр 171-183,. Дои : 10,1145 / 800061,808746 , ISBN 0-89791-099-0, S2CID 12572142.
- Бабай, Ласло (2015), Изоморфизм графов в квазиполиномиальном времени , arXiv : 1512.03547 , Bibcode : 2015arXiv151203547B
- Бэрд, HS; Чо, Й.Е. (1975), "Система проверки дизайна художественного произведения" , Труды 12-й конференции по автоматизации проектирования (DAC '75) , Пискатауэй, штат Нью-Джерси, США: IEEE Press, стр. 414–420.
- Блюм, Мануэль ; Kannan, Сампатх (1995), "Разработка программы , которые проверяют свою работу" , Журнал ACM , 42 (1): 269-291, CiteSeerX 10.1.1.38.2537 , DOI : 10,1145 / 200836,200880 , S2CID 52151779.
- Bodlaender, Ганс (1990), "полиномиальные алгоритмы для изоморфизма графов и хроматического индекса на частичном K -дерев", Journal алгоритмов , 11 (4): 631-643, DOI : 10.1016 / 0196-6774 (90) 90013-5 , Руководство по ремонту 1079454.
- Бут, Kellogg S .; Колборн, CJ (1977), Проблемы, полиномиально эквивалентные изоморфизму графов , Технический отчет, CS-77-04, Департамент компьютерных наук, Университет Ватерлоо.
- Бут, Kellogg S .; Lueker, Джордж С. (1979), "Линейный алгоритм времени для принятия решения интервального изоморфизма графов" , Журнал ACM , 26 (2): 183-195, DOI : 10,1145 / 322123,322125 , MR 0528025 , S2CID 18859101.
- Boucher, C .; Локер, Д. (2006), Полнота изоморфизма графов для совершенных графов и подклассов совершенных графов (PDF) , Технический отчет, CS-2006-32, Департамент компьютерных наук, Университет Ватерлоо.
- Чанг, Вентилятор Р.К. (1985), «О Ширина разреза и топологической ширины полосы дерева», SIAM журнал на алгебраических и дискретных методов , 6 (2): 268-277, DOI : 10,1137 / 0606026 , МР 0778007.
- Colbourn, CJ (1981), "О проверке изоморфизма графов перестановок", сети , 11 : 13-21, DOI : 10.1002 / net.3230110103 , MR 0608916.
- Колборн, Марлен Джонс; Colbourn, Чарльз Дж (1978), "изоморфизм графов и самодополнительных графов", ACM SIGACT News , 10 (1): 25-29, DOI : 10,1145 / 1008605,1008608 , S2CID 35157300.
- Кук, Дайан Дж .; Холдер, Лоуренс Б. (2007), «Раздел 6.2.1: Каноническая маркировка» , Mining Graph Data , Wiley, стр. 120–122, ISBN 978-0-470-07303-2.
- Datta, S .; Limaye, N .; Nimbhorkar, P .; Thierauf, T .; Вагнер, Ф. (2009), «Изоморфизм плоских графов находится в лог-пространстве», 24-я Ежегодная конференция IEEE по вычислительной сложности , 2009 г. , стр. 203, Arxiv : 0809,2319 , DOI : 10,1109 / CCC.2009.16 , ISBN 978-0-7695-3717-7, S2CID 14836820.
- Филотти, ИС; Майер, Джек Н. (1980), «Полином времени алгоритм для определения изоморфизма графов фиксированного рода», Труды 12 - й ежегодной ACM симпозиум по теории вычислений , С. 236-243,. Дои : 10,1145 / 800141,804671 , ISBN 0-89791-017-6, S2CID 16345164.
- Foggia, P .; Sansone, C .; Венто, М. (2001), "Сравнение производительности пяти алгоритмов для изоморфизма графов" (PDF) , Proc. 3-й семинар IAPR-TC15 Графические представления в распознавании образов , стр. 188–199.
- Гарей, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и несговорчивость: Руководство по теории NP-полноты , WH Freeman, ISBN 978-0-7167-1045-5.
- Григорьев, Д.Ю. (1981), «Сложность„диких“матричных задач, изоморфизма алгебр и графов», Записки научных семинаров Ленинградского Otdeleniya Математического института Imeni В. А. Стеклова АН СССР (ЛОМИ) (на русском языке ), 105 : 10-17, 198 , Руководство по ремонту 0628981. Английский перевод в Journal of Mathematical Sciences 22 (3): 1285–1289, 1983.
- Хопкрофт, Джон ; Wong, J. (1974), «время алгоритм Linear изоморфизма планарных графов», Труды Шестой Ежегодной ACM симпозиум по теории вычислений , стр 172-184,. Дои : 10,1145 / 800119,803896 , S2CID 15561884.
- Ирнигер, Кристоф-Андре Марио (2005 г.), Сопоставление графов: фильтрация баз данных графов с использованием машинного обучения , Диссертация на тему: künstlichen Intelligenz, 293 , AKA, ISBN. 1-58603-557-6.
- Kaibel, Volker; Шварц, Александр (2003), "О сложности проблем изоморфизма многогранников" , Графы и комбинаторика , 19 (2): 215–230, arXiv : math / 0106093 , doi : 10.1007 / s00373-002-0503-y , MR 1996205 , S2CID 179936 , заархивировано из оригинала 21.07.2015.
- Келли, Пол Дж (1957), "Конгруэнтность теорема для деревьев", Тихоокеанский журнал математики , 7 : 961-968, DOI : 10,2140 / pjm.1957.7.961 , MR 0087949.
- Кёблер, Йоханнес; Шёнинг, Уве ; Toran, Джакобо (1992), "изоморфизм графов является низким для ПП", вычислительная сложность , 2 (4): 301-330, DOI : 10.1007 / BF01200427 , МР 1215315 , S2CID 8542603.
- Кодзэно, Dexter (1978), "Проблема клики эквивалентно изоморфизма графов", ACM SIGACT News , 10 (2): 50-52, DOI : 10,1145 / 990524,990529 , S2CID 52835766.
- Luks, Евгений М. (1982), «Изоморфизм графов ограниченной валентности может быть проверен в полиномиальное время», журнал компьютерных и системных наук , 25 : 42-65, DOI : 10,1016 / 0022-0000 (82) 90009-5 , Руководство по ремонту 0685360 , S2CID 2572728.
- Люкс, Юджин М. (1986), "Параллельные алгоритмы для групп перестановок и изоморфизм графов", Proc. IEEE Symp. Основы компьютерных наук , стр. 292–302..
- Матон, Рудольф (1979), «Заметка о проблеме подсчета изоморфизма графов», Письма об обработке информации , 8 (3): 131–132, DOI : 10.1016 / 0020-0190 (79) 90004-8 , MR 0526453.
- Маккей, Брендан Д. (1981), "Практический изоморфизм графов" , 10-е. Конференция Манитобы по вычислительной математике и вычислениям (Виннипег, 1980) , Congressus Numerantium, 30 , стр. 45–87, MR 0635936.
- Миллер, Гари (1980), «тестирование Изоморфизм графов ограниченного рода», Труды 12 - й ежегодный симпозиум ACM по теории вычислений , стр 225-235,. Дои : 10,1145 / 800141,804670 , ISBN 0-89791-017-6, S2CID 13647304.
- Миллер, Гэри Л. (1983), "Проверка изоморфизма и канонические формы для k- сжимаемых графов (обобщение ограниченной валентности и ограниченного рода)", Proc. Int. Конф. по основам теории информатики , Lecture Notes в области компьютерных наук , 158 ., С. 310-327, DOI : 10.1007 / 3-540-12689-9_114. Полный текст статьи в Information and Control 56 (1–2): 1–20, 1983.
- Мур, Кристофер ; Рассел, Александр; Шульман, Леонард Дж. (2008), «Симметричная группа не поддается строгой выборке Фурье», SIAM Journal on Computing , 37 (6): 1842–1864, arXiv : Quant-ph / 0501056 , doi : 10,1137 / 050644896 , MR 2386215.
- Музычук, Михаил (2004), "Решение проблемы изоморфизма для циркулянтных графов", Тр. Лондонская математика. Soc. , 88 : 1-41, DOI : 10,1112 / s0024611503014412 , MR 2018956.
- Narayanamurthy, SM; Равиндран, Б. (2008), «О сложности нахождения симметрий в марковских процессах принятия решений» (PDF) , Труды Двадцать пятой Международной конференции по машинному обучению (ICML 2008) , стр. 688–696.
- Schmidt, Douglas C .; Druffel, Ларри Е. (1976), "Быстрый алгоритм возвратов испытаний ориентированных графов для изоморфизма с использованием матриц расстояния", Журнал АСМ , 23 (3): 433-445, DOI : 10,1145 / 321958,321963 , МР 0411230 , S2CID 6163956.
- Шёнинг, Уве (1987), «Изоморфизм графов находится в низшей иерархии», Труды 4-го ежегодного симпозиума по теоретическим аспектам информатики , стр. 114–124; также Journal of Computer and System Sciences 37 : 312–323, 1988.
- Шоу-Тейлор, Джон; Pisanski, Tomaž (1994), "Гомеоморфизм из 2-комплексов изоморфизм графов полный", SIAM журнал по вычислениям , 23 (1): 120-132, DOI : 10,1137 / S0097539791198900 , МР 1258998.
- Спилман, Дэниел А. (1996), "Более быстрое тестирование изоморфизма строго регулярных графов", Труды Двадцать восьмого ежегодного симпозиума ACM по теории вычислений (STOC '96) , ACM, стр. 576–584, ISBN 978-0-89791-785-8.
- Ульман, Джулиан Р. (1976), "Алгоритм подграфа изоморфизма" (PDF) , Журнал ACM , 23 : 31-42, CiteSeerX 10.1.1.361.7741 , DOI : 10,1145 / 321921,321925 , MR 0495173 , S2CID 17268751.
Обзоры и монографии
- Прочтите, Рональд С.; Corneil, Дерек Г. (1977), "Граф болезнь изоморфизмом", Журнал теории графов , 1 (4): 339-363, DOI : 10.1002 / jgt.3190010410 , МР 0485586.
- Гати, Г. (1979), «Дополнительная аннотированная библиография по болезни изоморфизма», Journal of Graph Theory , 3 (2): 95–109, DOI : 10.1002 / jgt.3190030202.
- Земляченко В.Н.; Корнеенко Н.М.; Тышкевич, RI (1985), "Graph проблема изоморфизма", журнал математических наук , 29 (4): 1426-1481, DOI : 10.1007 / BF02104746 , S2CID 121818465. ( В переводе с Записки научных семинаров Ленинградского Otdeleniya Математического института им. В. А. Стеклова АН СССР (отчеты Семинары Ленинградское отделение Математического института им Академии наук СССР ), т. 118, стр. 83-158, 1982.)
- Арвинд, В .; Торан, Якобо (2005), «Проверка изоморфизма: перспективы и открытые проблемы» (PDF) , Бюллетень Европейской ассоциации теоретической информатики , 86 : 66–84. (Краткий обзор открытых вопросов, связанных с проблемой изоморфизма графов, колец и групп.)
- Кёблер, Йоханнес; Шёнинг, Уве ; Торан, Якобо (1993), Проблема изоморфизма графов: ее структурная сложность , Биркхойзер, ISBN 978-0-8176-3680-7. ( С обложки книги : книги фокусируются на проблеме вычислительной сложности задачи и представляют несколько недавних результатов, которые обеспечивают лучшее понимание относительного положения проблемы в классе NP, а также в других классах сложности.)
- Джонсон, Дэвид С. (2005), "NP-полнота Колонка", ACM Сделки по алгоритмам , 1 (1): 160-176, DOI : 10,1145 / 1077464,1077476 , S2CID 12604799. (В этом 24-м выпуске колонки обсуждается современное состояние открытых проблем из книги « Компьютеры и неразрешимость» и предыдущих колонок, в частности, об изоморфизме графов.)
- Торан, Хакобо; Вагнер, Фабиан (2009), «Сложность изоморфизма плоских графов» (PDF) , Бюллетень Европейской ассоциации теоретической информатики , 97 , заархивировано из оригинала (PDF) 20 сентября 2010 г. , извлечено 2010-06- 03.
Программное обеспечение
- Изоморфизм графов , обзор реализаций, The Stony Brook Algorithm Repository .