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

В теорії графів клікова ширина графа G displaystyle G це параметр який описує структурну складність графа Параметр тісно

Клікова ширина

В теорії графів клікова ширина графа  — це параметр, який описує структурну складність графа. Параметр тісно пов'язаний з деревною шириною, але, на відміну від деревної ширини, клікова ширина може бути обмеженою навіть для щільних графів. Клікова ширина визначається як мінімальна кількість міток, необхідних для побудови за допомогою таких 4 операцій:

  1. Створення нової вершини v з міткою i (операція i(v))
  2. Незв'язне об'єднання двох розмічених графів G і H (операція )
  3. З'єднання ребром кожної вершини з міткою i з кожною вершиною з міткою j (операція η(i, j)), де
  4. Перейменування мітки i на j (операція ρ(i,j))
image
Побудова дистанційно-успадковуваного графа клікової ширини 3 незв'язним об'єднанням, перейменуванням вершин і об'єднанням міток. Мітки вершин показано кольорами.

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

Послідовності побудови, на які спирається поняття клікової ширини, сформулювали Курсель, Енгельфрід і Розенберг у 1990 і Ванке. Назву «клікова ширина» використала для іншої концепції Хлєбікова. Від 1993 термін став уживатися в сучасному значенні.

Особливі класи графів

Кографи — це точно графи з кліковою шириною, що не перевищує двох. Будь-який дистанційно-успадковуваний граф має клікову ширину, що не перевищує 3. Однак клікова ширина інтервальних графів не обмежена (згідно зі структурою ґратки). Так само не обмежена клікова ширина двочасткових (графів перестановок) (згідно з подібною структурою ґратки). Ґрунтуючись на описі кографів як графів без породжених підграфів, ізоморфних шляхам без хорд, класифіковано клікову ширину багатьох класів графів, визначених забороненими породженими підграфами.

Інші графи з обмеженою кліковою шириною — k-[en] для обмежених значень k, тобто породжені підграфи листків дерева T у степені графа Tk. Однак степінь листків за необмеженого показника степеня не має обмеженої ширини листків.

Межі

Курсель і Олару, а також Корнейл і Ротікс, дали такі межі клікової ширини деяких графів:

  • Якщо граф має клікову ширину максимум k, то те саме істинне для будь-якого породженого підграфа графа.
  • Доповнення графа з кліковою шириною k має клікову ширину, що не перевищує 2k.
  • Графи з деревною шириною w мають клікову ширину, що не перевищує 3 · 2w − 1. Експоненційна залежність у межі необхідна — існують графи, клікова ширина яких експоненційно більша від їхньої деревної ширини. З іншого боку, графи з обмеженою кліковою шириною можуть мати необмежену деревну ширину. Наприклад, повні графи з n вершинами мають клікову ширину 2, але деревну ширину n − 1. Однак, графи з кліковою шириною k, які не містять повного двочасткового графа Kt,t як підграфа, мають деревну ширину, що не перевищує 3k(t − 1) − 1. Таким чином, для будь-якого сімейства розріджених графів наявність обмеження деревної ширини еквівалентне наявності обмеження клікової ширини.
  • Інший параметр графів, рангова ширина, обмежена в обох напрямках кліковою шириною: рангова ширина ≤ клікової ширини ≤ 2рангової ширини + 1 .

Крім того, якщо граф G має клікову ширину k, то степінь графа Gc має клікову ширину, що не перевищує 2kck. Хоча в нерівностях для клікової ширини в порівняннях з деревною шириною та степенем графа присутня експонента, ці межі не дають суперпозиції — якщо граф G має деревну ширину w, то Gc має клікову ширину, що не перевершує 2(c + 1)w + 1 − 2, лише проста експонента від деревної ширини.

Обчислювальна складність

