Проблем изоморфизма графова

Проблем изоморфизма графова је рачунарски проблем утврђивања да ли су два коначна графа изоморфна.

Поред практичног значаја, проблем изоморфизма графова је веома занимљив у рачунарској теорији комплексности као један од ретких проблема који припадају НП, за који се не зна да ли је решив у полиномијалном времену нити да ли је НП-комплетан: један је од 12 проблема који се налазе на листи Гареy & Јохнсон 1979, и један од само два проблема чија комплексност остаје нерешива (други је Растављање на факторе)^[1]. Од 2008 године најбољи алгоритам за графове са н темена (Еугене Лукс, 1983) је сложености 2^{О(√(н лог н))}.^[2]^[3]

Познато је да се проблем изоморфизма графова налази на нижем нивоу хијерархије класе НП, што говори да није НП-комплетан осим ако на лествици полиномијалног времена не достиже други ниво.^[4]

Истовремено, изоморфизам за неке специјалне графове може бити решен у полиномијалном времену, а у пракси изоморфизам графова се обично ефикасно решава.^[5]

Овај проблем је специјална врста проблема изоморфизма подграфа^[6], за који се зна да је НП-комплетан. Познат је као специјалан случај проблема не-абелове скривене подгрупе преко симетричних група.^[7]

Историја

Садашњи најбољи алгоритам је алгоритам који је осмислио Еугене Лукс (1983) и базиран је на ранијим радовима Лукса (1981), Бабаија и Лукса (1982) комбинован са подфакторијалним алгоритмом Земљашенка. Алгоритам је заснован на класификацији коначних простих група. Без ове класификације ЦФСГ, добијена је несто слабија граница 2^{О(√н лог² н)},прво за јаке регуларне графове Лазло Баблаи , (1980), а затим су је Бабаи и Лукс (1982) проширили на опште графове. Побољшање експонента √н је главни отворени проблем; за јаке регуларне графове то је решио Спиелман 1996 (1996). За хиперграфове ограниченог ранга,где субекспоненцијална горња граница одговара случају графова, решење/одговор су недавно нашли Бабаи и Цаденотти.

Проблем изоморфизма графова је рачунски еквивалентан проблему израчунавања аутоморфизма групе графа, и слабији је од проблема изоморфизма пермутационих група, и од проблема пресека пермутационих група. За последња два проблема Бабаи, Кантор и Лукс (1983) су добили границе сложености сличне онима за изоморфизам графова.^[8]

Постоји неколико конкурентних практичних алгоритама за изоморфизме графова,које су поставили МцКаy (1981), Сцхмидт & Друффел (1976), Уллман (1976), и тако даље. Иако делује да се извршава добро на случајним графовима,главни недостатак ових алгоритама је њихова експоненцијална временска сложеност у најгорем случају.^[9]

Специјални случајеви

Листа специјалних случајева проблема изоморфизма графова, који имају ефикасно решење у полиномијалном времену:

Стабла^[10]
Планарни графови^[11] (У ствари, изоморфизам планарних графова се решава у логаритамском времену,^[12] класа која је се налази у П)
Тежински графови^[13]
Пермутациони графови^[14]
Делимична к-стабла^[15]
Графови са ограниченом вредношћу неких параметара
- Графови ограниченог рода^[16](Планарни графови су графови рода 0)
- Графови ограниченог степена^[17]
- к-контрактибилни графови(уопштени графови ограниченог рода и степена)^[18]
- Изоморфизам обојивих графова са ограниченом вредношћу боја (већина чворова имаће исту боју за фиксирану вредност боја к) је класе НЦ, која је подкласа класе П.^[19]

Сложена класа ГИ

Пошто се за проблем изоморфизма графова не зна да ли је НП-комплетан, нити да ли је обрадив, истраживачи су настојали да стекну бољи увид у овај проблем дефинисањем нове класе ГИ, кроз низ проблема који су решиви у полиномијалном времену.^[20] У ствари ако би проблем изоморфизма графова био решив у полиномијалном времену онда би ГИ класа била једнака са П

