Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

В теорії графів дистанційно успадковуваний граф або цілком сепарабельний граф це граф у якому відстані в будь якому зв я

Дистанційно-успадковуваний граф

В теорії графів дистанційно-успадковуваний граф (або цілком сепарабельний граф) — це граф, у якому відстані в будь-якому зв'язному породженому підграфі такі самі, як і в початковому графі. Таким чином, будь-який породжений підграф успадковує відстані більшого графу.

Дистанційно-успадковувані графи назвав і вперше вивчив Говорка (Howorka), хоча вже 1970 року Олару і Сакс (Olaru, Sachs) для еквівалентного класу графів показали, що клас містить досконалі графи.

Вже деякий час було відомо, що дистанційно-успадковувані графи складають клас графів перетинів, але модель перехрещення не була відомою, поки її не дали Іоан і Пауль (Gioan, Paul, 2012).

Визначення та опис

Оригінальне визначення дистанційно-успадковуваного графу — це граф G, такий, що, якщо будь-які дві вершини u і v належать зв'язному породженому підграфу H графу G, то деякий найкоротший шлях, що з'єднує u і v в G, має бути в підграфі H, причому відстань між u і v в H має бути такою ж, як у G.

Дистанційно-успадковувані графи можна описати кількома іншими еквівалентними способами:

  • Це графи, в яких будь-який породжений шлях є найкоротшим.
  • Це графи, в яких будь-який цикл довжини щонайменше п'ять має дві або більше діагоналей і в яких будь-який цикл довжини рівно п'ять має щонайменше одну пару діагоналей, що перетинаються.
  • Це графи, в яких будь-який цикл довжини п'ять і більше має щонайменше одну пару діагоналей, що перетинаються.
  • Це графи, в яких для будь-яких чотирьох вершин u, v, w і x щонайменше дві з трьох сум відстаней d(u,v)+d(w,x), d(u,w)+d(v,x) и d(u,x)+d(v,w) рівні.
  • Це графи, в яких немає ізометричних підграфів будь-якого циклу довжини п'ять і більше або будь-якого з трьох інших графів: 5-циклу з однією хордою, 5-циклу з двома хордами, що не перетинаються і 6-циклу з хордою, що сполучає протилежні вершини.
image
Три операції, за допомогою яких можна побудувати будь-який дистанційно-успадковуваний граф
  • Це графи, які можна створити з однієї вершини за допомогою послідовності трьох операцій (показаних на ілюстрації):
    1. Додавання нової висячої вершини, з'єднаної одним ребром з наявною вершиною графу.
    2. Заміна будь-якої вершини графу парою вершин, кожна з яких має тих самих сусідів, що й видалена вершина. Нова пара вершин називається двійнятами.
    3. Заміна будь-якої вершини графу парою вершин, кожна з яких має тих самих сусідів, що й видалена вершина, а також іншу вершину з пари. Нова пара вершин називається близнюками.
  • Це графи, які можна повністю розкласти на кліки і зірки (повні двочасткові графи K1,q) за допомогою [en] . У такому розщепленні отримують розклади графу на дві підмножини, такі, що розбивні ребра, які утворюють повний двочастковий підграф, формують два менших графи заміною кожного боку двочасткового графу вершинами з рекурсивним розщепленням цих двох підграфів.
  • Це графи, які мають одиничну рангову ширину, де рангова ширина графу визначається як мінімум максимального (рангу) за всіма ієрархічними поділами вершин серед певних підматриць матриці суміжності графу, визначених поділом.

Зв'язок з іншими сімействами графів