image Нерозв'язана проблема математики:
Чи можна граф з обмеженою кліковою шириною розпізнати за поліноміальний час?
(більше нерозв'язаних проблем математики)

Багато задачі оптимізації, NP-складні для більш загальних класів графів, можна ефективно розв'язати за допомогою динамічного програмування на графах з обмеженою кліковою шириною, якщо послідовність побудови цих графів відома. Зокрема, будь-який інваріант графа, який можна виразити в MSO1 ([en], вид логіки другого порядку, що дозволяє квантори над множинами вершин) має алгоритм лінійного часу для графів з обмеженою шириною за одним із формулювань (теореми Курселя). Можна також знайти оптимальні розмальовки або гамільтонові цикли графів з обмеженою кліковою шириною за поліноміальний час, якщо послідовність побудови графа відома, але степінь полінома збільшується зі збільшенням клікової ширини, і доводи з теорії обчислювальної складності показують, що така залежність, схоже, неминуча.

Графи з кліковою шириною три можна розпізнати і послідовність їх побудови можна знайти за поліноміальний час за допомогою алгоритму, заснованого на [en]. Для класів графів з необмеженою кліковою шириною точне обчислення клікової ширини є NP-складною задачею, а також NP-складно отримати апроксимацію з сублінійною адитивною помилкою. Однак, якщо верхня межа клікової ширини відома, можна отримати послідовність побудови графа з обмеженою шириною (експоненціально більшою від справжньої клікової ширини) за поліноміальний час. Залишається відкритим питання, чи можна точну клікову ширину або близьку апроксимацію обчислити за [en] час, чи можна її обчислити за поліноміальний час для графів з будь-якою фіксованою межею клікової ширини, або, навіть, чи можна графи з кліковою шириною чотири розпізнати за поліноміальний час.

Зв'язок з деревною шириною

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

Див. також

Примітки

  1. Courcelle, Engelfriet, Rozenberg, 1993.
  2. Wanke, 1994.
  3. Chlebíková, 1992.
  4. Courcelle, 1993.
  5. Courcelle, Olariu, 2000.
  6. Golumbic, Rotics, 2000.
  7. Brandstädt, Lozin, 2003.
  8. Brandstädt, Dragan, Le, Mosca, 2005.
  9. Brandstädt, Engelfriet, Le, Lozin, 2006.
  10. Brandstädt, Hundt, 2008.
  11. Gurski, Wanke, 2009.
  12. Corneil, Rotics, 2005.
  13. Courcelle, Olariu, 2000, с. Corollary 3.3.
  14. Courcelle, Olariu, 2000, с. Theorem 4.1.
  15. Corneil, Rotics, 2005, Усиление — Courcelle, Olariu, 2000, Theorem 5.5.
  16. Gurski, Wanke, 2000.
  17. Oum, Seymour, 2006.
  18. Todinca, 2003.
  19. Cogis, Thierry, 2005.
  20. Courcelle, Makowsky, Rotics, 2000.
  21. Fomin, Golovach, Lokshtanov, Saurabh, 2010.
  22. Corneil at al, 2012.
  23. Fellows, Rosamond, Rotics, Szeider, 2009.
  24. Hliněný, Oum, 2008.
  25. Oum, 2009.
  26. Gurski, Wanke, 2007.

Література

  • Andreas Brandstädt, F.F. Dragan, H.-O. Le, R. Mosca. New graph classes of bounded clique-width // Theory of Computing Systems. — 2005. — Т. 38 (17 червня). — С. 623–645. — DOI:10.1007/s00224-004-1154-6.
  • Andreas Brandstädt, J. Engelfriet, H.-O. Le, V.V. Lozin. Clique-width for 4-vertex forbidden subgraphs // Theory of Computing Systems. — 2006. — Т. 39 (17 червня). — С. 561–590. — DOI:10.1007/s00224-005-1199-1.
  • Andreas Brandstädt, Christian Hundt. LATIN 2008: Theoretical informatics. — Springer, Berlin, 2008. — Т. 4957. — С. 479–491. — (Lecture Notes in Comput. Sci.) — DOI:10.1007/978-3-540-78773-0_42.
  • Andreas Brandstädt, V.V. Lozin. On the linear structure and clique-width of bipartite permutation graphs // . — 2003. — Т. 67 (17 червня). — С. 273–281.
  • J. Chlebíková. On the tree-width of a graph // Acta Mathematica Universitatis Comenianae. — 1992. — Т. 61, вип. 2 (17 червня). — С. 225–236. — (New Series).
  • 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.
  • Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce Reed, Udi Rotics. Polynomial-time recognition of clique-width ≤ 3 graphs // . — 2012. — Т. 160, вип. 6 (17 червня). — С. 834–865. — DOI:10.1016/j.dam.2011.03.020..
  • Derek G. Corneil, Udi Rotics. On the relationship between clique-width and treewidth // . — 2005. — Т. 34, вип. 4 (17 червня). — С. 825–847. — DOI:10.1137/S0097539701385351.
  • Bruno Courcelle, Joost Engelfriet, Grzegorz Rozenberg. Handle-rewriting hypergraph grammars // Journal of Computer and System Sciences. — 1993. — Т. 46, вип. 2 (17 червня). — С. 218–270. — DOI:10.1016/0022-0000(93)90004-G.
  • B. Courcelle. Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93). — 1993. — С. 179–190. — DOI:10.1109/LICS.1993.287589.
  • B. Courcelle, J. A. Makowsky, 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.
  • B. Courcelle, S. Olariu. Upper bounds to the clique width of graphs // . — 2000. — Т. 101, вип. 1–3 (17 червня). — С. 77–144. — DOI:10.1016/S0166-218X(99)00184-5.
  • Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider. Clique-width is NP-complete // SIAM Journal on Discrete Mathematics. — 2009. — Т. 23, вип. 2 (17 червня). — С. 909–939. — DOI:10.1137/070687256.
  • Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh. Intractability of clique-width parameterizations // . — 2010. — Т. 39, вип. 5 (17 червня). — С. 1941–1956. — DOI:10.1137/080742270..
  • 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.
  • Frank Gurski, Egon Wanke. Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Germany, June 15–17, 2000, Proceedings / Ulrik Brandes, Dorothea Wagner. — Berlin : Springer, 2000. — Т. 1928. — С. 196–205. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-40064-8_19.
  • Frank Gurski, Egon Wanke. Line graphs of bounded clique-width // . — 2007. — Т. 307, вип. 22 (17 червня). — С. 2734–2754. — DOI:10.1016/j.disc.2007.01.020.
  • Frank Gurski, Egon Wanke. The NLC-width and clique-width for powers of graphs of bounded tree-width // . — 2009. — Т. 157, вип. 4 (17 червня). — С. 583–595. — DOI:10.1016/j.dam.2008.08.031.
  • Petr Hliněný, Sang-il Oum. Finding branch-decompositions and rank-decompositions // . — 2008. — Т. 38, вип. 3 (17 червня). — С. 1012–1032. — DOI:10.1137/070685920.
  • Sang-il Oum, . Approximating clique-width and branch-width // . — 2006. — Т. 96, вип. 4 (17 червня). — С. 514–528. — (Series B). — DOI:10.1016/j.jctb.2005.10.006.
  • Sang-il Oum. Approximating rank-width and clique-width quickly // . — 2009. — Т. 5, вип. 1 (17 червня). — С. Art. 10, 20. — DOI:10.1007/11604686_5.
  • Ioan Todinca. Graph-theoretic concepts in computer science. — Springer, Berlin, 2003. — Т. 2880. — С. 370–382. — (Lecture Notes in Comput. Sci.) — DOI:10.1007/978-3-540-39890-5_32.
  • Egon Wanke. k-NLC graphs and polynomial algorithms // . — 1994. — Т. 54, вип. 2—3 (17 червня). — С. 251–266. — DOI:10.1016/0166-218X(94)90026-4.

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

