Часткове k-дерево

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

Мінори графів

Заборонені мінори для часткових 3-дерев

Для будь-якої фіксованої константи k часткові k дерева замкнуті щодо операції взяття мінорів графів, тому за теоремою Робертсона — Сеймура, таке сімейство графів можна описати скінченним набором заборонених мінорів. Часткові 1-дерева — це точно ліси і їх єдиним забороненим мінором є трикутник. Для часткових 2-дерев єдиним забороненим мінором є повний граф з чотирма вершинами. Однак при зростанні значення k далі кількість заборонених мінорів зростає. Для часткових 3-дерев є чотири заборонені мінори — повний граф з п'ятьма вершинами, октаедральний граф із шістьма вершинами, граф Вагнера з вісьмома вершинами і граф п'ятикутної призми з десятьма вершинами[1].

Динамічне програмування

Докладніше: Динамічне програмування

Багато алгоритмічних задач, NP-повних для довільних графів, можна ефективно розв'язати для часткових k-дерев за допомогою динамічного програмування, якщо використовувати деревну декомпозицію цих графів[2][3][4].

Пов'язані сімейства графів

Якщо сімейство графів має деревну ширину, обмежену числом k, воно є підсімейством часткових k-дерев. Сімейства графів із цією властивістю включають кактуси, псевдоліси, паралельно-послідовні графи, зовніпланарні графи, графи Халіна та графи Аполлонія[1]. Наприклад, паралельно-послідовні графи є підсімейством часткових 2-дерев. Строгіше, граф є частковим 2-деревом тоді й лише тоді, коли будь-який його шарнір є паралельно-послідовним.

Графи потоку керування, що виникають при трансляції структурованих програм також мають обмежену деревну ширину, що дозволяє ефективно виконувати деякі завдання, такі як розподіл регістрів[5].

Примітки

  1. ↑ а б Bodlaender, 1998.
  2. ↑ Arnborg, Proskurowski, 1989.
  3. ↑ Bern, Lawler, Wong, 1987.
  4. ↑ Bodlaender, 1988.
  5. ↑ Thorup, 1998.

Література

  • S. Arnborg, A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees // Discrete Applied Mathematics. — 1989. — Т. 23, вип. 1. — С. 11–24. — DOI:10.1016/0166-218X(89)90031-0.
  • M. W. Bern, E. L. Lawler, A. L. Wong. Linear-time computation of optimal subgraphs of decomposable graphs // Journal of Algorithms. — 1987. — Т. 8, вип. 2. — С. 216–235. — DOI:10.1016/0196-6774(87)90039-3..
  • Hans L. Bodlaender. Proc. 15th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1988. — Т. 317. — С. 105–118. — (Lecture Notes in Computer Science) — DOI:10.1007/3-540-19488-6_110.
  • Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вип. 1–2. — С. 1–45. — DOI:10.1016/S0304-3975(97)00228-4..
  • Mikkel Thorup. All structured programs have small tree width and good register allocation // Information and Computation. — 1998. — Т. 142, вип. 2. — С. 159–181. — DOI:10.1006/inco.1997.2697..

Read other articles:

Carl Jonas Love Almqvist

Carl Jonas Love AlmqvistNama dalam bahasa asli(sv) Carl Jonas Love Almqvist BiografiKelahiran28 November 1793 Adolf Fredriks parish (en) Kematian26 September 1866 (72 tahun)Bremen Tempat pemakamanSolna cemetery (en), SO 01 2 59°21′11″N 18°01′31″E / 59.35294°N 18.02518°E / 59.35294; 18.02518 Data pribadiAgamaGereja Lutheran PendidikanUniversitas Uppsala (1808–1815) KegiatanPekerjaanPenulis, komponis, penyair, wartawan, novelis, school teacher (en), pen...

 

Comité français de libération nationale

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Certaines informations figurant dans cet article ou cette section devraient être mieux reliées aux sources mentionnées dans les sections « Bibliographie », « Sources » ou « Liens externes » (novembre 2012). Vous pouvez améliorer la vérifiabilité en associant ces informations à des références à l'aide d'appels de notes. République françaiseComité français de libér...

 

Sekolah Enderun

Perpustakaan neo-klasik Enderun Sekolah Enderun (Turki Utsmaniyah: اندرون مکتب, Enderûn Mektebi) adalah sebuah sekolah istana dan sekolah dasar yang sebagian besar untuk millet Kristen di Kekaisaran Utsmaniyah, yang utamanya merekrut murid-murid melalui devşirme,[1] sebuah sistem Islamisasi anak-anak Kristen untuk bertugas pada pemerintahan Utsmaniyah dalam birokratik, manajerial, dan posisi militer Janisari.[2] Kurikulum Kurikulumnya terbagi dalam lima divisi utam...