Као што је уобичајено за комплексне класе које се решавају у полиномијалном времену, проблем се назива ГИ-тежак ако постоји Тјурингова редукција било ког проблема ГИ класе до тог проблема у полиномијалном времену, односно полиномијално-временско решење неког ГИ-тешког проблема би се добило уз помоћ проблема изоморфизма графова који се такође решава у полиномијалном времену (ово важи за све проблеме ГИ класе). Проблем $X$ је комплетан за ГИ, или је ГИ-комплетан

Проблем изоморфизма графова садржан је у НП и цо-АМ. ГИ је мање исадржан и/у Паритy П, а такође је део потенцијално много мање класе СПП.^[21] То да лежи у Паритy П значи да проблем изоморфизма графова није ништа тежи од одређивања да ли је полиномијално-време уопште могуће детерминисати. Тјурингова машина има паран или непаран број прихватања путања. ГИ је такође садржан и низак за ЗПП^НП.^[22]. Ово суштински значи да ефикасан Лас Вегас алгоритам са приступом НП ораклу може да реши изомофизме графова тако лако, да чак не добија никакву моћ стицањем могућности да то уради у константном времену.

ГИ-комплетни и ГИ-тешки проблеми

Проблем изоморфизма неких других објеката

Постоји велики број класа математичких објеката за које је проблем изоморфизма графова ГИ-комплетан. Неки од њих су графови са неким додатним својствима или ограничењима:^[23]

директни графовии^[23]
етикетирани графови, под условом да изоморфизам не треба да памти све етикете,^[23] већ само оне које припадају теменима са истим етикетама
"поларизовани графови" (који се састоје од комплетних графова К_м и празних графова и од још неких грана које повезују та два графа; њихов изоморфизам мора да чува поделу)^[23]
2-обојиви графови^[23]
експлицитно дати графови са коначном структуром^[23]
мултиграфови^[23]
хипер графови^[23]
коначно изгенерисани^[23]
Марков процес одлучивања^[24]
комутативна 3-нилпотентна(пример: xyз=0 за све елементе x,y,з) полугрупа^[23]
Контекстно-слободна граматика^[23]
Непотпуно балансирани блок дизајн^[23]

ГИ-комплетне класе графова

Класа графова се назива ГИ-комплетна ако је проблем изоморфизма графова из ове групе ГИ-комплетан. Следеће класе су ГИ-комплетне:^[23]

повезани графови^[23]
графови чији је дијаметар једнак 2 а радиус 1^[23]
директни ациклични графови^[23]
регуларни графови^[23]
бипартитивни графови без не-тривијалних регуларних подграфова^[23]
бипартитивни Ојлерови графови^[23]
бипартитивни регуларни графови^[23]
линијски графови^[23]
сплит графови^[25]
цхордал грапхс^[23]
регуларни само-комплементарни графови^[23]

Ова листа није употпуњена! Доста класа диграфова такодје су ГИ-комплетне.

Остали ГИ-комплетни проблеми

Постоје и неки други нетривијални ГИ-комплетни проблеми поред проблема изоморфизма графова:

Проналажење само-комплементарних графова или диграфова.^[26]
Проблем клике за такозвану класу M-графова. Показало се да је проналажење изоморфизма за н-највише тачке графова еквивалентно проналажењу н-клика у M-графу величине н². Ова чињеница је интересантна јер је проблем проналажења (н − ε)-клике у M-графу величине н² НП-комплетан за произвољно мало ε.^[27]
Проблем хомеоморфизма 2-комплекса.^[28]

ГИ-тешки проблеми

Проблем бројања изоморфизма између два графа је полиномијалног времена еквивалентан проблему који говори да ли неки од та два графа уопште постоји.^[29]
Проблем одлучивања да ли два конвексна политопа добијена или V-описом или Х-описом су " пројецтивелy ор аффинелy изоморфни", што значи да постоји пројецтиве ор аффине мапа између простора који садрже два политопа (не нужно истих димензија) које укључује бијаицију између два политопа.

