Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Дерево (вверху) и соответствующая ему трехлепестковая сила (внизу)

В математической области теории графов степень k- листа дерева - это граф , вершины которого являются листьями, а ребра соединяют пары листьев, расстояние в которых не больше . То есть, это подграф из мощности графа , индуцированный листьев . Для графа, построенного таким образом, называется k -листным корнем из .

Граф - это листовая степень, если для некоторых он является -листовой степенью . [1] Эти графы имеют приложения в филогении , проблеме восстановления эволюционных деревьев.

Связанные классы графиков [ править ]

Поскольку степени сильно хордовых графов являются сильно хордовыми, а деревья - сильно хордовыми, отсюда следует, что листовые степени являются сильно хордовыми графами. [2] Фактически, листовые степени образуют собственный подкласс сильно хордовых графов; граф является листовой степенью тогда и только тогда, когда он является графом NeST с фиксированным допуском [3] и такие графы являются собственным подклассом сильно хордовых графов. [4]

В Brandstädt et al. (2010) показано, что интервальные графы и более широкий класс корневых ориентированных графов путей являются листовыми степенями. На графиках безразличия точно пластинчатые силы, базовых дерева гусеницы дерев .

В K -leaf силы для ограниченных значений к имеют ограниченную кликовым ширину , но это не так пластинчатых полномочий с неограниченными показателями. [5]

Структура и узнаваемость [ править ]

Нерешенная проблема в информатике :

Есть ли алгоритм с полиномиальным временем для распознавания листовых или -листовых степеней для ?

(больше нерешенных проблем в информатике)

Граф является степенью 2-листа , если и только если оно является объединением непересекающегося из клик (т.е. кластера график ). [1]

Граф является трехлистной степенью тогда и только тогда, когда он является хордальным графом без (быков, дротиков, драгоценных камней) . [6] Основываясь на этой и подобных характеристиках, 3-листовые мощности могут быть распознаны за линейное время . [7]

Характеристики четырехлистных степеней даны Раутенбахом (2006) и Brandstädt, Le & Sritharan (2008) , которые также позволяют распознавать линейное время. Распознавание 5-листового и 6-листового графов мощности также решается за линейное время Чангом и Ко (2007) [8] и Ducoffe (2018), [9] соответственно.