Дата публікації:
V teoriyi grafiv klikova shirina grafa G displaystyle G ce parametr yakij opisuye strukturnu skladnist grafa Parametr tisno pov yazanij z derevnoyu shirinoyu ale na vidminu vid derevnoyi shirini klikova shirina mozhe buti obmezhenoyu navit dlya shilnih grafiv Klikova shirina viznachayetsya yak minimalna kilkist mitok neobhidnih dlya pobudovi G displaystyle G za dopomogoyu takih 4 operacij Stvorennya novoyi vershini v z mitkoyu i operaciya i v Nezv yazne ob yednannya dvoh rozmichenih grafiv G i H operaciya G H displaystyle G oplus H Z yednannya rebrom kozhnoyi vershini z mitkoyu i z kozhnoyu vershinoyu z mitkoyu j operaciya h i j de i j displaystyle i neq j Perejmenuvannya mitki i na j operaciya r i j Pobudova distancijno uspadkovuvanogo grafa klikovoyi shirini 3 nezv yaznim ob yednannyam perejmenuvannyam vershin i ob yednannyam mitok Mitki vershin pokazano kolorami Do grafiv z obmezhenoyu klikovoyu shirinoyu nalezhat kografi i distancijno uspadkovuvani grafi Hocha obchislennya klikovoyi shirini ye NP skladnoyu zadacheyu za umovi sho verhnya mezha ne vidoma i nevidomo chi mozhna yiyi obchisliti za polinomialnij chas koli verhnya mezha vidoma efektivni aproksimacijni algoritmi obchislennya klikovoyi shirini vidomi Spirayuchis na ci algoritmi i teoremu Kurselya bagato optimizacijnih zadach na grafah NP skladnih dlya dovilnih grafiv mozhna rozv yazati abo shvidko aproksimuvati dlya grafiv z obmezhenoyu klikovoyu shirinoyu Poslidovnosti pobudovi na yaki spirayetsya ponyattya klikovoyi shirini sformulyuvali Kursel Engelfrid i Rozenberg u 1990 i Vanke Nazvu klikova shirina vikoristala dlya inshoyi koncepciyi Hlyebikova Vid 1993 termin stav uzhivatisya v suchasnomu znachenni Osoblivi klasi grafivKografi ce tochno grafi z klikovoyu shirinoyu sho ne perevishuye dvoh Bud yakij distancijno uspadkovuvanij graf maye klikovu shirinu sho ne perevishuye 3 Odnak klikova shirina intervalnih grafiv ne obmezhena zgidno zi strukturoyu gratki Tak samo ne obmezhena klikova shirina dvochastkovih grafiv perestanovok zgidno z podibnoyu strukturoyu gratki Gruntuyuchis na opisi kografiv yak grafiv bez porodzhenih pidgrafiv izomorfnih shlyaham bez hord klasifikovano klikovu shirinu bagatoh klasiv grafiv viznachenih zaboronenimi porodzhenimi pidgrafami Inshi grafi z obmezhenoyu klikovoyu shirinoyu k en dlya obmezhenih znachen k tobto porodzheni pidgrafi listkiv dereva T u stepeni grafa Tk Odnak stepin listkiv za neobmezhenogo pokaznika stepenya ne maye obmezhenoyi shirini listkiv MezhiKursel i Olaru a takozh Kornejl i Rotiks dali taki mezhi klikovoyi shirini deyakih grafiv Yaksho graf maye klikovu shirinu maksimum k to te same istinne dlya bud yakogo porodzhenogo pidgrafa grafa Dopovnennya grafa z klikovoyu shirinoyu k maye klikovu shirinu sho ne perevishuye 2k Grafi z derevnoyu shirinoyu w mayut klikovu shirinu sho ne perevishuye 3 2w 1 Eksponencijna zalezhnist u mezhi neobhidna isnuyut grafi klikova shirina yakih eksponencijno bilsha vid yihnoyi derevnoyi shirini Z inshogo boku grafi z obmezhenoyu klikovoyu shirinoyu mozhut mati neobmezhenu derevnu shirinu Napriklad povni grafi z n vershinami mayut klikovu shirinu 2 ale derevnu shirinu n 1 Odnak grafi z klikovoyu shirinoyu k yaki ne mistyat povnogo dvochastkovogo grafa Kt t yak pidgrafa mayut derevnu shirinu sho ne perevishuye 3k t 1 1 Takim chinom dlya bud yakogo simejstva rozridzhenih grafiv nayavnist obmezhennya derevnoyi shirini ekvivalentne nayavnosti obmezhennya klikovoyi shirini Inshij parametr grafiv rangova shirina obmezhena v oboh napryamkah klikovoyu shirinoyu rangova shirina klikovoyi shirini 2rangovoyi shirini 1 Krim togo yaksho graf G maye klikovu shirinu k to stepin grafa Gc maye klikovu shirinu sho ne perevishuye 2kck Hocha v nerivnostyah dlya klikovoyi shirini v porivnyannyah z derevnoyu shirinoyu ta stepenem grafa prisutnya eksponenta ci mezhi ne dayut superpoziciyi yaksho graf G maye derevnu shirinu w to Gc maye klikovu shirinu sho ne perevershuye 2 c 1 w 1 2 lishe prosta eksponenta vid derevnoyi shirini Obchislyuvalna skladnistNerozv yazana problema matematiki Chi mozhna graf z obmezhenoyu klikovoyu shirinoyu rozpiznati za polinomialnij chas bilshe nerozv yazanih problem matematiki Bagato zadachi optimizaciyi NP skladni dlya bilsh zagalnih klasiv grafiv mozhna efektivno rozv yazati za dopomogoyu dinamichnogo programuvannya na grafah z obmezhenoyu klikovoyu shirinoyu yaksho poslidovnist pobudovi cih grafiv vidoma Zokrema bud yakij invariant grafa yakij mozhna viraziti v MSO1 en vid logiki drugogo poryadku sho dozvolyaye kvantori nad mnozhinami vershin maye algoritm linijnogo chasu dlya grafiv z obmezhenoyu shirinoyu za odnim iz formulyuvan teoremi Kurselya Mozhna takozh znajti optimalni rozmalovki abo gamiltonovi cikli grafiv z obmezhenoyu klikovoyu shirinoyu za polinomialnij chas yaksho poslidovnist pobudovi grafa vidoma ale stepin polinoma zbilshuyetsya zi zbilshennyam klikovoyi shirini i dovodi z teoriyi obchislyuvalnoyi skladnosti pokazuyut sho taka zalezhnist shozhe neminucha Grafi z klikovoyu shirinoyu tri mozhna rozpiznati i poslidovnist yih pobudovi mozhna znajti za polinomialnij chas za dopomogoyu algoritmu zasnovanogo na en Dlya klasiv grafiv z neobmezhenoyu klikovoyu shirinoyu tochne obchislennya klikovoyi shirini ye NP skladnoyu zadacheyu a takozh NP skladno otrimati aproksimaciyu z sublinijnoyu aditivnoyu pomilkoyu Odnak yaksho verhnya mezha klikovoyi shirini vidoma mozhna otrimati poslidovnist pobudovi grafa z obmezhenoyu shirinoyu eksponencialno bilshoyu vid spravzhnoyi klikovoyi shirini za polinomialnij chas Zalishayetsya vidkritim pitannya chi mozhna tochnu klikovu shirinu abo blizku aproksimaciyu obchisliti za en chas chi mozhna yiyi obchisliti za polinomialnij chas dlya grafiv z bud yakoyu fiksovanoyu mezheyu klikovoyi shirini abo navit chi mozhna grafi z klikovoyu shirinoyu chotiri rozpiznati za polinomialnij chas Zv yazok z derevnoyu shirinoyuTeoriya grafiv z obmezhenoyu klikovoyu shirinoyu podibna do teoriyi grafiv z obmezhenoyu derevnoyu shirinoyu ale na vidminu vid derevnoyi shirini dopuskaye shilni grafi Yaksho simejstvo grafiv maye obmezhenu klikovu shirinu to vono abo maye obmezhenu derevnu shirinu abo bud yakij povnij dvochastkovij graf ye pidgrafom yakogos grafa v simejstvi Derevna shirina i klikova shirina takozh pov yazani teoriyeyu rebernih grafiv rodina grafiv maye obmezhenu derevnu shirinu todi j lishe todi koli yihni reberni grafi mayut obmezhenu klikovu shirinu Div takozhDerevna shirina Shlyahova shirina grafaPrimitkiCourcelle Engelfriet Rozenberg 1993 Wanke 1994 Chlebikova 1992 Courcelle 1993 Courcelle Olariu 2000 Golumbic Rotics 2000 Brandstadt Lozin 2003 Brandstadt Dragan Le Mosca 2005 Brandstadt Engelfriet Le Lozin 2006 Brandstadt Hundt 2008 Gurski Wanke 2009 Corneil Rotics 2005 Courcelle Olariu 2000 s Corollary 3 3 Courcelle Olariu 2000 s Theorem 4 1 Corneil Rotics 2005 Usilenie Courcelle Olariu 2000 Theorem 5 5 Gurski Wanke 2000 Oum Seymour 2006 Todinca 2003 Cogis Thierry 2005 Courcelle Makowsky Rotics 2000 Fomin Golovach Lokshtanov Saurabh 2010 Corneil at al 2012 Fellows Rosamond Rotics Szeider 2009 Hlineny Oum 2008 Oum 2009 Gurski Wanke 2007 LiteraturaAndreas Brandstadt F F Dragan H O Le R Mosca New graph classes of bounded clique width Theory of Computing Systems 2005 T 38 17 chervnya S 623 645 DOI 10 1007 s00224 004 1154 6 Andreas Brandstadt J Engelfriet H O Le V V Lozin Clique width for 4 vertex forbidden subgraphs Theory of Computing Systems 2006 T 39 17 chervnya S 561 590 DOI 10 1007 s00224 005 1199 1 Andreas Brandstadt Christian Hundt LATIN 2008 Theoretical informatics Springer Berlin 2008 T 4957 S 479 491 Lecture Notes in Comput Sci DOI 10 1007 978 3 540 78773 0 42 Andreas Brandstadt V V Lozin On the linear structure and clique width of bipartite permutation graphs 2003 T 67 17 chervnya S 273 281 J Chlebikova On the tree width of a graph Acta Mathematica Universitatis Comenianae 1992 T 61 vip 2 17 chervnya S 225 236 New Series 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 Derek G Corneil Michel Habib Jean Marc Lanlignel Bruce Reed Udi Rotics Polynomial time recognition of clique width 3 graphs 2012 T 160 vip 6 17 chervnya S 834 865 DOI 10 1016 j dam 2011 03 020 Derek G Corneil Udi Rotics On the relationship between clique width and treewidth 2005 T 34 vip 4 17 chervnya S 825 847 DOI 10 1137 S0097539701385351 Bruno Courcelle Joost Engelfriet Grzegorz Rozenberg Handle rewriting hypergraph grammars Journal of Computer and System Sciences 1993 T 46 vip 2 17 chervnya S 218 270 DOI 10 1016 0022 0000 93 90004 G B Courcelle Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science LICS 93 1993 S 179 190 DOI 10 1109 LICS 1993 287589 B Courcelle J A Makowsky 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 B Courcelle S Olariu Upper bounds to the clique width of graphs 2000 T 101 vip 1 3 17 chervnya S 77 144 DOI 10 1016 S0166 218X 99 00184 5 Michael R Fellows Frances A Rosamond Udi Rotics Stefan Szeider Clique width is NP complete SIAM Journal on Discrete Mathematics 2009 T 23 vip 2 17 chervnya S 909 939 DOI 10 1137 070687256 Fedor V Fomin Petr A Golovach Daniel Lokshtanov Saket Saurabh Intractability of clique width parameterizations 2010 T 39 vip 5 17 chervnya S 1941 1956 DOI 10 1137 080742270 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 Frank Gurski Egon Wanke Graph Theoretic Concepts in Computer Science 26th International Workshop WG 2000 Konstanz Germany June 15 17 2000 Proceedings Ulrik Brandes Dorothea Wagner Berlin Springer 2000 T 1928 S 196 205 Lecture Notes in Computer Science DOI 10 1007 3 540 40064 8 19 Frank Gurski Egon Wanke Line graphs of bounded clique width 2007 T 307 vip 22 17 chervnya S 2734 2754 DOI 10 1016 j disc 2007 01 020 Frank Gurski Egon Wanke The NLC width and clique width for powers of graphs of bounded tree width 2009 T 157 vip 4 17 chervnya S 583 595 DOI 10 1016 j dam 2008 08 031 Petr Hlineny Sang il Oum Finding branch decompositions and rank decompositions 2008 T 38 vip 3 17 chervnya S 1012 1032 DOI 10 1137 070685920 Sang il Oum Approximating clique width and branch width 2006 T 96 vip 4 17 chervnya S 514 528 Series B DOI 10 1016 j jctb 2005 10 006 Sang il Oum Approximating rank width and clique width quickly 2009 T 5 vip 1 17 chervnya S Art 10 20 DOI 10 1007 11604686 5 Ioan Todinca Graph theoretic concepts in computer science Springer Berlin 2003 T 2880 S 370 382 Lecture Notes in Comput Sci DOI 10 1007 978 3 540 39890 5 32 Egon Wanke k NLC graphs and polynomial algorithms 1994 T 54 vip 2 3 17 chervnya S 251 266 DOI 10 1016 0166 218X 94 90026 4
Топ