Провера програма

Блум анд Каннан^[30] су представили програм који проверава изоморфизме графова. Узмимо да се за П тврди да је полиномијално-временска процедура која проверава да ли су два графа изоморфна, али није поуздан. Да би се проверило да ли су Г и Х изоморфни:

Питати П да ли су Г и Х изоморфни.
- Ако је одговор "да":
  - Покушати конструисање изоморфизма користећи П као субрутину. Означити теме у Г и в у Х, I модификовати графове како би постали различити (са малом локалном променом). Питати П да ли су модификовани графови изоморфни. Ако не, померити в на друго теме/вертеx. Наставити са претрагом.
  - Изоморфизам или ће бити пронађен (и моћи ће да буде верификован) или ће П противречити сам себи.
- Ако је одговор "не":
  - Извести следеће 100 пута. Изабрати насумично Г или Х, и насумично пермутовати њихова темена(вертицес). Питати П да ли је граф изоморфанза Г и Х. (као у АМ протоколу за неизоморфизам графова).
  - Ако било који од од тестова буду негативни, оценити П као неисправан(инвалид) програм. У супротномо дговор је "не".

Ова процедура је полиномијално-временска,и даје исправан одговор ако је П тачан програм за изоморфизме графова. Ако П није одговарајући програм али исправно одговори на Г и Х,контрола ће или дати тачан одговор, или ће детектовати неважеће понашање П.Ако П није одговарајући програм, а нетачноодговоринаГ и Х,контролаћесавеликомвероватноћом,детектоватинеисправнопонашањекод П, а са вероватноћом 2⁻¹⁰⁰ ће одговорити погрешно.

Напомена,П је коришћен само као 'блацкбоx'.

Примене

У хеминформатици и математичкој хемији, тестирање изоморфизма графова користи се за проналажење хемијског једњења у хемијској бази.^[31] Такође, у органској математичкој хемији тестирање изоморфизма графова корисно је за генеразиционе молекуларне графове и за компијутерску синтезу.

Претрага хемијске базе је пример анализе података помоћу графова у којем се приступ канонизације графова често користи.^[32]Један број идентификатора за хемијске супстанце као што су СМИЛЕС и ИнЦхИ, који су направљени да обезбеде стандардизовани читљив начин за кодирање молекуларних информација као и да омогући претрагу таквих информација у базама података на интернету,користе канонизацијски корак у свом рачунању, што је у суштини канонизација графа који представља молекул. У аутоматизацији електронског дизајна, изоморфизам графова је основа Лаyоут Версус Сцхематиц (ЛВС) цирцуит десигн степ, који верификује да ли су електрично коло представљена прикладном схемом и схема интегрисаног кола исте.^[33]

Референце