Будь-який дистанційно-успадковуваний граф є досконалим, точніше, цілком упорядковуваним графом. Будь-який дистанційно-успадковуваний граф є також парним графом, графом, у якому будь-які два шляхи між однією і тією ж парою вершин мають одночасно або парну довжину, або непарну. Будь-який парний (степінь) дистанційно-успадковуваного графу G (тобто граф G2i, утворений з'єднанням пар вершин на відстані, що не перевищує 2i в G) є хордальним графом.

Будь-який дистанційно-успадковуваний граф можна подати як граф перетинів хорд у колі, тобто як (коловий граф). Це можна показати, побудувавши граф за допомогою додавання висячих вершин, «двійнят» і «близнюків», формуючи при цьому на кожному кроці набір хорд, що утворює граф. Додавання висячої вершини відповідає додаванню хорди поруч з кінцем наявною хорди так, що нова хорда буде перетинати тільки цю хорду. Додавання «двійнят» відповідає заміні хорди двома паралельними хордами, що перетинають один і той самий набір хорд. Додавання «близнюків» відповідає заміні хорди двома майже паралельними перетинними хордами, які перетинають один і той самий набір інших хорд.

Дистанційно-успадковуваний граф є двочастковим тоді і тільки тоді, коли в ньому немає трикутників. Двочастковий дистанційно-успадковуваний граф можна побудувати з єдиної вершини додаванням тільки висячих вершин і «двійнят», оскільки будь-які «близнюки» утворюють трикутник, а операції додавання висячої вершини і «двійнят» зберігають двочастковість.

Графи, які можна побудувати з єдиної вершини додаванням висячих вершин і створенням «близнюків» без операції створення «двійнят», є окремими випадками (птолемеєвих графів) і включають блокові графи. Графи, які можна створити з єдиної вершини створенням «двійнят» і «близнюків», але без додавання висячих вершин, — це кографи, які є, таким чином, дистанційно-успадковуваними. Кографи — це точно незв'язне об'єднання дистанційно-успадковуваних графів з діаметром 2. Окіл будь-якої вершини дистанційно-успадковуваного графу є кографом. Транзитивне замикання орієнтованого графу, утвореного вибором будь-якого набору орієнтацій ребер будь-якого дерева, є дистанційно-успадковуваним. Окремий випадок, у якому дерево орієнтоване в напрямі від деякої вершини, утворює підклас дистанційно-успадковуваних графів, відомий як (тривіально досконалі графи), який також називають хордальними кографами.

Алгоритми

Дистанційно-успадковувані графи можна розпізнати й розкласти на послідовність висячих вершин і операцій подвоєння за лінійний час.

Оскільки дистанційно-успадковувані графи досконалі, деякі оптимізаційні задачі можна розв'язати за поліноміальний час, хоча ці задачі NP-складні для загальніших класів графів. Отже, можна за поліноміальний час знайти максимальну кліку або незалежну множину в дистанційно-успадковуваному графі або знайти його оптимальне розфарбування. Оскільки дистанційно-успадковувані графи є (коловими графами), вони успадковують алгоритми з поліноміальним часом для колових графів. Наприклад, можна визначити за поліноміальний час деревну ширину будь-якого колового графу, а отже й будь-якого дистанційно-успадковуваного графу. Крім того, клікова ширина будь-якого дистанційно-успадковуваного графу не перевищує трьох. Як наслідок, за (теоремою Курселя), для багатьох задач на цих графах існують ефективні алгоритми на основі динамічного програмування.

Деякі інші задачі оптимізації на дистанційно-успадковуваних графах можна розв'язати ефективно за допомогою алгоритмів, спеціально розроблених для таких графів. Як показали де Атрі та Москаріні, мінімальна (або, еквівалентно, кістяк із максимально можливим числом листків) на дистанційно-успадковуваних графах можна знайти за поліноміальний час. Гамільтонів граф або гамільтонів шлях будь-якого дистанційно-успадковуваного графу можна знайти за поліноміальний час.

Див. також

  • (Розщеплюваний граф)
  • (Граф парності)
  • (Граф Мейнеля)

Примітки

  1. Hammer, Maffray, 1990.
  2. Howorka, 1977.
  3. Олару і Сакс показали α-досконалість графів, у яких будь-який цикл довжини п'ять і більше має пару перетинних діагоналей (Sachs, 1970, теорема 5). За Ловашем (Lovász, 1972), α-досконалість є еквівалентною формою визначення досконалих графів.
  4. McKee, McMorris, 1999.
  5. Howorka, (1977); Bandelt, Mulder, (1986); Hammer, Maffray, (1990); Brandstädt, Le, Spinrad, (1999), Теорема 10.1.1, стор. 147.
  6. Gioan, Paul, (2012). Тісно пов'язану декомпозицію використали для візуалізації графів Епштейн, Гудріх і Менг (Eppstein, Goodrich, Meng, (2006)) і (для двочасткових дистанційно-успадковуваних графів) Хуей, Шефер і Штефанкович (Hui, Schaefer, Štefankovič, (2004)).
  7. Oum, 2005.
  8. Brandstädt, Le, Spinrad, 1999, с. 70–71, 82.
  9. Brandstädt, Le, Spinrad, 1999, с. 45.
  10. Brandstädt, Le, Spinrad, 1999, с. 164 Теорема 10.6.14.
  11. Cornelsen, Di Stefano, 2005.
  12. Damiand, Habib, Paul, (2001); Gioan, Paul, (2012). До цього про границю заявили Хаммер і Маффрей (Hammer, Maffray, (1990)), але Даміанд (Damiand) виявив у міркуваннях помилку.
  13. Когіс і Тьєррі Cogis, Thierry, (2005) представили простий прямий алгоритм для пошуку максимальних зважених незалежних множин у дистанційно-успадковуваних графах, заснований на розборі графу на висячі вершини і подвійні вершини, виправивши попередню спробу створення такого алгоритму Хаммером і Маффреєм (Hammer, Maffray, (1990)). Оскільки дистанційно-успадковувані графи є цілком упорядковуваними, їх можна оптимально розфарбувати за лінійний час за допомогою алгоритму LexBFS пошуку досконалого упорядкування і застосування жадібного розфарбовування.
  14. Kloks, 1996.
  15. Brandstädt, Le, Spinrad, 1999, с. 170.
  16. Golumbic, Rotics, 2000.
  17. Courcelle, Makowski, Rotics, 2000.
  18. Espelage, Gurski, Wanke, 2001.
  19. D'Atri, Moscarini, 1988.
  20. Hsieh, Ho, Hsu, Ko, 2002.
  21. Müller, Nicolai, 1993.

Література

  • Hans-Jürgen Bandelt, Henry Martyn Mulder. Distance-hereditary graphs // . — 1986. — Т. 41, вип. 2 (17 червня). — С. 182–208. — (Series B). — DOI:10.1016/0095-8956(86)90043-2..
  • Andreas Brandstädt, Van Bang Le, Jeremy Spinrad. Graph Classes: A Survey. — SIAM Monographs on Discrete Mathematics and Applications, 1999. — ..
  • O. Cogis, E. Thierry. Computing maximum stable sets for distance-hereditary graphs // Discrete Optimization. — 2005. — Т. 2, вип. 2 (17 червня). — С. 185–188. — DOI:10.1016/j.disopt.2005.03.004..
  • Sabine Cornelsen, Gabriele Di Stefano. Proc. 30th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2004). — Springer-Verlag, 2005. — Т. 3353. — С. 46–57. — ()[недоступне посилання].
  • B. Courcelle, J. A. Makowski, U. Rotics. Linear time solvable optimization problems on graphs on bounded clique width // Theory of Computing Systems. — 2000. — Т. 33, вип. 2 (17 червня). — С. 125–150. — DOI:10.1007/s002249910009..
  • Alessandro D'Atri, Marina Moscarini. Distance-hereditary graphs, Steiner trees, and connected domination // . — 1988. — Т. 17, вип. 3 (17 червня). — С. 521–538. — DOI:10.1137/0217032..
  • Guillaume Damiand, Michel Habib, Christophe Paul. A simple paradigm for graph recognition: application to cographs and distance hereditary graphs // . — 2001. — Т. 263, вип. 1–2 (17 червня). — С. 99–111. — DOI:10.1016/S0304-3975(00)00234-6..
  • David Eppstein, Michael T. Goodrich, Jeremy Yu Meng. (Proc. 13th Int. Symp. Graph Drawing (GD 2005)) / Patrick Healy, Nikola S. Nikolov. — Springer-Verlag, 2006. — Т. 3843. — С. 165–176. — ().
  • W. Espelage, F. Gurski, E. Wanke. Proc. 27th Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2001). — Springer-Verlag, 2001. — Т. 2204. — С. 117–128. — ().
  • Emeric Gioan, Christophe Paul. Split decomposition and graph-labelled trees: Characterizations and fully dynamic algorithms for totally decomposable graphs // . — 2012. — Т. 160, вип. 6 (17 червня). — С. 708–733. — arXiv:0810.1823. — DOI:10.1016/j.dam.2011.05.007..
  • Martin Charles Golumbic, Udi Rotics. On the clique-width of some perfect graph classes // International Journal of Foundations of Computer Science. — 2000. — Т. 11, вип. 3 (17 червня). — С. 423–443. — DOI:10.1142/S0129054100000260..
  • Peter Ladislaw Hammer, Frédéric Maffray. Completely separable graphs // . — 1990. — Т. 27, вип. 1–2 (17 червня). — С. 85–99. — DOI:10.1016/0166-218X(90)90131-U..
  • Edward Howorka. A characterization of distance-hereditary graphs // The Quarterly Journal of Mathematics. Oxford. Second Series. — 1977. — Т. 28, вип. 112 (17 червня). — С. 417–420. — DOI:10.1093/qmath/28.4.417..
  • Sun-yuan Hsieh, Chin-wen Ho, Tsan-sheng Hsu, Ming-tat Ko. Computing and Combinatorics: 8th Annual International Conference, COCOON 2002 Singapore, August 15–17, 2002, Proceedings. — Springer-Verlag, 2002. — Т. 2387. — С. 51–75. — () — . — DOI:10.1007/3-540-45655-4_10..
  • Peter Hui, Marcus Schaefer, Daniel Štefankovič. (Proc. 12th Int. Symp. Graph Drawing (GD 2004)) / János Pach. — Springer-Verlag, 2004. — Т. 3383. — С. 318–328. — ().
  • T. Kloks. Treewidth of circle graphs // International Journal of Foundations of Computer Science. — 1996. — Т. 7, вип. 2 (17 червня). — С. 111–120. — DOI:10.1142/S0129054196000099..
  • László Lovász. Normal hypergraphs and the perfect graph conjecture // . — 1972. — Т. 2, вип. 3 (17 червня). — С. 253–267. — DOI:10.1016/0012-365X(72)90006-4..
  • Terry A. McKee, F. R. McMorris. Topics in Intersection Graph Theory. — Philadelphia : Society for Industrial and Applied Mathematics, 1999. — Т. 2. — (SIAM Monographs on Discrete Mathematics and Applications) — .
  • Haiko Müller, Falk Nicolai. Polynomial time algorithms for Hamiltonian problems on bipartite distance-hereditary graphs // . — 1993. — Т. 46, вип. 5 (17 червня). — С. 225–230. — DOI:10.1016/0020-0190(93)90100-N..
  • Sang-il Oum. Rank-width and vertex-minors // . — 2005. — Т. 95, вип. 1 (17 червня). — С. 79–100. — (Series B). — DOI:10.1016/j.jctb.2005.03.003..
  • Horst Sachs. Combinatorial Structures and their Applications (Proc. Calgary Internat. Conf., Calgary, Alta., 1969). — Gordon and Breach, 1970. — С. 377–384..

