Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В математической области теории графов граф считается без четных отверстий, если он не содержит индуцированного цикла с четным числом вершин .

Аддарио-Берри и др. (2008) продемонстрировали, что каждый граф без четных дырок содержит бисимплициальную вершину , что разрешило гипотезу Рида.

Признание [ править ]

Conforti et al. (2002b) дал первый алгоритм распознавания за полиномиальное время для графов без четных отверстий, который работает во времени. [1] da Silva и Vušković (2008) позже улучшили это до .Chang & Lu (2012) и Chang & Lu (2015) улучшили это время. Самый известный в настоящее время алгоритм представлен Lai, Lu & Thorup (2020), который работает во времени.

Хотя графы без четных отверстий могут быть распознаны за полиномиальное время, NP- полнота определения того, содержит ли граф четное отверстие, которое включает определенную вершину. [2]

Неизвестно, могут ли раскраска графа и задача о максимальном независимом множестве быть решены за полиномиальное время на графах без четных дырок, или они являются NP-полными. Однако максимальную клику можно найти в графах без четных дырок за полиномиальное время. [3]

Заметки [ править ]

  1. ^ Конфорти и др. (2002b) представляют свой алгоритм и утверждают, что он работает за полиномиальное время, не давая явного анализа. По оценкам Чудновского, Каварабаяши и Сеймура (2004) , он движется «во времени».
  2. ^ Bienstock (1991)
  3. ^ Вушкович (2010) .

Ссылки [ править ]

  • Аддарио-Берри, Луиджи; Чудновский, Мария ; Хаве, Фредерик; Рид, Брюс ; Сеймур, Пол (2008), «Бисимплициальные вершины в графах без четных дырок», Журнал комбинаторной теории, серия B , 98 (6): 1119–1164, DOI : 10.1016 / j.jctb.2007.12.006
  • Бинсток, Дэн (1991), «О сложности тестирования нечетных отверстий и индуцированных нечетных путей», Дискретная математика , 90 (1): 85–92, DOI : 10.1016 / 0012-365X (91) 90098-M
  • Чудновский, Мария ; Каварабаяси, Кен-ичи ; Seymour, Paul (2004), "Обнаружение даже дыры", Журнал теории графов , 48 (2): 85-111, DOI : 10.1002 / jgt.20040
  • Конфорти, Микеле; Корнежоль, Жерар ; Капур, Аджай; Vušković, Кристина (январь 2002a), "Даже лунки свободных графиков часть I: теорема разложения" (PDF) , Журнал теории графов , 39 (1): 6-49, DOI : 10.1002 / jgt.10006
  • Конфорти, Микеле; Корнежоль, Жерар ; Капур, Аджай; Vušković, Кристина (август 2002b), "Даже лунками свободных графиков часть II: алгоритм распознавания" (PDF) , Журнал теории графов , 40 (4): 238-266, DOI : 10.1002 / jgt.10045
  • да Силва, Мурило В.Г.; Вушкович, Кристина (2008), Разложение графов без четных отверстий с помощью звездных сечений и 2-соединений
  • Чанг, Сянь-Чжи; Лу, Сюэ-I (январь 2012 г.), «Более быстрый алгоритм распознавания графиков без четных отверстий» , SODA '12: Материалы двадцать третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам : 1286–1297, doi : 10,1137 /1.9781611973099.101 , ISBN 978-1-61197-210-8
  • Чанг, Сянь-Чжи; Лу, Сюэ-I (июль 2015 г.), «Более быстрый алгоритм распознавания графов без четных отверстий», Журнал комбинаторной теории, серия B , 113 : 141–161, arXiv : 1311.0358 , doi : 10.1016 / j.jctb. 2015.02.001 , S2CID  1744497
  • Vušković, Кристина (2010), "Even-неповрежденные графики: обзор" (PDF) , Применимый анализ и дискретная математика , 4 (2): 219-240, DOI : 10,2298 / AADM100812027V , JSTOR  43666110 , MR  2724633
  • Лай, Кай-Юань; Лу, Сюэ-И; Торуп, Миккель (июнь 2020 г.), «Три в дереве в почти линейное время», STOC 2020: Материалы 52-го ежегодного симпозиума ACM SIGACT по теории вычислений : 1279–1292, arXiv : 1909.07446 , doi : 10.1145 / 3357713.3384235 (неактивный 2021-01-11)CS1 maint: DOI неактивен с января 2021 г. ( ссылка )

Внешние ссылки [ править ]

  • «Графы без четных дырок» , Информационная система по классам графов и их включениям