B' Katīgoria 2009-2010

B' Katīgoria 2009-2010Β΄ κατηγορία Competizione B' Katīgoria Sport Calcio Edizione 55ª Organizzatore CFA Date dal 19 settembre 2009all'8 maggio 2010 Luogo  Cipro Partecipanti 14 Formula Girone all'italiana Risultati Vincitore  Alkī Larnaca Promozioni  Olympiakos Nicosia AEK Larnaca Alkī Larnaca Retrocessioni  Agia Napa Frenaros FC 2000 MEAP Nīsou Statistiche Incontri disputati 194 Gol segnati 464 (2,39 per incontro) Cronologia...

 

Calty Design Research

Toyota design studio Calty Design Research Office in Newport Beach, CA Calty Design Research Incorporated (also simply known as Calty) is a Toyota design studio established in 1973. They have two facilities: one in Newport Beach, California for concept designs, and another in Ann Arbor, Michigan for production designs. Calty provides both interior and exterior styling proposals for future Toyota vehicles[1] and advanced design, production color and wheel design concepts for Toyota's p...

 

Live Fast Motorsports

NASCAR team Live Fast MotorsportsOwner(s)B. J. McLeodJoe FalkPrincipal(s)Jessica McLeod (CEO)[1]BaseMooresville, North Carolina[2]SeriesNASCAR Cup SeriesRace drivers78. B. J. McLeod (part-time)Sponsors78. TBAManufacturerChevroletOpened2020CareerDebut2021 Daytona 500 (Daytona)Latest race2024 GEICO 500 (Talladega)Races competed110Drivers' Championships0Race victories0Pole positions0 Live Fast Motorsports is an American professional stock car racing team that currently competes p...

Pedro Munitis

Spanish footballer and manager In this Spanish name, the first or paternal surname is Munitis and the second or maternal family name is Álvarez. Pedro Munitis Munitis in 2013Personal informationFull name Pedro Munitis Álvarez[1]Date of birth (1975-06-19) 19 June 1975 (age 48)[1]Place of birth Santander, Spain[1]Height 1.70 m (5 ft 7 in)[1]Position(s) ForwardYouth career SantoñaSenior career*Years Team Apps (Gls)1992–1993 Santoñ...

 

コルク

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: コルク – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2017年4月） コルクを打ち抜いて作った瓶の栓 コルク（木栓、�...

 

Henry Zaga

Henry Zaga Henry Zaga, nome d'arte di Henrique Chagas Moniz de Aragão Gonzaga (Brasilia, 30 aprile 1993), è un attore brasiliano. Indice 1 Biografia 2 Filmografia 2.1 Cinema 2.2 Televisione 3 Note 4 Collegamenti esterni Biografia Zaga è nato a Brasilia, figlio di Sonia Gontijo e Admar Gonzaga. Suo padre è un discendente di italiani e portoghesi e sua madre è di origine spagnola e indigeni brasiliani. Ha ottenuto popolarità già all'inizio della sua carriera quando è stato scelto nel ru...

2020–21 Moldovan Cup

Football tournament season 2020–21 Moldovan CupThe Zimbru Stadium in Chișinău hosted the finalTournament detailsCountryMoldovaDates8 August 2020 – 30 May 2021Teams47Final positionsChampionsSfîntul GheorgheRunner-upSheriff TiraspolTournament statisticsMatches played45Goals scored188 (4.18 per match)← 2019–202021–22 → The 2020–21 Moldovan Cup (Romanian: Cupa Moldovei) was the 30th season of the annual Moldovan football cup competition. The compe...

 

Bangun Pagi