Посилання

  • , Information System on Graph Classes and their Inclusions, архів оригіналу за 3 травня 2021, процитовано 12 липня 2021

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Дата публікації:
V teoriyi grafiv distancijno uspadkovuvanij graf abo cilkom separabelnij graf ce graf u yakomu vidstani v bud yakomu zv yaznomu porodzhenomu pidgrafi taki sami yak i v pochatkovomu grafi Takim chinom bud yakij porodzhenij pidgraf uspadkovuye vidstani bilshogo grafu Distancijno uspadkovuvani grafi nazvav i vpershe vivchiv Govorka Howorka hocha vzhe 1970 roku Olaru i Saks Olaru Sachs dlya ekvivalentnogo klasu grafiv pokazali sho klas mistit doskonali grafi Vzhe deyakij chas bulo vidomo sho distancijno uspadkovuvani grafi skladayut klas grafiv peretiniv ale model perehreshennya ne bula vidomoyu poki yiyi ne dali Ioan i Paul Gioan Paul 2012 Viznachennya ta opisOriginalne viznachennya distancijno uspadkovuvanogo grafu ce graf G takij sho yaksho bud yaki dvi vershini u i v nalezhat zv yaznomu porodzhenomu pidgrafu H grafu G to deyakij najkorotshij shlyah sho z yednuye u i v v G maye buti v pidgrafi H prichomu vidstan mizh u i v v H maye buti takoyu zh yak u G Distancijno uspadkovuvani grafi mozhna opisati kilkoma inshimi ekvivalentnimi sposobami Ce grafi v yakih bud yakij porodzhenij shlyah ye najkorotshim Ce grafi v yakih bud yakij cikl dovzhini shonajmenshe p yat maye dvi abo bilshe diagonalej i v yakih bud yakij cikl dovzhini rivno p yat maye shonajmenshe odnu paru diagonalej sho peretinayutsya Ce grafi v yakih bud yakij cikl dovzhini p yat i bilshe maye shonajmenshe odnu paru diagonalej sho peretinayutsya Ce grafi v yakih dlya bud yakih chotiroh vershin u v w i x shonajmenshe dvi z troh sum vidstanej d u v d w x d u w d v x i d u x d v w rivni Ce grafi v yakih nemaye izometrichnih pidgrafiv bud yakogo ciklu dovzhini p yat i bilshe abo bud yakogo z troh inshih grafiv 5 ciklu z odniyeyu hordoyu 5 ciklu z dvoma hordami sho ne peretinayutsya i 6 ciklu z hordoyu sho spoluchaye protilezhni vershini Tri operaciyi za dopomogoyu yakih mozhna pobuduvati bud yakij distancijno uspadkovuvanij graf Ce grafi yaki mozhna stvoriti z odniyeyi vershini za dopomogoyu poslidovnosti troh operacij pokazanih na ilyustraciyi Dodavannya novoyi visyachoyi vershini z yednanoyi odnim rebrom z nayavnoyu vershinoyu grafu Zamina bud yakoyi vershini grafu paroyu vershin kozhna z yakih maye tih samih susidiv sho j vidalena vershina Nova para vershin nazivayetsya dvijnyatami Zamina bud yakoyi vershini grafu paroyu vershin kozhna z yakih maye tih samih susidiv sho j vidalena vershina a takozh inshu vershinu z pari Nova para vershin nazivayetsya bliznyukami Ce grafi yaki mozhna povnistyu rozklasti na kliki i zirki povni dvochastkovi grafi K1 q za dopomogoyu en U takomu rozsheplenni otrimuyut rozkladi grafu na dvi pidmnozhini taki sho rozbivni rebra yaki utvoryuyut povnij dvochastkovij pidgraf formuyut dva menshih grafi zaminoyu kozhnogo boku dvochastkovogo grafu vershinami z rekursivnim rozsheplennyam cih dvoh pidgrafiv Ce grafi yaki mayut odinichnu rangovu shirinu de rangova shirina grafu viznachayetsya yak minimum maksimalnogo rangu za vsima iyerarhichnimi podilami vershin sered pevnih pidmatric matrici sumizhnosti grafu viznachenih podilom Zv yazok z inshimi simejstvami grafivBud yakij distancijno uspadkovuvanij graf ye doskonalim tochnishe cilkom uporyadkovuvanim grafom Bud yakij distancijno uspadkovuvanij graf ye takozh parnim grafom grafom u yakomu bud yaki dva shlyahi mizh odniyeyu i tiyeyu zh paroyu vershin mayut odnochasno abo parnu dovzhinu abo neparnu Bud yakij parnij stepin distancijno uspadkovuvanogo grafu G tobto graf G2i utvorenij z yednannyam par vershin na vidstani sho ne perevishuye 2i v G ye hordalnim grafom Bud yakij distancijno uspadkovuvanij graf mozhna podati yak graf peretiniv hord u koli tobto yak kolovij graf Ce mozhna pokazati pobuduvavshi graf za dopomogoyu dodavannya visyachih vershin dvijnyat i bliznyukiv formuyuchi pri comu na kozhnomu kroci nabir hord sho utvoryuye graf Dodavannya visyachoyi vershini vidpovidaye dodavannyu hordi poruch z kincem nayavnoyu hordi tak sho nova horda bude peretinati tilki cyu hordu Dodavannya dvijnyat vidpovidaye zamini hordi dvoma paralelnimi hordami sho peretinayut odin i toj samij nabir hord Dodavannya bliznyukiv vidpovidaye zamini hordi dvoma majzhe paralelnimi peretinnimi hordami yaki peretinayut odin i toj samij nabir inshih hord Distancijno uspadkovuvanij graf ye dvochastkovim todi i tilki todi koli v nomu nemaye trikutnikiv Dvochastkovij distancijno uspadkovuvanij graf mozhna pobuduvati z yedinoyi vershini dodavannyam tilki visyachih vershin i dvijnyat oskilki bud yaki bliznyuki utvoryuyut trikutnik a operaciyi dodavannya visyachoyi vershini i dvijnyat zberigayut dvochastkovist Grafi yaki mozhna pobuduvati z yedinoyi vershini dodavannyam visyachih vershin i stvorennyam bliznyukiv bez operaciyi stvorennya dvijnyat ye okremimi vipadkami ptolemeyevih grafiv i vklyuchayut blokovi grafi Grafi yaki mozhna stvoriti z yedinoyi vershini stvorennyam dvijnyat i bliznyukiv ale bez dodavannya visyachih vershin ce kografi yaki ye takim chinom distancijno uspadkovuvanimi Kografi ce tochno nezv yazne ob yednannya distancijno uspadkovuvanih grafiv z diametrom 2 Okil bud yakoyi vershini distancijno uspadkovuvanogo grafu ye kografom Tranzitivne zamikannya oriyentovanogo grafu utvorenogo viborom bud yakogo naboru oriyentacij reber bud yakogo dereva ye distancijno uspadkovuvanim Okremij vipadok u yakomu derevo oriyentovane v napryami vid deyakoyi vershini utvoryuye pidklas distancijno uspadkovuvanih grafiv vidomij yak trivialno doskonali grafi yakij takozh nazivayut hordalnimi kografami AlgoritmiDistancijno uspadkovuvani grafi mozhna rozpiznati j rozklasti na poslidovnist visyachih vershin i operacij podvoyennya za linijnij chas Oskilki distancijno uspadkovuvani grafi doskonali deyaki optimizacijni zadachi mozhna rozv yazati za polinomialnij chas hocha ci zadachi NP skladni dlya zagalnishih klasiv grafiv Otzhe mozhna za polinomialnij chas znajti maksimalnu kliku abo nezalezhnu mnozhinu v distancijno uspadkovuvanomu grafi abo znajti jogo optimalne rozfarbuvannya Oskilki distancijno uspadkovuvani grafi ye kolovimi grafami voni uspadkovuyut algoritmi z polinomialnim chasom dlya kolovih grafiv Napriklad mozhna viznachiti za polinomialnij chas derevnu shirinu bud yakogo kolovogo grafu a otzhe j bud yakogo distancijno uspadkovuvanogo grafu Krim togo klikova shirina bud yakogo distancijno uspadkovuvanogo grafu ne perevishuye troh Yak naslidok za teoremoyu Kurselya dlya bagatoh zadach na cih grafah isnuyut efektivni algoritmi na osnovi dinamichnogo programuvannya Deyaki inshi zadachi optimizaciyi na distancijno uspadkovuvanih grafah mozhna rozv yazati efektivno za dopomogoyu algoritmiv specialno rozroblenih dlya takih grafiv Yak pokazali de Atri ta Moskarini minimalna abo ekvivalentno kistyak iz maksimalno mozhlivim chislom listkiv na distancijno uspadkovuvanih grafah mozhna znajti za polinomialnij chas Gamiltoniv graf abo gamiltoniv shlyah bud yakogo distancijno uspadkovuvanogo grafu mozhna znajti za polinomialnij chas Div takozhRozsheplyuvanij graf Graf parnosti Graf MejnelyaPrimitkiHammer Maffray 1990 Howorka 1977 Olaru i Saks pokazali a doskonalist grafiv u yakih bud yakij cikl dovzhini p yat i bilshe maye paru peretinnih diagonalej Sachs 1970 teorema 5 Za Lovashem Lovasz 1972 a doskonalist ye ekvivalentnoyu formoyu viznachennya doskonalih grafiv McKee McMorris 1999 Howorka 1977 Bandelt Mulder 1986 Hammer Maffray 1990 Brandstadt Le Spinrad 1999 Teorema 10 1 1 stor 147 Gioan Paul 2012 Tisno pov yazanu dekompoziciyu vikoristali dlya vizualizaciyi grafiv Epshtejn Gudrih i Meng Eppstein Goodrich Meng 2006 i dlya dvochastkovih distancijno uspadkovuvanih grafiv Huej Shefer i Shtefankovich Hui Schaefer Stefankovic 2004 Oum 2005 Brandstadt Le Spinrad 1999 s 70 71 82 Brandstadt Le Spinrad 1999 s 45 Brandstadt Le Spinrad 1999 s 164 Teorema 10 6 14 Cornelsen Di Stefano 2005 Damiand Habib Paul 2001 Gioan Paul 2012 Do cogo pro granicyu zayavili Hammer i Maffrej Hammer Maffray 1990 ale Damiand Damiand viyaviv u mirkuvannyah pomilku Kogis i Tyerri Cogis Thierry 2005 predstavili prostij pryamij algoritm dlya poshuku maksimalnih zvazhenih nezalezhnih mnozhin u distancijno uspadkovuvanih grafah zasnovanij na rozbori grafu na visyachi vershini i podvijni vershini vipravivshi poperednyu sprobu stvorennya takogo algoritmu Hammerom i Maffreyem Hammer Maffray 1990 Oskilki distancijno uspadkovuvani grafi ye cilkom uporyadkovuvanimi yih mozhna optimalno rozfarbuvati za linijnij chas za dopomogoyu algoritmu LexBFS poshuku doskonalogo uporyadkuvannya i zastosuvannya zhadibnogo rozfarbovuvannya Kloks 1996 Brandstadt Le Spinrad 1999 s 170 Golumbic Rotics 2000 Courcelle Makowski Rotics 2000 Espelage Gurski Wanke 2001 D Atri Moscarini 1988 Hsieh Ho Hsu Ko 2002 Muller Nicolai 1993 LiteraturaHans Jurgen Bandelt Henry Martyn Mulder Distance hereditary graphs 1986 T 41 vip 2 17 chervnya S 182 208 Series B DOI 10 1016 0095 8956 86 90043 2 Andreas Brandstadt Van Bang Le Jeremy Spinrad Graph Classes A Survey SIAM Monographs on Discrete Mathematics and Applications 1999 ISBN 0 89871 432 X O Cogis E Thierry Computing maximum stable sets for distance hereditary graphs Discrete Optimization 2005 T 2 vip 2 17 chervnya S 185 188 DOI 10 1016 j disopt 2005 03 004 Sabine Cornelsen Gabriele Di Stefano Proc 30th Int Worksh Graph Theoretic Concepts in Computer Science WG 2004 Springer Verlag 2005 T 3353 S 46 57 nedostupne posilannya B Courcelle J A Makowski U Rotics Linear time solvable optimization problems on graphs on bounded clique width Theory of Computing Systems 2000 T 33 vip 2 17 chervnya S 125 150 DOI 10 1007 s002249910009 Alessandro D Atri Marina Moscarini Distance hereditary graphs Steiner trees and connected domination 1988 T 17 vip 3 17 chervnya S 521 538 DOI 10 1137 0217032 Guillaume Damiand Michel Habib Christophe Paul A simple paradigm for graph recognition application to cographs and distance hereditary graphs 2001 T 263 vip 1 2 17 chervnya S 99 111 DOI 10 1016 S0304 3975 00 00234 6 David Eppstein Michael T Goodrich Jeremy Yu Meng Proc 13th Int Symp Graph Drawing GD 2005 Patrick Healy Nikola S Nikolov Springer Verlag 2006 T 3843 S 165 176 W Espelage F Gurski E Wanke Proc 27th Int Worksh Graph Theoretic Concepts in Computer Science WG 2001 Springer Verlag 2001 T 2204 S 117 128 Emeric Gioan Christophe Paul Split decomposition and graph labelled trees Characterizations and fully dynamic algorithms for totally decomposable graphs 2012 T 160 vip 6 17 chervnya S 708 733 arXiv 0810 1823 DOI 10 1016 j dam 2011 05 007 Martin Charles Golumbic Udi Rotics On the clique width of some perfect graph classes International Journal of Foundations of Computer Science 2000 T 11 vip 3 17 chervnya S 423 443 DOI 10 1142 S0129054100000260 Peter Ladislaw Hammer Frederic Maffray Completely separable graphs 1990 T 27 vip 1 2 17 chervnya S 85 99 DOI 10 1016 0166 218X 90 90131 U Edward Howorka A characterization of distance hereditary graphs The Quarterly Journal of Mathematics Oxford Second Series 1977 T 28 vip 112 17 chervnya S 417 420 DOI 10 1093 qmath 28 4 417 Sun yuan Hsieh Chin wen Ho Tsan sheng Hsu Ming tat Ko Computing and Combinatorics 8th Annual International Conference COCOON 2002 Singapore August 15 17 2002 Proceedings Springer Verlag 2002 T 2387 S 51 75 ISBN 978 3 540 43996 7 DOI 10 1007 3 540 45655 4 10 Peter Hui Marcus Schaefer Daniel Stefankovic Proc 12th Int Symp Graph Drawing GD 2004 Janos Pach Springer Verlag 2004 T 3383 S 318 328 T Kloks Treewidth of circle graphs International Journal of Foundations of Computer Science 1996 T 7 vip 2 17 chervnya S 111 120 DOI 10 1142 S0129054196000099 Laszlo Lovasz Normal hypergraphs and the perfect graph conjecture 1972 T 2 vip 3 17 chervnya S 253 267 DOI 10 1016 0012 365X 72 90006 4 Terry A McKee F R McMorris Topics in Intersection Graph Theory Philadelphia Society for Industrial and Applied Mathematics 1999 T 2 SIAM Monographs on Discrete Mathematics and Applications ISBN 0 89871 430 3 Haiko Muller Falk Nicolai Polynomial time algorithms for Hamiltonian problems on bipartite distance hereditary graphs 1993 T 46 vip 5 17 chervnya S 225 230 DOI 10 1016 0020 0190 93 90100 N Sang il Oum Rank width and vertex minors 2005 T 95 vip 1 17 chervnya S 79 100 Series B DOI 10 1016 j jctb 2005 03 003 Horst Sachs Combinatorial Structures and their Applications Proc Calgary Internat Conf Calgary Alta 1969 Gordon and Breach 1970 S 377 384 Posilannya Information System on Graph Classes and their Inclusions arhiv originalu za 3 travnya 2021 procitovano 12 lipnya 2021
Топ