Мощность листа

Дерево (вверху) и соответствующая ему трехлистная степень (внизу).

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

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

Связанные классы графиков

Поскольку степени сильно хордальных графов сильно хордальны, а деревья сильно хордальны, отсюда следует, что степени листьев являются сильно хордальными графами. На самом деле листовые степени образуют собственный подкласс сильно хордальных графов; граф является степенью листа тогда и только тогда, когда он является графом NeST с фиксированным допуском и такие графы являются собственным подклассом сильно хордальных графов.

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

Степени k -листов для ограниченных значений k имеют ограниченную ширину клика , но это не относится к степеням листьев с неограниченными показателями.

Структура и признание

Граф является трехлистной степенью тогда и только тогда, когда он является хордальным графом без (быка, дротика, драгоценного камня) . На основании этой и подобных характеристик трехлистные степени можно распознать за линейное время .

Характеристики четырехлистных степеней даны Раутенбахом (2006) и Брандштедтом, Ле и Шритараном (2008) , что также позволяет распознавание линейного времени. Распознавание 5-листовых и 6-листовых степенных графов также решается за линейное время Чангом и Ко (2007). и Дюкофф (2018), соответственно.

Для k ≥ 7 проблема распознавания степеней k -листа долгое время оставалась нерешенной, но Лафонд (2021) показал, что степени k -листа можно распознать за полиномиальное время для любого фиксированного k . Однако высокая зависимость от параметра k делает этот алгоритм непригодным для практического использования.

Кроме того, было доказано, что распознавание степеней k -листов можно осуществить с фиксированным параметром, если оно параметризовано k и вырожденностью входного графа.

Ссылки

• Бибельниекс, Э.; Диринг, П.М. (1993), «Графы допуска поддерева окрестности», Discrete Applied Mathematics , 43 : 13–26, doi : 10.1016/0166-218X(93)90165-K .
• Брандштедт, Андреас; Хундт, Кристиан (2008), «Графы Птолемея и интервальные графики являются листовыми степенями», LATIN 2008: Теоретическая информатика , Конспекты лекций по вычислительной технике. наук, том. 4957, Springer, Берлин, стр. 479–491, doi : 10.1007/978-3-540-78773-0_42 , ISBN.  978-3-540-78772-3 , МР   2472761 .
• Брандштедт, Андреас ; Хундт, Кристиан; Манчини, Федерико; Вагнер, Питер (2010), «Графы направленных путей с корнем являются степенями листьев», Discrete Mathematics , 310 (4): 897–910, doi : 10.1016/j.disc.2009.10.006 .
• Брандштедт, Андреас ; Ле, Ван Банг (2006), «Распознавание структуры и линейного времени трехлистных степеней», Information Processing Letters , 98 (4): 133–138, CiteSeerX   10.1.1.144.3486 , doi : 10.1016/j.ipl.2006.01 .004 .
• Брандштедт, Андреас ; Ле, Ван Банг; Шритаран, Р. (2008), «Распознавание структуры и линейного времени четырехлистных степеней», Транзакции 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 .
• Дальхаус, Э.; Дюше, П. (1987), «О сильно хордальных графах», Ars Combinatoria , 24 B : 23–30 .
• Дальхаус, Э.; Мануэль, доктор медицинских наук; Миллер, М. (1998), «Характеристика сильно хордальных графов», Discrete Mathematics , 187 (1–3): 269–271, doi : 10.1016/S0012-365X(97)00268-9 .
• Дом, М.; Го, Дж.; Хюффнер, Ф.; Нидермайер, Р. (2006), «Компенсация ошибок при проблемах с корнями листьев», Algorithmica , 44 (4): 363–381, CiteSeerX   10.1.1.218.490 , doi : 10.1007/s00453-005-1180-z , S2CID   75279 .
• Фарбер, М. (1983), «Характеристики сильно хордальных графов», Discrete Mathematics , 43 (2–3): 173–189, doi : 10.1016/0012-365X(83)90154-1 .
• Гурски, Фрэнк; Ванке, Эгон (2009), «NLC-ширина и кликовая ширина для степеней графов ограниченной ширины дерева», Discrete Applied Mathematics , 157 (4): 583–595, doi : 10.1016/j.dam.2008.08. 031 , МР   2499471 .
• Хейворд, РБ; Кирни, ЧП; Малтон, А. (2002), «Графики NeST», Discrete Applied Mathematics , 121 (1–3): 139–153, doi : 10.1016/s0166-218x(01)00207-4 .
• Лафонд, Мануэль (2021), «Распознавание степеней k-листов за полиномиальное время для постоянного k», Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2022 года : 1384–1410, arXiv : 2110.15421 .
• Любив, А. (1987), «Двойной лексический порядок матриц», SIAM Journal on Computing , 16 (5): 854–879, doi : 10.1137/0216057 .
• Макки, Т. А. (1999), «Новая характеристика сильно хордальных графов», Discrete Mathematics , 205 (1–3): 245–247, doi : 10.1016/S0012-365X(99)00107-7 .
• Нисимура, Н.; Рагде, П.; Тиликос, Д.М. (2002), «О степенях графа для деревьев с помеченными листьями», Journal of Algorithms , 42 : 69–108, CiteSeerX   10.1.1.43.1127 , doi : 10.1006/jagm.2001.1195 .
• Раутенбах, Д. (2006), «Некоторые замечания о корнях листьев», Discrete Mathematics , 306 (13): 1456–1461, doi : 10.1016/j.disc.2006.03.030 .
• Райчаудхури, А. (1992), «О степенях сильно хордальных графов и дуговых графов», Ars Combinatoria , 34 : 147–160 .
• Эппштейн, Д.; Хавваи, Х. (2020), «Параметрическое распознавание мощности листьев посредством внедрения в графовые продукты» , Algorithmica , 82 (8): 2337–2359, arXiv : 1810.02452 , doi : 10.1007/s00453-020-00720-8 , S2CID   2189880 55 .