Bangun PagiStiker label singel Bangun PagiLagu oleh AdikarsoSisi-AFaridaFormatpelat 10GenrePop, lagu anak-anakDurasi3:00LabelIrama L. 566-136PenciptaAdikarso Bangun Pagi adalah sebuah lagu yang diciptakan dan dinyanyikan oleh Adikarso, diiringi orkes Kelana Ria. Di sisi-A dari singel ini terdapat lagu Farida yang juga dinyanyikan oleh Adikarso. Pada tahun 1960, lagu ini dirilis pada album kompilasi Papaja Mangga Pisang Djambu sebagai lagu kesembilan pada album tersebut. Pranala luar (Indonesi...

 

Арагонский язык

Арагонский язык Самоназвание aragonés [ˌa.ɾa.ɣɔ.ˈnes] Страны Испания Регионы Арагон Регулирующая организация Академия арагонского языка Общее число говорящих 42 000 Статус есть угроза исчезновения[1] Классификация Категория Языки Евразии Индоевропейская семья Романская гр...

Hong Xiuquan

Chinese revolutionary and leader of Taiping Rebellion (1814–1864) Not to be confused with Hung Hsiu-chu. In this Chinese name, the family name is Hong. Hong Xiuquan洪秀全Heavenly King of Great PeaceAlleged[a] drawing of Hong Xiuquan, dating from around early 1850s.Taiping Heavenly KingReign11 January 1851 – 1 June 1864PredecessorKingdom establishedSuccessorHong TianguifuBornHong Huoxiu (洪火秀)(1814-01-01)1 January 1814Hua County, Guangdong, Qing ChinaDied1 June 1864(1864-06...

 

Etruscan vase painting

A youth mounted on a dolphin and playing the flute; stamnos, circa 360/340 BC Etruscan vase painting was produced from the 7th through the 4th centuries BC, and is a major element in Etruscan art. It was strongly influenced by Greek vase painting, and followed the main trends in style over the period. Besides being producers in their own right, the Etruscans were the main export market for Greek pottery outside Greece, and some Greek painters probably moved to Etruria, where richly decorated ...

 

List of Maratha dynasties and states

This article possibly contains original research. Please improve it by verifying the claims made and adding inline citations. Statements consisting only of original research should be removed. (June 2023) (Learn how and when to remove this message) This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: List of Maratha dynasties and states –&#...

Janowiec (gmina)

Cet article est une ébauche concernant une localité polonaise. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Pour les articles homonymes, voir Janowiec. Gmina Janowiec Héraldique Drapeau Administration Pays Pologne Voïvodie(Région) Lublin Powiat(District) Puławy Siège Janowiec Plaque d'immatriculation LPU Démographie Population 3 594 hab. (2006) Densité 45 hab./km2 Géographie Coordonn�...

 

1998 Illinois Fighting Illini football team

American college football season 1998 Illinois Fighting Illini footballConferenceBig Ten ConferenceRecord3–8 (2–5 Big Ten)Head coachRon Turner (2nd season)Offensive coordinatorBuddy Teevens (2nd season)Defensive coordinatorTim Kish (2nd season)Home stadiumMemorial StadiumSeasons← 19971999 → 1998 Big Ten Conference football standings vte Conf Overall Team   W   L     W   L   No. 2 Ohio State %+   7 &#...

 

José Echegaray

Spanish statesman In this Spanish name, the first or paternal surname is Echegaray and the second or maternal family name is Eizaguirre. The Most ExcellentJosé EchegarayBornJosé Echegaray y Eizaguirre(1832-04-19)19 April 1832Madrid, SpainDied14 September 1916(1916-09-14) (aged 84)Madrid, SpainResting placeSaint Isidore CemeteryOccupationDramatist, civil engineer and mathematicianNationalitySpanishGenreDramaNotable awardsNobel Prize in Literature 1904 Seat e of the Real Academia...

StaySafe.ph

Software associated with the COVID-19 pandemic StaySafe.phOther namesStay SafeDeveloper(s)MultiSys TechnologiesInitial releaseSeptember 3, 2020; 3 years ago (2020-09-03)Stable release3.0.10 (Android) 3.0.2 (iOS) / June 23, 2021 (Android) July 2, 2021 (iOS) Operating systemAndroid, iOSSize7.1MB (Android)12.1 MB (iOS)Available inEnglishWebsitewww.staysafe.ph StaySafe.ph or Stay Safe is a digital contact tracing app launched by the Philippine government as a response to the COV...

 

Jean Lebeuf

Pour les articles homonymes, voir Lebeuf. Jean LebeufGravure de l’abbé Lebeuf des années 1760.BiographieNaissance 7 mars 1687AuxerreDécès 10 avril 1760 (à 73 ans)Formation Faculté de théologie catholique de ParisActivités Historien, prêtreAutres informationsMembre de Académie des inscriptions et belles-lettres (1741-1760)modifier - modifier le code - modifier Wikidata L'abbé Jean Lebeuf, né le 6 mars 1687 à Auxerre, mort le 10 avril 1760, est un prêtre, historien et éru...