^ Тхе латест оне ресолвед wас минимум-wеигхт триангулатион, провед то бе НП-цомплете ин 2006. Мулзер, Wолфганг; Роте, Гüнтер (2008), „Минимум-wеигхт триангулатион ис НП-хард”, Јоурнал оф тхе АЦМ, 55 (2): 1, С2ЦИД 1658062, арXив:цс.ЦГ/0601002  , дои:10.1145/1346330.1346336
^ Јохнсон 2005
^ Бабаи & Цоденотти 2008
^ Уwе Сцхöнинг, "Грапх исоморпхисм ис ин тхе лоw хиерарцхy", Процеедингс оф тхе 4тх Аннуал Сyмпосиум он Тхеоретицал Аспецтс оф Цомпутер Сциенце, 1987, 114-124; алсо: Јоурнал оф Цомпутер анд Сyстем Сциенцес, вол. 37 (1988), 312-323
^ МцКаy 1981
^ Уллман 1976
^ Цристопхер Мооре; Русселл, Алеxандер; Сцхулман, Леонард Ј. (2005). „Тхе Сyмметриц Гроуп Дефиес Стронг Фоуриер Самплинг: Парт И”. арXив:qуант-пх/0501056в3  [qуант-пх].
^ Лáсзлó Бабаи, Wиллиам Кантор, Еугене Лукс, Цомпутатионал цомплеxитy анд тхе цлассифицатион оф фините симпле гроупс, Проц. 24тх ФОЦС (1983). стр. 162.–171.
^ П. Фоггиа, C.Сансоне, M. Венто, А Перформанце Цомпарисон оф Фиве Алгоритхмс фор Грапх Исоморпхисм Архивирано на сајту Wayback Machine (24. септембар 2015), Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition. (2001). стр. 188–199.
^ P.J. Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957). стр. 961.–968; Aho, Hopcroft & Ullman 1974
^ Hopcroft & Wong 1974
^ Datta, Samir; Limaye, Nutan; Nimbhorkar, Prajakta; Thierauf, Thomas; Wagner, Fabian (2009). „Planar Graph Isomorphism is in Log-Space”. 2009 24th Annual IEEE Conference on Computational Complexity. стр. 203—214. ISBN 978-0-7695-3717-7. doi:10.1109/CCC.2009.16.
^ Booth & Lueker 1979
^ Colbourn 1981
^ Bodlaender 1990
^ Miller 1980; Filotti & Mayer 1980
^ Luks 1982
^ Gary L. Miller: Isomorphism Testing and Canonical Forms for k-Contractable Graphs (A Generalization of Bounded Valence and Bounded Genus). Proc. Int. Conf. on Foundations of Computer Theory, (1983). стр. 310-327 (Lecture Notes in Computer Science, vol. 158, full paper in: Information and Control, 56(1-2):1–20, 1983.)
^ Eugene Luks, "Parallel algorithms for permutation groups and graph isomorphism", Proc. IEEE Symp. Foundations of Computer Science. (1986). стр. 292–302.
^ Booth & Colbourn 1977; Köbler, Schöning & Torán 1993
^ Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
^ Arvind & Köbler 2000
^ ^а ^б ^в ^г ^д ^ђ ^е ^ж ^з ^и ^ј ^к ^л ^љ ^м ^н ^њ ^о ^п ^р ^с ^т ^ћ Zemlyachenko, Korneenko & Tyshkevich 1985
^ "On the hardness of finding symmetries in Markov decision processes", by SM Narayanamurthy, B Ravindran, Proceedings of the Twenty Fifth International Conference on Machine Learning (ICML 2008). стр. 688-696.
^ Chung, Fan RK (1985). „On the cutwidth and the topological bandwidth of a tree”. SIAM Journal on Algebraic Discrete Methods. 6 (2): 268—277. doi:10.1137/0606026. Приступљено 13. 4. 2015.
^ Colbourn M.J., Colbourn Ch.J. "Graph isomorphism and self-complementary graphs", SIGACT News, 1978, vol. 10, no. 1, 25-29.
^ Kozen 1978
^ J. Shawe-Taylor, T.Pisanski, "Homeomorphism of 2-Complexes is Graph Isomorphism Complete", SIAM Journal on Computing, 23 (1994) 120 - 132 .
^ R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979). стр. 131—132; Johnson 2005
^ Designing Programs that Check their Work
^ Christophe-André Mario Irniger. Graph Matching: Filtering Databases of Graphs Using Machine Learning. 2005. ISBN 978-1-58603-557-0.
^ Цоок, Диане Ј.; Холдер, Лаwренце Б. (2006). Мининг Грапх Дата. Јохн Wилеy & Сонс. стр. 120—122. ИСБН 978-0-470-07303-2.
^ Баирд, ХС; Цхо, YЕ (1975). Ан артwорк десигн верифицатион сyстем. Процеедингс оф тхе 12тх Десигн Аутоматион Цонференце. ИЕЕЕ Пресс. стр. 414—420.

Литература