Для ≥ 7 проблема распознавания -листовых степеней открыта, равно как и открытая проблема, можно ли распознать листовые степени за полиномиальное время . Однако было доказано, что распознавание степеней -листов является управляемым с фиксированным параметром, если параметризовано с помощью и вырожденностью входного графа. [10]

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

  1. ^ a b Nishimura, Ragde & Thilikos (2002) .
  2. ^ Dahlhaus & Duchet (1987) ; Любив (1987) ; Райчаудхури (1992) .
  3. ^ Brandstädt et al. (2010) ; Хейворд, Кирни и Малтон (2002) .
  4. ^ Broin & Lowe (1986) ; Bibelnieks & Dearing (1993) .
  5. ^ Brandstädt & Hundt (2008) ; Гурски и Ванке (2009) .
  6. ^ Dom et al. (2006) ; Раутенбах (2006)
  7. ^ Brandstädt & Le (2006) .
  8. ^ Ко, Мин-Тат; Чанг, Мо-Шан (21.06.2007). Проблема 3-Штейнера . Теоретико-графические концепции в компьютерных науках . Конспект лекций по информатике. Шпрингер, Берлин, Гейдельберг. С. 109–120. DOI : 10.1007 / 978-3-540-74839-7_11 . ISBN 9783540748380.
  9. ^ Ducoffe, Гийом (2018-10-04). "Распознавание 4-степеней Штейнера за полиномиальное время". arXiv : 1810.02304 [ cs.CC ].
  10. ^ Эппштейн, Дэвид; Хаввеи, Эльхам (01.08.2020). «Распознавание параметризованной силы листьев посредством встраивания в графические продукты» . Алгоритмика . 82 (8): 2337–2359. DOI : 10.1007 / s00453-020-00720-8 . ISSN 1432-0541 . S2CID 218988055 .  

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

  • Bibelnieks, E .; Даринг, PM (1993), "Графики допусков соседних поддеревьев", Дискретная прикладная математика , 43 : 13–26, DOI : 10.1016 / 0166-218X (93) 90165-K.
  • Брандштадт, Андреас; Хундт, Кристиан (2008), «Птолемеевы графы и интервальные графы - это листовые полномочия», LATIN 2008: Теоретическая информатика , Конспекты лекций в Comput. Sci . , 4957 ., Springer, Berlin, С. 479-491, DOI : 10.1007 / 978-3-540-78773-0_42 , ISBN 978-3-540-78772-3, Руководство по ремонту  2472761.
  • Брандштадт, Андреас ; Хундт, Кристиан; Манчини, Федерико; Вагнер, Питер (2010), "Корневые ориентированные графы пути являются листовые силы", Дискретная математика , 310 (4): 897-910, DOI : 10.1016 / j.disc.2009.10.006.
  • Брандштадт, Андреас ; Ле, Ван Банг (2006), "Распознавание структуры и линейного времени трехлистных степеней", Письма об обработке информации , 98 (4): 133–138, CiteSeerX  10.1.1.144.3486 , doi : 10.1016 / j.ipl.2006.01 0,004.
  • Брандштадт, Андреас ; Ле, Ван Банг; Sritharan, R. (2008), "Структура и линейное распознавание времени 4-створчатые полномочий", ACM Сделки по алгоритмам , 5 : 1-22, DOI : 10,1145 / 1435375,1435386 , S2CID  6114466.
  • Брандштадт, Андреас ; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор , Монографии SIAM по дискретной математике и приложениям, ISBN 978-0-89871-432-6.
  • Броин, МВт; Лоу, Т.Дж. (1986), "Графы допуска соседних поддеревьев", SIAM J. Algebr. Дискретные методы , 7 : 348-357, DOI : 10,1137 / 0607039.
  • Dahlhaus, E .; Duchet, P. (1987), "О сильно хордовых графах", Ars Combinatoria , 24 B : 23–30.
  • Dahlhaus, E .; Мануэль, PD; Миллер, М. (1998), "Характеризация сильно хордальных графы", дискретная математика , 187 (1-3): 269-271, DOI : 10.1016 / S0012-365X (97) 00268-9.
  • Дом, М .; Guo, J .; Hüffner, F .; Нидермайер, R. (2006), "компенсация ошибки в лист корня проблемы", Algorithmica , 44 (4): 363-381, CiteSeerX  10.1.1.218.490 , DOI : 10.1007 / s00453-005-1180-г , S2CID  75279.
  • Фарбер, М. (1983), "Характеризация сильно хордальных графы", дискретная математика , 43 (2-3): 173-189, DOI : 10.1016 / 0012-365X (83) 90154-1.
  • Гурски, Франк; Ванка, Эгон (2009), "НКА-ширина и клика ширина для степеней графов ограниченной древовидной ширины", Дискретная прикладная математика , 157 (4): 583-595, DOI : 10.1016 / j.dam.2008.08. 031 , Руководство MR  2499471.
  • Хейворд, РБ; Кирни, ЧП; Мальтон, A. (2002), "вкладывание графа", дискретная прикладная математика , 121 (1-3): 139-153, DOI : 10.1016 / s0166-218x (01) 00207-4.
  • Lubiw, А. (1987), "двукратно лексические упорядоченности матриц", SIAM журнал по вычислениям , 16 (5): 854-879, DOI : 10,1137 / 0216057.
  • Макки, TA (1999), "Новая характеристика сильно аккордовых графов", Дискретная математика , 205 (1-3): 245-247, DOI : 10.1016 / S0012-365X (99) 00107-7.
  • Nishimura, N .; Ragde, P .; Thilikos, DM (2002), «О степенях графа для деревьев с листовой меткой», Journal of Algorithms , 42 : 69–108, CiteSeerX  10.1.1.43.1127 , doi : 10.1006 / jagm.2001.1195.
  • Раутенбах, Д. (2006), «Некоторые замечания о корнях листьев», Дискретная математика , 306 (13): 1456–1461, DOI : 10.1016 / j.disc.2006.03.030.
  • Райчаудхури, А. (1992), "О степенях сильно хордовых графов и графов с дугами окружностей", Ars Combinatoria , 34 : 147–160.
  • Eppstein, D .; Havvaei, H. (2020), "параметризованная Leaf автораспознавание через Погружение в Graph Products" , Algorithmica , 82 (8): 2337-2359, DOI : 10.1007 / s00453-020-00720-8 , S2CID  218988055.