Тегіс сызба - Even-hole-free graph

Ішінде математикалық ауданы графтар теориясы, график тегіс тесіксіз егер ол жоқ болса индукцияланған цикл жұп санымен төбелер.

Аддарио-Берри және басқалар. (2008) саңылаусыз әр графикте а болатындығын көрсетті бисимпликиалды шың, бұл Ридтің жорамалын шешті.

Тану

Конфорти және басқалар. (2002б) ішіне кіретін, сызықсыз графиктердің алғашқы полиномдық уақытты тану алгоритмін берді ${displaystyle {mathcal {O}} (n ^ {40})}$ уақыт.^[1]да Силва және Вушкович (2008) кейінірек оны жақсартты ${displaystyle {mathcal {O}} (n ^ {19})}$ .Чанг және Лу (2012) және Chang & Lu (2015) мұны жақсартты ${displaystyle {mathcal {O}} (n ^ {11})}$ уақыт.Ең жақсы танымал алгоритм берілген Лай, Лу және Торуп (2020) кіреді ${displaystyle {mathcal {O}} (n ^ {9})}$ уақыт.

Тесіксіз графиктерді көпмүшелік уақытта тануға болатынымен, ол NP-графикте белгілі бір шыңды қамтитын жұп тесік бар-жоғын анықтау үшін аяқтаңыз.^[2]

Бұл белгісіз графикалық бояу және максималды тәуелсіз жиынтық мәселені полиномды уақытта жұп саңылаусыз графиктер бойынша шешуге болады, немесе олар NP-ге толы ма. максималды клик көпмүшелік уақыттағы саңылаусыз графиктерден табуға болады.^[3]

Ескертулер

^ Конфорти және басқалар. (2002б) олардың алгоритмін ұсыныңыз және оның нақты талдаусыз полиномдық уақытта жұмыс істейтінін растаңыз. Чудновский, Каварабааши және Сеймур (2004) шамамен «уақыт ішінде» жұмыс істейтінін бағалаңыз ${displaystyle {mathcal {O}} (n ^ {40})}$ ."
^ Биенсток (1991)
^ Вушкович (2010).

Әдебиеттер тізімі

Аддарио-Берри, Луиджи; Чудновский, Мария; Хавт, Фредерик; Рид, Брюс; Сеймур, Пол (2008), «Тесіксіз графиктердегі бисимплипиалды шыңдар», Комбинаторлық теория журналы, В сериясы, 98 (6): 1119–1164, дои:10.1016 / j.jctb.2007.12.006
Биенсток, Дэн (1991), «Тақ саңылаулар мен индукцияланған тақ жолдарды сынаудың күрделілігі туралы», Дискретті математика, 90 (1): 85–92, дои:10.1016 / 0012-365X (91) 90098-M
Чудновский, Мария; Каварабаяши, Кен-ичи; Сеймур, Пол (2004), «Жұп тесіктерді анықтау», Графикалық теория журналы, 48 (2): 85–111, дои:10.1002 / jgt.20040
Конфорти, Мишель; Корнуэхолс, Жерар; Капур, Ажай; Вушкович, Кристина (2002 ж. Қаңтар), «Тесіксіз графиктер I бөлім: ыдырау теоремасы» (PDF), Графикалық теория журналы, 39 (1): 6–49, дои:10.1002 / jgt.10006
Конфорти, Мишель; Корнуэхолс, Жерар; Капур, Ажай; Вушкович, Кристина (2002 ж. Тамыз), «Тесіксіз графиктер II бөлім: тану алгоритмі» (PDF), Графикалық теория журналы, 40 (4): 238–266, дои:10.1002 / jgt.10045
да Силва, Мурило В.Г .; Вушкович, Кристина (2008), Жұлдызшалар мен 2 қосылыстары бар біркелкі саңылаусыз графиктердің ыдырауы
Чан, Сян-Чих; Лу, Хсуех-I (қаңтар 2012), «Тесіксіз графиканы танудың жылдамырақ алгоритмі», SODA '12: Дискретті алгоритмдер бойынша жиырма үшінші ACM-SIAM симпозиумының материалдары.: 1286–1297
Чан, Сян-Чих; Лу, Хсуэ-I (шілде 2015 ж.), «Тесіксіз графиканы танудың жылдамырақ алгоритмі», Комбинаторлық теория журналы, В сериясы, 113: 141–161, arXiv:1311.0358, дои:10.1016 / j.jctb.2015.02.001, S2CID 1744497
Вушкович, Кристина (2010), «Тесіксіз графиктер: сауалнама» (PDF), Қолданылатын талдау және дискретті математика, 4 (2): 219–240, дои:10.2298 / AADM100812027V, JSTOR 43666110, МЫРЗА 2724633
Лай, Кай-Юань; Лу, Хсуех-I; Торуп, Миккель (маусым, 2020 ж.), «Жақындағы сызықтық уақытта үш түп ағаш», STOC 2020: 52-жылдық ACM SIGACT есептеу теориясы симпозиумының материалдары.: 1279–1292, arXiv:1909.07446, дои:10.1145/3357713.3384235 (белсенді емес 2020-09-29)CS1 maint: DOI 2020 жылдың қыркүйегіндегі жағдай бойынша белсенді емес (сілтеме)

Сыртқы сілтемелер

«Тесіксіз графиктер», Графикалық кластар және олардың қосындылары туралы ақпараттық жүйе

[1] Конфорти және басқалар. (2002б) олардың алгоритмін ұсыныңыз және оның нақты талдаусыз полиномдық уақытта жұмыс істейтінін растаңыз. Чудновский, Каварабааши және Сеймур (2004) шамамен «уақыт ішінде» жұмыс істейтінін бағалаңыз ${displaystyle {mathcal {O}} (n ^ {40})}$ ."

[2] Биенсток (1991)

[FOOTNOTEVušković2010-3] Вушкович (2010).

[1]

[2]

[3]