Ахо, Алфред V.; Хопцрофт, Јохн; Уллман, Јеффреy D. (1974), Тхе Десигн анд Аналyсис оф Цомпутер Алгоритхмс, Реадинг, МА: Аддисон-Wеслеy .
Арвинд, Викраман; Кöблер, Јоханнес (2000), „Грапх исоморпхисм ис лоw фор ЗПП(НП) анд отхер лоwнесс ресултс.”, Процеедингс оф тхе 17тх Аннуал Сyмпосиум он Тхеоретицал Аспецтс оф Цомпутер Сциенце, Лецтуре Нотес ин Цомпутер Сциенце, 1770, Спрингер-Верлаг, стр. 431—442, ИСБН 978-3-540-67141-1, ОЦЛЦ 43526888 .
Арвинд, Викраман; Курур, Пиyусх П. (2006), „Грапх исоморпхисм ис ин СПП”, Информатион анд Цомпутатион, 204 (5): 835—852, дои:10.1016/ј.иц.2006.02.002 .
Бабаи, Лáсзлó; Цоденотти, Паоло (2008). „Исоморпхисм оф Хyперграпхс оф Лоw Ранк ин Модерателy Еxпонентиал Тиме”. ФОЦС '08: Процеедингс оф тхе 2008 49тх Аннуал ИЕЕЕ Сyмпосиум он Фоундатионс оф Цомпутер Сциенце. ИЕЕЕ Цомпутер Социетy. стр. 667—676. ИСБН 978-0-7695-3436-7. .
Бабаи, Лáсзлó; Григорyев, D. Yу.; Моунт, Давид M. (1982), „Исоморпхисм оф грапхс wитх боундед еигенвалуе мултиплицитy”, Процеедингс оф тхе 14тх Аннуал АЦМ Сyмпосиум он Тхеорy оф Цомпутинг, стр. 310—324, ИСБН 978-0-89791-070-5, С2ЦИД 12837287, дои:10.1145/800070.802206 .
Бодлаендер, Ханс (1990), „Полyномиал алгоритхмс фор грапх исоморпхисм анд цхроматиц индеx он партиал к-треес”, Јоурнал оф Алгоритхмс, 11 (4): 631—643, дои:10.1016/0196-6774(90)90013-5 .
Боотх, Келлогг С.; Цолбоурн, C. Ј. (1977), Проблемс полyномиаллy еqуивалент то грапх исоморпхисм, Тецхницал Репорт ЦС-77-04, Цомпутер Сциенце Департмент, Университy оф Wатерлоо .
Боотх, Келлогг С.; Луекер, Георге С. (1979), „А линеар тиме алгоритхм фор децидинг интервал грапх исоморпхисм”, Јоурнал оф тхе АЦМ, 26 (2): 183—195, С2ЦИД 18859101, дои:10.1145/322123.322125 .
Боуцхер, C.; Локер, D. (2006), Грапх исоморпхисм цомплетенесс фор перфецт грапхс анд субцлассес оф перфецт грапхс (ПДФ), Университy оф Wатерлоо, Тецхницал Репорт ЦС-2006-32 .
Цолбоурн, C. Ј. (1981), „Он тестинг исоморпхисм оф пермутатион грапхс”, Нетwоркс, 11: 13—21, дои:10.1002/нет.3230110103 .
Филотти, I. С.; Маyер, Јацк Н. (1980), „А полyномиал-тиме алгоритхм фор детермининг тхе исоморпхисм оф грапхс оф фиxед генус”, Процеедингс оф тхе 12тх Аннуал АЦМ Сyмпосиум он Тхеорy оф Цомпутинг, стр. 236—243, ИСБН 978-0-89791-017-0, С2ЦИД 16345164, дои:10.1145/800141.804671 .
Гареy, Мицхаел Р.; Јохнсон, Давид С. (1979), Цомпутерс анд Интрацтабилитy: А Гуиде то тхе Тхеорy оф НП-Цомплетенесс, W. Х. Фрееман, ИСБН 978-0-7167-1045-5, ОЦЛЦ 11745039 .
Хопцрофт, Јохн; Wонг, Ј. (1974), „Линеар тиме алгоритхм фор исоморпхисм оф планар грапхс”, Процеедингс оф тхе Сиxтх Аннуал АЦМ Сyмпосиум он Тхеорy оф Цомпутинг, стр. 172—184, С2ЦИД 15561884, дои:10.1145/800119.803896 .
Кöблер, Јоханнес; Сцхöнинг, Уwе; Торáн, Јацобо (1992), „Грапх исоморпхисм ис лоw фор ПП”, Цомпутатионал Цомплеxитy, 2 (4): 301—330, С2ЦИД 8542603, дои:10.1007/БФ01200427 .
Кöблер, Јоханнес; Сцхöнинг, Уwе; Торáн, Јацобо (1993), Тхе Грапх Исоморпхисм Проблем: Итс Струцтурал Цомплеxитy, Биркхäусер, ИСБН 978-0-8176-3680-7, ОЦЛЦ 246882287 .
Козен, Деxтер (1978), „А цлиqуе проблем еqуивалент то грапх исоморпхисм”, АЦМ СИГАЦТ Неwс, 10 (2): 50—52, С2ЦИД 52835766, дои:10.1145/990524.990529 .
Лукс, Еугене M. (1982), „Исоморпхисм оф грапхс оф боундед валенце цан бе тестед ин полyномиал тиме”, Јоурнал оф Цомпутер анд Сyстем Сциенцес, 25: 42—65, дои:10.1016/0022-0000(82)90009-5 .
МцКаy, Брендан D. (1981), „Працтицал грапх исоморпхисм”, Цонгрессус Нумерантиум, 30: 45—87, 10тх. Манитоба Цонференце он Нумерицал Матхематицс анд Цомпутинг (Wиннипег, 1980) .
Миллер, Гарy (1980), „Исоморпхисм тестинг фор грапхс оф боундед генус”, Процеедингс оф тхе 12тх Аннуал АЦМ Сyмпосиум он Тхеорy оф Цомпутинг, стр. 225—235, ИСБН 978-0-89791-017-0, С2ЦИД 13647304, дои:10.1145/800141.804670 .
Сцхмидт, Доуглас C.; Друффел, Ларрy Е. (1976), „А Фаст Бацктрацкинг Алгоритхм то Тест Дирецтед Грапхс фор Исоморпхисм Усинг Дистанце Матрицес”, Ј. АЦМ, АЦМ, 23 (3): 433—445, ИССН 0004-5411, С2ЦИД 6163956, дои:10.1145/321958.321963 .
Спиелман, Даниел А. (1996). „Фастер исоморпхисм тестинг оф стронглy регулар грапхс”. СТОЦ '96: Процеедингс оф тхе тwентy-еигхтх аннуал АЦМ сyмпосиум он Тхеорy оф цомпутинг. АЦМ. стр. 576–584. ИСБН 978-0-89791-785-8. .
Уллман, Јулиан Р. (1976), „Ан алгоритхм фор субграпх исоморпхисм”, Јоурнал оф тхе АЦМ, 23: 31—42, С2ЦИД 17268751, дои:10.1145/321921.321925 .

