NP толық мәселелерінің тізімі - List of NP-complete problems
Бұл жиі кездесетін кейбір мәселелердің тізімі NP аяқталды ретінде көрсетілгенде шешім қабылдау проблемалары. Мұндай жүздеген проблемалар белгілі болғандықтан, бұл тізім ешқандай жолмен қамтылмаған. Осы типтегі көптеген мәселелерді табуға болады Гарей және Джонсон (1979).
Графиктер мен гиперографтар
Графиктер күнделікті қолданбаларда жиі кездеседі. Мысалдарға биологиялық немесе әлеуметтік желілерді жатқызуға болады, олар кейбір жағдайларда жүздеген, мыңдаған, тіпті миллиардтаған түйіндерді қамтиды (мысалы. Facebook немесе LinkedIn ).
- 1-жоспарлық[1]
- 3 өлшемді сәйкестік[2][3]
- Екі жақты өлшем[4]
- Сыйымдылығы ең аз ағаш[5]
- Маршрутты тексеру проблемасы (деп те аталады Қытай пошташылар мәселесі) үшін аралас графиктер (бағытталған және бағытталмаған шеттері бар). Бағдарлама полиномдық уақытта шешіледі, егер графикада барлық бағытталмаған немесе барлық бағытталған шеттер болса. Нұсқаларға ауылдық пошташы мәселесі кіреді.[6]
- Клик проблемасы[2][7]
- Толық бояу, акроматикалық сан[8]
- Доматикалық нөмір[9]
- Үстемдік жиынтығы, а.к.а. үстемдік саны[10]
- NP толық арнайы жағдайларға жатады жиек үстем жиынтығы мәселе, яғни сызықтық графиктердегі басым жиынтық мәселесі. NP толық нұсқаларына мыналар жатады қосылған домин жиынтығы проблема және жапырақтың максималды ағашы проблема.[11]
- Өткізу қабілеті проблемасы[12]
- Кликаның қақпағы ақаулы[2][13]
- Дәрежені бояу цикл дәрежесі
- Шектелген ағаш[14]
- Дәл мұқаба проблема. 3 жиынтыққа арналған NP толық болып қалады. 2 жиынтық үшін полиномдық уақытта шешілетін (бұл а сәйкестендіру ).[2][15]
- Кері байланыс шыңы орнатылды[2][16]
- Кері байланыс доғасы орнатылды[2][17]
- Графикалық гомоморфизм проблема[18]
- Графикті бояу[2][19]
- Графикалық бөлім ішіне ішкі графиктер нақты түрлерінің (үшбұрыштарының, изоморфты ішкі графиктер, Гамильтониан ішкі сызбалар, ормандар, тамаша сәйкестіктер ) белгілі NP-толық. Бөлу клиптер сияқты проблема болып табылады бояу The толықтыру берілген графиктің. Байланысты проблема - бұл бөліктер арасындағы жиектер санының оңтайлы бөлігін табу.[20]
- Гамильтондық аяқтау[21]
- Гамильтондық жол мәселесі, бағытталған және бағытталмаған.[2][22]
- Ең ұзын жол мәселесі[23]
- Максималды екі жақты субография немесе (әсіресе өлшенген шеттермен) максималды кесу.[2][24]
- Максималды тәуелсіз жиынтық[25]
- Максимум Индукциялық жол[26]
- Графиктің қиылысу нөмірі[27]
- Метрикалық өлшем график[28]
- Минималды k-кесу
- Штайнер ағашы, немесе Минималды созылатын ағаш графиктің шыңдары үшін.[2] (Толық графиктің ең аз таралатын ағашы көпмүшелік уақытта шешіледі).
- Модульдік максимизация[29]
- Түбі[30]
- Қақпақты орнатыңыз (деп те аталады ең төменгі қақпақ Мәселе) Бұл түсу матрицасын ұрып-соғатын жиынтық мәселесіне ауыстыру арқылы эквивалентті.[2][31]
- Бөлуді орнатыңыз проблема[32]
- Жолдың ең қысқа жалпы ұзындығы[33]
- Көлбеу нөмірі екі тестілеу[34]
- Түзу[30]
- Шыңның қақпағы[2][35]
Математикалық бағдарламалау
- 3-бөлім мәселесі[36]
- Қораптың ақаулығы[37]
- Рюкзак мәселесі, квадраттық рюкзак мәселесі, және бірнеше нұсқалары[2][38]
- Айырмашылықтар Сатушы мәселесі. Графиктер үшін проблема NP-ге тең, егер жиектердің ұзындықтары бүтін сандар болып саналса. Жазықтықтағы нүктелер үшін мәселе дискретті евклидтік метрикамен және түзу сызықты метрикамен толық NP болып табылады. Мәселе европлидтік метрикамен (дискретті емес) NP-қиын екені белгілі.[39]
- Бөтелкедегі саяхатшы[40]
- Бүтін программалау. Айнымалылар 0 немесе 1 болуы керек нұсқасы, нөлдік-сызықтық бағдарламалау деп аталады және басқа бірнеше нұсқалары да NP-аяқталған[2][41]
- Латын квадраттары (Ішінара толтырылған квадратты квадрат құру үшін аяқтауға болатындығын анықтау мәселесі)
- Сандық 3-өлшемді сәйкестендіру[42]
- Бөлім мәселесі[2][43]
- Квадраттық тағайындау есебі[44]
- Екі айнымалы квадрат көпмүшелерді бүтін сандар бойынша шешу.[45] Натурал сандар берілген , натурал сандарды табыңыз осындай
- Квадраттық бағдарламалау (Кейбір жағдайларда NP-қатты, егер дөңес болса)
- Ішкі жиынның проблемасы[46]
Ресми тілдер және жолдарды өңдеу
- Ең жақын жол[47]
- Төменгі проблема бірнеше ретпен[48]
- -Дың шектелген нұсқасы Хат алмасу мәселесі[49]
- Ең қысқа жалпы суперсеңсіздік[50]
- Жолдардан жолдарға түзету мәселесі[51]
Ойындар мен жұмбақтар
- Әскери кеме
- Бұқалар мен сиырлар ретінде сатылады Master Mind: белгілі бір оңтайландыру проблемалары, бірақ ойынның өзі емес.
- Мәңгілік II
- (Жалпыланған ) FreeCell[52]
- Филломино[53]
- Хашивокакеро[54]
- Сәлем[55]
- (Жалпыланған ) Лездік ақылсыздық[56]
- Какуро (кросс-қосындылар)
- Kingdomino[57]
- Куромасу (сонымен қатар Куродоко деп аталады)[58]
- LaserTank [59]
- Леммингтер (көпмүшелік уақыт шегі бар)[60]
- Жарық[61]
- Масю[62]
- Мина тазалағыш жүйесіндегі қиындық[63] (бірақ Скотт, Стедж және ван Ройхты қараңыз[64])
- Нимбер бағытталған графтың (немесе Grundy нөмірі).[65]
- Сандық сілтеме
- Нонограммалар
- Нурикабе
- (Жалпыланған ) Пандемия[66]
- Үшін оңтайлы шешім N×N×N Рубик кубы[67]
- SameGame
- (Жалпыланған ) Орнатыңыз[68]
- Slither сілтемесі әр түрлі торларда[69][70][71]
- (Жалпыланған ) Судоку[69][72]
- Қатысты мәселелер Тетрис[73]
- Ауызша арифметика
Басқа
- Айлақ бөлу мәселесі[74]
- Аралық
- Оңтайлы жинау Bitcoin блок.[75]
- Логикалық қанағаттанушылық проблемасы (SAT).[2][76] Көптеген вариациялар бар, олар да NP-аяқталған. Маңызды нұсқа - бұл әр сөйлемде үш әріптен тұратын (3SAT), өйткені ол көптеген басқа NP-нәтижелерін дәлелдеуде қолданылады.[77]
- Логикалық байланыстырушы сұрау[78]
- Циклдік тапсырыс
- Схеманың қанағаттанушылығы проблемасы
- Сыйымдылығы жеткіліксіз ғимараттың орналасу проблемасы
- Дүкендерді жоспарлау мәселесі
- Жалпы тағайындау мәселесі
- Жоғары жоспарлау тестілеу[34]
- Ауруханалар мен тұрғындар ерлі-зайыптылармен проблема
- Қатысты кейбір мәселелер Дүкендерді жоспарлау
- Монохроматикалық үшбұрыш[79]
- Минималды максималды тәуелсіз жиынтық минималды тәуелсіз үстемдік жиынтығы[80]
- NP толық арнайы жағдайларға жатады минималды максималды сәйкестік проблема,[81] ол мәні бойынша тең жиек үстем жиынтығы проблема (жоғарыдан қараңыз).
- Максималды кең таралған субографиялық изоморфизм мәселесі[82]
- Ағаштың минималды дәрежесі
- К-таралатын минималды ағаш
- Метрикалық k-орталық
- Максимум 2-қанықтылық[83]
- Модальды логика S5-қанықтылық
- Қатысты кейбір мәселелер Мультипроцессорлық жоспарлау
- Максималды дыбыс деңгейі субматрица - m x n матрицасының ең жақсы шартталған ішкі жиынын таңдау мәселесі. Бұл проблемалар класы Rank айқындаумен байланысты QR факторизациясы және D оңтайлы эксперименттік дизайн.[84]
- Минималды қосу тізбектері реттілік үшін.[85] Жеке сандар үшін минималды қосу тізбектерінің күрделілігі белгісіз.[86]
- GF бойынша сызықтық емес бір айнымалы көпмүшелер [2n], кірістің ұзындығы n. Шынында да, кез-келген GF [qn].
- Ашық дүкен кестесі
- Түбі,[30] немесе баламалы түрде, аралық қалыңдығы, және шыңды бөлу нөмірі[87]
- Құймақты сұрыптау жолдар үшін қашықтық проблемасы[88]
- k-қытайлық пошташы
- Субографиялық изоморфизм мәселесі[89]
- Вариациялары Штайнер ағашының проблемасы. Дәлірек айтқанда, дискреттелген эвклидтік метрикамен, түзу сызықты метрикамен. Мәселе европлидтік метрикамен (дискретті емес) NP-қиын екені белгілі.[90]
- Қаптаманы орнатыңыз[2][91]
- Тізбектілік мәліметтер қорының тарихы[92]
- Салмақталған аяқталу уақытын азайту үшін жоспарлау
- Сирек жуықтау
- Сұрыптауды блоктау[93] (Блокты жылжыту бойынша сұрыптау)
- Екінші тәртіп сәттілік
- Түзу[30]
- A немесе жоқ екендігін тексеру ағаш ретінде ұсынылуы мүмкін Евклидтік минималды ағаш
- Үшөлшемді Үлгілеу[94]
- Көлік маршрутының ақаулығы
Сондай-ақ қараңыз
- Шындықтардың экзистенциалдық теориясы # Барлық есептер
- Карптың 21 NP толық есептері
- PSPACE аяқталған мәселелер тізімі
- Қысқарту (күрделілік)
Ескертулер
- ^ Григорьев және Бодлаендер (2007).
- ^ а б в г. e f ж сағ мен j к л м n o б q Карп (1972)
- ^ Гарей және Джонсон (1979): SP1
- ^ Гарей және Джонсон (1979): GT18
- ^ Гарей және Джонсон (1979): ND5
- ^ Гарей және Джонсон (1979): ND25, ND27
- ^ Гарей және Джонсон (1979): GT19
- ^ Гарей және Джонсон (1979): GT5
- ^ Гарей және Джонсон (1979): GT3
- ^ Гарей және Джонсон (1979): GT2
- ^ Гарей және Джонсон (1979): ND2
- ^ Гарей және Джонсон (1979): GT40
- ^ Гарей және Джонсон (1979): GT17
- ^ Гарей және Джонсон (1979): ND1
- ^ Гарей және Джонсон (1979): SP2
- ^ Гарей және Джонсон (1979): GT7
- ^ Гарей және Джонсон (1979): GT8
- ^ Гарей және Джонсон (1979): GT52
- ^ Гарей және Джонсон (1979): GT4
- ^ Гарей және Джонсон (1979): GT11, GT12, GT13, GT14, GT15, GT16, ND14
- ^ Гарей және Джонсон (1979): GT34
- ^ Гарей және Джонсон (1979): GT37, GT38, GT39
- ^ Гарей және Джонсон (1979): ND29
- ^ Гарей және Джонсон (1979): GT25, ND16
- ^ Гарей және Джонсон (1979): GT20
- ^ Гарей және Джонсон (1979): GT23
- ^ Гарей және Джонсон (1979): GT59
- ^ Гарей және Джонсон (1979): GT61
- ^ Брендс, Улрик; Делинг, Даниэль; Гертлер, Марко; Герке, Роберт; Хофер, Мартин; Николоски, Зоран; Вагнер, Доротея (2006), Модульділікті арттыру өте қиын, arXiv:физика / 0608255, Бибкод:2006 физика ... 8255B
- ^ а б в г. Арнборг, Корнейл және Проскуровски (1987)
- ^ Гарей және Джонсон (1979): SP5, SP8
- ^ Гарей және Джонсон (1979): SP4
- ^ Гарей және Джонсон (1979): ND3
- ^ а б Гарг, Ашим; Тамассия, Роберто (1995). «Жоғары және түзу сызықтық жазықтықты сынаудың есептеу қиындығы туралы». Информатика пәнінен дәрістер. 894/1995. 286–297 беттер. дои:10.1007/3-540-58950-3_384. ISBN 978-3-540-58950-1.
- ^ Гарей және Джонсон (1979): GT1
- ^ Гарей және Джонсон (1979): SP15
- ^ Гарей және Джонсон (1979): SR1
- ^ Гарей және Джонсон (1979): MP9
- ^ Гарей және Джонсон (1979): ND22, ND23
- ^ Гарей және Джонсон (1979): ND24
- ^ Гарей және Джонсон (1979): MP1
- ^ Гарей және Джонсон (1979): SP16
- ^ Гарей және Джонсон (1979): SP12
- ^ Гарей және Джонсон (1979): ND43
- ^ Квадраттық көпмүшеліктер үшін NP толық шешім есептері
- ^ Гарей және Джонсон (1979): SP13
- ^ Ланкот, Дж.Кевин; Ли, Мин; Ma, Bin; Ван, Шаоцзюй; Чжан, Луксин (2003), «Жолдарды таңдау мәселелерін ажырату», Ақпарат және есептеу, 185 (1): 41–55, дои:10.1016 / S0890-5401 (03) 00057-9, МЫРЗА 1994748
- ^ Гарей және Джонсон (1979): SR10
- ^ Гарей және Джонсон (1979): SR11
- ^ Гарей және Джонсон (1979): SR8
- ^ Гарей және Джонсон (1979): SR20
- ^ Malte Helmert, Жоспарлау кезінде стандартты эталондар үшін күрделіліктің нәтижелері, Жасанды Интеллект 143 (2): 219-262, 2003 ж.
- ^ Ято, Такауки (2003). Басқа шешім іздеудің күрделілігі мен толықтығы және оны жұмбақтарға қолдану. CiteSeerX 10.1.1.103.8380.
- ^ «HASHIWOKAKERO NP-Complete».
- ^ Holzer & Ruepp (2007)
- ^ Гарей және Джонсон (1979): GP15
- ^ Нгуен, Вьет-Ха; Перро, Кевин; Валлет, Матье (24 маусым 2020). «KingdominoTM ойынының NP-толықтығы». Теориялық информатика. 822: 23–35. дои:10.1016 / j.tcs.2020.04.007. ISSN 0304-3975.
- ^ Kölker, Jonas (2012). «Куродоко NP аяқталды» (PDF). Ақпаратты өңдеу журналы. 20 (3): 694–706. дои:10.2197 / ipsjjip.20.694. S2CID 46486962.
- ^ Александрссон, Пер; Рестадх, Питер (2020). «LaserTank - NP-Complete». Компьютерлік және ақпараттық ғылымдардың математикалық аспектілері. Информатика пәнінен дәрістер. Springer International Publishing. 11989: 333–338. arXiv:1908.05966. дои:10.1007/978-3-030-43120-4_26. ISBN 978-3-030-43119-8. S2CID 201058355.
- ^ Cormode, Graham (2004). Леммингтер ойынының қаттылығы немесе жоқ, жоқ NP-толықтығының дәлелі (PDF).
- ^ Light Up - NP-Complete
- ^ Фридман, Эрих (2012 ж. 27 наурыз). «Інжу-басқатырғыштар NP-мен аяқталды».
- ^ Кайе (2000)
- ^ Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper NP толық болмауы мүмкін, бірақ соған қарамастан қиын Математикалық интеллект 33: 4 (2011), 5-17 бет.
- ^ Гарей және Джонсон (1979): GT56
- ^ Накай, Кеничиро; Такенага, Ясухико (2012). «Пандемияның NP-толықтығы». Ақпаратты өңдеу журналы. 20 (3): 723–726. дои:10.2197 / ipsjjip.20.723. ISSN 1882-6652.
- ^ Демейн, Эрик; Эйзенстат, Сара; Рудой, Михаил (2018). Рубик кубын оңтайлы шешу NP аяқталды. Информатиканың теориялық аспектілері бойынша 35-ші симпозиум (STACS 2018). дои:10.4230 / LIPIcs.STACS.2018.24.
- ^ http://pbg.cs.illinois.edu/papers/set.pdf
- ^ а б Сато, Такаюки; Сета, Такахиро (1987). Басқа шешім іздеудің күрделілігі мен толықтығы және оны жұмбақтарға қолдану (PDF). Халықаралық алгоритмдер симпозиумы (SIGAL 1987).
- ^ Нукуй; Уеджима (наурыз 2007). «Бірнеше тордағы слайдтық сілтеме басқатырғышының ASP-толықтығы». Ipsj Sig Notes. 2007 (23): 129–136.
- ^ Kölker, Jonas (2012). «Таңдалған слайдтық сілтеме нұсқалары толық емес». Ақпаратты өңдеу журналы. 20 (3): 709–712. дои:10.2197 / ipsjjip.20.709.
- ^ NP-COMPLETE жұмбақтарын зерттеу, 23 бөлім; Грэм Кендалл, Эндрю Паркес, Кристиан Сперер; Наурыз 2008 ж. (icga2008.pdf)
- ^ Демейн, Эрик Д .; Хохенбергер, Сюзан; Либен-Новелл, Дэвид (2003 ж. 25-28 шілде). Тетрис шамамен, тіпті қиын (PDF). 9-шы Халықаралық есептеу және комбинаторика конференциясының материалдары (COCOON 2003). Үлкен аспан, Монтана.
- ^ Лим, Эндрю (1998), «Айлақты жоспарлау мәселесі», Операцияларды зерттеу хаттары, 22 (2–3): 105–110, дои:10.1016 / S0167-6377 (98) 00010-8, МЫРЗА 1653377
- ^ Дж.Бонно, «Биткоинді өндіру NP-қиын
- ^ Гарей және Джонсон (1979): LO1
- ^ Гарей және Джонсон (1979): б. 48
- ^ Гарей және Джонсон (1979): SR31
- ^ Гарей және Джонсон (1979): GT6
- ^ Минималды тәуелсіз домин жиынтығы
- ^ Гарей және Джонсон (1979): GT10
- ^ Гарей және Джонсон (1979): GT49
- ^ Гарей және Джонсон (1979): LO5
- ^ https://web.archive.org/web/20150203193923/http://www.meliksah.edu.tr/acivril/max-vol-original.pdf
- ^ Питер Дауни, Бентон Леонг және Рави Сети. «Қосымша тізбектермен есептеулер тізбегі» SIAM Дж. Комп., 10 (3), 638-646, 1981
- ^ Д. Дж.Бернштейн, «Пиппергердің дәрежелеу алгоритмі (жоба)
- ^ Кашивабара және Фуджисава (1979); Охцуки және басқалар. (1979); Ленгауэр (1981).
- ^ Хюркенс, С .; Иерсель, Л.В .; Кейжспер, Дж .; Келк, С .; Стюджи, Л .; Тромп, Дж. (2007). «Екілік және үштік жолдардағы префиксті қалпына келтіру». SIAM J. Дискретті математика. 21 (3): 592–611. arXiv:математика / 0602456. дои:10.1137/060664252.
- ^ Гарей және Джонсон (1979): GT48
- ^ Гарей және Джонсон (1979): ND13
- ^ Гарей және Джонсон (1979): SP3
- ^ Гарей және Джонсон (1979): SR33
- ^ Бейн, В.В .; Лармор, Л. Латифи, С .; Sudborough, I. H. (1 қаңтар 2002). Блокты сұрыптау қиын. Параллель сәулет, алгоритмдер және желілер бойынша халықаралық симпозиум, 2002. I-SPAN '02. Іс жүргізу. 307-312 бет. дои:10.1109 / ISPAN.2002.1004305. ISBN 978-0-7695-1579-3. S2CID 32222403.
- ^ Барри Артур Ципра, «The Ising Model is NP-Complete», SIAM News, 33 том, No 6.
Пайдаланылған әдебиеттер
Жалпы
- Гари, Майкл Р.; Джонсон, Дэвид С. (1979), Компьютерлер және қиындықтар: NP-толықтығы теориясының нұсқаулығы, Фриман В., ISBN 0-7167-1045-5. Бұл кітап классик, теорияны дамытады, содан кейін каталогтайды көп NP-толық мәселелер.
- Кук, С.А. (1971). «Теореманың дәлелдеу процедураларының күрделілігі». Жинақ, есеп айырысу теориясының жыл сайынғы ACM симпозиумы, ACM, Нью-Йорк. 151–158 бет. дои:10.1145/800157.805047.
- Карп, Ричард М. (1972). «Комбинаторлық мәселелер арасындағы қысқарту». Миллерде Реймонд Э .; Тэтчер, Джеймс В. (ред.) Компьютерлік есептеулердің күрделілігі. Пленум. 85–103 бб.CS1 maint: ref = harv (сілтеме)
- Данн, П.Е. «Таңдалған NP толық мәселелерінің аннотацияланған тізімі». COMP202, информатика кафедрасы, Ливерпуль университеті. Алынған 21 маусым 2008.
- Крешенци, П .; Канн, V .; Халлдорсон, М .; Карпинский, М.; Сұмдық, Г.. «NP оңтайландыру мәселелері бойынша жинақ». KTH NADA, Стокгольм. Алынған 21 маусым 2008.
- Далке, К. «NP-толық мәселелер». Математикалық анықтама жобасы. Алынған 21 маусым 2008.
Нақты мәселелер
- Фридман, Е (2002). «Інжу-басқатырғыштар NP-мен аяқталды». Стетсон университеті, Деланд, Флорида. Алынған 21 маусым 2008.
- Григорьев, А; Bodlaender, H L (2007). «Бір шеті аз қиылысқан енгізілетін графиктердің алгоритмдері». Алгоритмика. 49 (1): 1–11. CiteSeerX 10.1.1.61.3576. дои:10.1007 / s00453-007-0010-x. МЫРЗА 2344391. S2CID 8174422.CS1 maint: ref = harv (сілтеме)
- Хартунг, С; Nichterlein, A (2012). Әлем қалай есептейді. Информатика пәнінен дәрістер. 7318. Шпрингер, Берлин, Гейдельберг. 283–292 беттер. CiteSeerX 10.1.1.377.2077. дои:10.1007/978-3-642-30870-3_29. ISBN 978-3-642-30869-7. S2CID 6112925.
- Хольцер, Маркус; Руепп, Оливер (2007). «Интерьер дизайнының қиындықтары - ойынның күрделілігін талдау» (PDF). Алгоритмдермен көңіл көтеру бойынша 4-ші халықаралық конференция, LNCS 4475. Шпрингер, Берлин / Гейдельберг. 198–212 бет. дои:10.1007/978-3-540-72914-3_18. ISBN 978-3-540-72913-6.CS1 maint: ref = harv (сілтеме)
- Кайе, Ричард (2000). «Minesweeper NP-аяқталған». Математикалық интеллект. 22 (2): 9–15. дои:10.1007 / BF03025367. S2CID 122435790.CS1 maint: ref = harv (сілтеме) Қосымша ақпарат онлайн режимінде қол жетімді Ричард Кайенің Minesweeper парақтары.
- Кашивабара, Т .; Фуджисава, Т. (1979). «Берілген графиканы ішкі график түрінде қамтитын минималды-кликтік-сандық интервалды графикті табу есебінің толықтығы». Іс жүргізу. Схемалар мен жүйелер бойынша халықаралық симпозиум. 657-660 бет.CS1 maint: ref = harv (сілтеме)
- Охцуки, Тацуо; Мори, Хаджиму; Кух, Эрнест С .; Кашивабара, Тошинобу; Фуджисава, Тосио (1979). «Бір өлшемді логикалық қақпаны тағайындау және интервалдық графиктер». IEEE тізбектер мен жүйелердегі транзакциялар. 26 (9): 675–684. дои:10.1109 / TCS.1979.1084695.CS1 maint: ref = harv (сілтеме)
- Ленгауэр, Томас (1981). «Қара-ақ тастар мен графиканы бөлу». Acta Informatica. 16 (4): 465–475. дои:10.1007 / BF00264496. S2CID 19415148.CS1 maint: ref = harv (сілтеме)
- Арнборг, Стефан; Корнейл, Дерек Г.; Проскуровский, Анджей (1987). «Кірістірулерді іздеудің күрделілігі к-ағаш ». SIAM журналы алгебралық және дискретті әдістер туралы. 8 (2): 277–284. дои:10.1137/0608024.CS1 maint: ref = harv (сілтеме)
- Cormode, Graham (2004). «Леммингтер ойынының қаттылығы немесе жоқ, жоқ NP-толықтығының дәлелі». Алгоритмдермен көңіл көтеруге арналған үшінші халықаралық конференция материалдары (FUN 2004). 65-76 бет.