Листовая сила - Leaf power

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

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

Граф - это сила листа если это ${\displaystyle k}$-листовая мощность для некоторых ${\displaystyle k}$.^[1] Эти графики имеют приложения в филогения, проблема реконструкции эволюционных деревьев.

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

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

В Brandstädt et al. (2010) показано, что интервальные графики и более крупный класс корневых ориентированных графов путей - это листовые степени. В графики безразличия в точности те силы листа, лежащие в основе которых гусеницы.

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

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

Нерешенная проблема в информатике: Есть ли алгоритм с полиномиальным временем для распознавания листовых степеней или ${\displaystyle k}$-листовые полномочия для ${\displaystyle k\geq 7}$? (больше нерешенных проблем в информатике)

Граф является 2-листовой степенью тогда и только тогда, когда это несвязный союз из клики (т.е. кластерный граф ).^[1]

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

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

За ${\displaystyle k}$ ≥ 7 проблема распознавания ${\displaystyle k}$-листовые полномочия открыты, и аналогично, это нерешенная проблема, можно ли распознать листовые полномочия в полиномиальное время. Однако было доказано, что признание ${\displaystyle k}$-листовые полномочия управляемый с фиксированными параметрами при параметризации ${\displaystyle k}$ и вырождение входного графа.^[10]

Примечания

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

Рекомендации

• Bibelnieks, E .; Уважаемый, П. (1993), "Графики толерантности к поддереву соседства", Дискретная прикладная математика, 43: 13–26, Дои:10.1016 / 0166-218X (93) 90165-К.
• Брандштадт, Андреас; Хундт, Кристиан (2008), «Птолемеевы графы и интервальные графы являются листовыми степенями», ЛАТИН 2008: Теоретическая информатика., Конспект лекций по вычисл. Наук, 4957, Springer, Berlin, pp. 479–491, Дои:10.1007/978-3-540-78773-0_42, ISBN  978-3-540-78772-3, МИСТЕР  2472761.
• Брандштадт, Андреас; Хундт, Кристиан; Манчини, Федерико; Вагнер, Питер (2010), «Графы ориентированных путей с корнем являются листовыми степенями», Дискретная математика, 310 (4): 897–910, Дои:10.1016 / j.disc.2009.10.006.
• Брандштадт, Андреас; Ле, Ван Банг (2006), "Распознавание структуры и линейного времени трехлистных степеней", Письма об обработке информации, 98 (4): 133–138, CiteSeerX  10.1.1.144.3486, Дои:10.1016 / j.ipl.2006.01.004.
• Брандштадт, Андреас; Ле, Ван Банг; Sritharan, R. (2008), "Распознавание структуры и линейного времени четырехлистных сил", ACM-транзакции на алгоритмах, 5: 1–22, Дои:10.1145/1435375.1435386, S2CID  6114466.
• Брандштадт, Андреас; Ле, Ван Банг; Спинрад, Джереми (1999), Классы графов: обзор, Монографии SIAM по дискретной математике и приложениям, ISBN  978-0-89871-432-6.
• Broin, M.W .; Лоу, Т.Дж. (1986), "Графики толерантности к поддереву соседства", SIAM J. Algebr. Дискретные методы, 7: 348–357, Дои:10.1137/0607039.
• Dahlhaus, E .; Duchet, P. (1987), "О сильно хордовых графах", Ars Combinatoria, 24 млрд: 23–30.
• Dahlhaus, E .; Manuel, P.D .; Миллер, М. (1998), "Характеристика сильно хордовых графов", Дискретная математика, 187 (1–3): 269–271, Дои:10.1016 / S0012-365X (97) 00268-9.
• Дом, М .; Guo, J .; Hüffner, F .; Нидермайер, Р. (2006), «Компенсация ошибок при проблемах с корнями листьев», Алгоритмика, 44 (4): 363–381, CiteSeerX  10.1.1.218.490, Дои:10.1007 / s00453-005-1180-z, S2CID  75279.
• Фарбер, М. (1983), "Характеризация сильно хордовых графов", Дискретная математика, 43 (2–3): 173–189, Дои:10.1016 / 0012-365X (83) 90154-1.
• Гурски, Франк; Ванке, Эгон (2009), "Ширина NLC и ширина клики для степеней графов ограниченной ширины дерева", Дискретная прикладная математика, 157 (4): 583–595, Дои:10.1016 / j.dam.2008.08.031, МИСТЕР  2499471.
• Hayward, R.B .; Kearney, P.E .; Малтон, А. (2002), "Графы NeST", Дискретная прикладная математика, 121 (1–3): 139–153, Дои:10.1016 / s0166-218x (01) 00207-4.
• Любив, А. (1987), "Дважды лексические упорядочения матриц", SIAM Журнал по вычислениям, 16 (5): 854–879, Дои:10.1137/0216057.
• Макки, Т. А. (1999), "Новая характеризация сильно хордовых графов", Дискретная математика, 205 (1–3): 245–247, Дои:10.1016 / S0012-365X (99) 00107-7.
• Nishimura, N .; Ragde, P .; Тиликос, Д. (2002), "О степенях графа для деревьев с листами", Журнал алгоритмов, 42: 69–108, CiteSeerX  10.1.1.43.1127, Дои:10.1006 / jagm.2001.1195.
• Раутенбах, Д. (2006), «Некоторые замечания о корнях листьев», Дискретная математика, 306 (13): 1456–1461, Дои:10.1016 / j.disc.2006.03.030.
• Райчаудхури, А. (1992), "О степенях сильно хордовых графов и круговых дуговых графов", Ars Combinatoria, 34: 147–160.
• Eppstein, D .; Хаввеи, Х. (2020), «Распознавание параметризованной листовой мощности посредством встраивания в графические продукты», Алгоритмика, 82 (8): 2337–2359, Дои:10.1007 / s00453-020-00720-8, S2CID  218988055.