Анкете и монографије

Реад, Роналд C.; Цорнеил, Дерек Г. (1977), „Тхе грапх исоморпхисм дисеасе”, Јоурнал оф Грапх Тхеорy, 1 (4): 339—363, МР 0485586, С2ЦИД 26589776, дои:10.1002/јгт.3190010410 ..
Гати, Г. "Фуртхер аннотатед библиограпхy он тхе исоморпхисм дисеасе." – Јоурнал оф Грапх Тхеорy 1979, 3, 95-109.
Землyацхенко, V. Н.; Корнеенко, Н. M.; Тyсхкевицх, Р. I. (1985), „Грапх исоморпхисм проблем”, Јоурнал оф Матхематицал Сциенцес, 29 (4): 1426—1481, С2ЦИД 121818465, дои:10.1007/БФ02104746 . (Транслатед фром Записки Науцхнyкх Семинаров Ленинградского Отделениyа Математицхеского Института им. V. А. Стеклова АН СССР (Рецордс оф Семинарс оф тхе Ленинград Департмент оф Стеклов Институте оф Матхематицс оф тхе УССР Ацадемy оф Сциенцес), Вол. 118. (1982). стр. 83–158.)
Арвинд, V.; Јацобо Торáн (2005), „Исоморпхисм Тестинг: Перспецтивес анд Опен Проблемс” (ПДФ), Буллетин оф тхе Еуропеан Ассоциатион фор Тхеоретицал Цомпутер Сциенце (86): 66—84, Архивирано из оригинала (ПДФ) 27. 07. 2011. г., Приступљено 26. 05. 2015 . (А бриеф сурвеy оф опен qуестионс релатед то тхе исоморпхисм проблем фор грапхс, рингс анд гроупс.)
Кöблер, Јоханнес; Сцхöнинг, Уwе; Јацобо Торáн (1993), Грапх Исоморпхисм Проблем: Тхе Струцтурал Цомплеxитy, Биркхäусер Верлаг, ИСБН 978-0-8176-3680-7, ОЦЛЦ 246882287 . (Фром тхе боок цовер: Тхе боокс фоцусес он тхе иссуе оф тхе цомпутатионал цомплеxитy оф тхе проблем анд пресентс северал рецент ресултс тхат провиде а беттер ундерстандинг оф тхе релативе поситион оф тхе проблем ин тхе цласс НП ас wелл ас ин отхер цомплеxитy цлассес.)
Јохнсон, Давид С. (2005), „Тхе НП-Цомплетенесс Цолумн”, АЦМ Трансацтионс он Алгоритхмс, 1 (1): 160—176, С2ЦИД 12604799, дои:10.1145/1077464.1077476 . (Тхис 24тх едитион оф тхе Цолумн дисцуссес тхе стате оф тхе арт фор тхе опен проблемс фром тхе боок Цомпутерс анд Интрацтабилитy анд превиоус цолумнс, ин партицулар, фор Грапх Исоморпхисм.)
Торáн, Јацобо; Фабиан Wагнер (2009), „Тхе Цомплеxитy оф Планар Грапх Исоморпхисм” (ПДФ), Буллетин оф тхе Еуропеан Ассоциатион фор Тхеоретицал Цомпутер Сциенце (97), Архивирано из оригинала (ПДФ) 20. 09. 2010. г., Приступљено 26. 05. 2015 .

Софтвер

Грапх Исоморпхисм, ревиеw оф имплементатионс, Тхе Стонy Броок Алгоритхм Репоситорy.

[1] Тхе латест оне ресолвед wас минимум-wеигхт триангулатион, провед то бе НП-цомплете ин 2006. Мулзер, Wолфганг; Роте, Гüнтер (2008), „Минимум-wеигхт триангулатион ис НП-хард”, Јоурнал оф тхе АЦМ, 55 (2): 1, С2ЦИД 1658062, арXив:цс.ЦГ/0601002  , дои:10.1145/1346330.1346336

[Johnson_2005-2] Јохнсон 2005

[3] Бабаи & Цоденотти 2008

[4] Уwе Сцхöнинг, "Грапх исоморпхисм ис ин тхе лоw хиерарцхy", Процеедингс оф тхе 4тх Аннуал Сyмпосиум он Тхеоретицал Аспецтс оф Цомпутер Сциенце, 1987, 114-124; алсо: Јоурнал оф Цомпутер анд Сyстем Сциенцес, вол. 37 (1988), 312-323

[5] МцКаy 1981

[6] Уллман 1976

[7] Цристопхер Мооре; Русселл, Алеxандер; Сцхулман, Леонард Ј. (2005). „Тхе Сyмметриц Гроуп Дефиес Стронг Фоуриер Самплинг: Парт И”. арXив:qуант-пх/0501056в3  [qуант-пх].

[8] Лáсзлó Бабаи, Wиллиам Кантор, Еугене Лукс, Цомпутатионал цомплеxитy анд тхе цлассифицатион оф фините симпле гроупс, Проц. 24тх ФОЦС (1983). стр. 162.–171.

[9] П. Фоггиа, C.Сансоне, M. Венто, А Перформанце Цомпарисон оф Фиве Алгоритхмс фор Грапх Исоморпхисм Архивирано на сајту Wayback Machine (24. септембар 2015), Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition. (2001). стр. 188–199.

[10] P.J. Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957). стр. 961.–968; Aho, Hopcroft & Ullman 1974

[11] Hopcroft & Wong 1974

[12] Datta, Samir; Limaye, Nutan; Nimbhorkar, Prajakta; Thierauf, Thomas; Wagner, Fabian (2009). „Planar Graph Isomorphism is in Log-Space”. 2009 24th Annual IEEE Conference on Computational Complexity. стр. 203—214. ISBN 978-0-7695-3717-7. doi:10.1109/CCC.2009.16.

[13] Booth & Lueker 1979

[14] Colbourn 1981

[15] Bodlaender 1990

[16] Miller 1980; Filotti & Mayer 1980

[17] Luks 1982

[18] Gary L. Miller: Isomorphism Testing and Canonical Forms for k-Contractable Graphs (A Generalization of Bounded Valence and Bounded Genus). Proc. Int. Conf. on Foundations of Computer Theory, (1983). стр. 310-327 (Lecture Notes in Computer Science, vol. 158, full paper in: Information and Control, 56(1-2):1–20, 1983.)

[19] Eugene Luks, "Parallel algorithms for permutation groups and graph isomorphism", Proc. IEEE Symp. Foundations of Computer Science. (1986). стр. 292–302.

[20] Booth & Colbourn 1977; Köbler, Schöning & Torán 1993

[21] Köbler, Schöning & Torán 1992; Arvind & Kurur 2006

[22] Arvind & Köbler 2000

[zkt-23] а ^б ^в ^г ^д ^ђ ^е ^ж ^з ^и ^ј ^к ^л ^љ ^м ^н ^њ ^о ^п ^р ^с ^т ^ћ Zemlyachenko, Korneenko & Tyshkevich 1985

[24] "On the hardness of finding symmetries in Markov decision processes", by SM Narayanamurthy, B Ravindran, Proceedings of the Twenty Fifth International Conference on Machine Learning (ICML 2008). стр. 688-696.

[chung1985cutwidth-25] Chung, Fan RK (1985). „On the cutwidth and the topological bandwidth of a tree”. SIAM Journal on Algebraic Discrete Methods. 6 (2): 268—277. doi:10.1137/0606026. Приступљено 13. 4. 2015.

[26] Colbourn M.J., Colbourn Ch.J. "Graph isomorphism and self-complementary graphs", SIGACT News, 1978, vol. 10, no. 1, 25-29.

[27] Kozen 1978

[28] J. Shawe-Taylor, T.Pisanski, "Homeomorphism of 2-Complexes is Graph Isomorphism Complete", SIAM Journal on Computing, 23 (1994) 120 - 132 .

[29] R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979). стр. 131—132; Johnson 2005

[30] Designing Programs that Check their Work

[31] Christophe-André Mario Irniger. Graph Matching: Filtering Databases of Graphs Using Machine Learning. 2005. ISBN 978-1-58603-557-0.

[32] Цоок, Диане Ј.; Холдер, Лаwренце Б. (2006). Мининг Грапх Дата. Јохн Wилеy & Сонс. стр. 120—122. ИСБН 978-0-470-07303-2.

[33] Баирд, ХС; Цхо, YЕ (1975). Ан артwорк десигн верифицатион сyстем. Процеедингс оф тхе 12тх Десигн Аутоматион Цонференце. ИЕЕЕ Пресс. стр. 414—420.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]