Částečný k-strom - Partial k-tree - Wikipedia

v teorie grafů, a částečný k-strom je typ grafu, definovaný buď jako podgraf a k-strom nebo jako graf s šířka stromu nejvícek. Mnoho NP-tvrdé kombinatorické problémy na grafech jsou řešitelné v polynomiálním čase, pokud jsou omezeny na částečné k-stromy, pro omezené hodnotyk.

Graf nezletilí

Zakázané nezletilé pro částečné 3-stromy

Pro jakoukoli pevnou konstantu k, dílčí k-stromy jsou uzavřeny za provozu nezletilí v grafu, a tedy tím, že Věta Robertson – Seymour, tuto rodinu lze charakterizovat z hlediska konečné množiny zakázané nezletilé. Dílčí 1-stromy jsou přesně ty lesy, a jejich jediný zakázaný nezletilý je trojúhelník. Pro dílčí 2-stromy je jediným zakázaným nezletilým symbol kompletní graf na čtyřech vrcholech. Počet zakázaných nezletilých se však zvyšuje pro větší hodnoty k. U částečných tří stromů existují čtyři zakázané nezletilé: úplný graf na pěti vrcholech, oktaedrický graf se šesti vrcholy, osmi vrcholy Wagnerův graf a pětiúhelníkový hranol s deseti vrcholy.[1]

Dynamické programování

Mnoho algoritmických problémů, které jsou NP-kompletní pro libovolné grafy lze řešit efektivně pro částečné k-stromy dynamické programování, za použití stromové rozklady těchto grafů.[2]

Související rodiny grafů

Pokud je rodina grafů ohraničená šířka stromu, pak se jedná o podrodinu částečné k-stromy, kde k je vázán na šířku stromu. Rodiny grafů s touto vlastností zahrnují kaktusové grafy, pseudolesy, sériově paralelní grafy, vnější rovinné grafy, Halinovy ​​grafy, a Apollonské sítě.[1] Například sériově paralelní grafy jsou podrodinou částečných 2 stromů a silněji je graf částečným 2 stromem právě tehdy, když každý z jeho vzájemně propojené komponenty je sériově paralelní.

The kontrolní grafy toku vznikající v sestavení z strukturované programy také mají omezenou šířku stromu, která umožňuje určité úkoly, jako je přidělení registru aby byly na nich prováděny efektivně.[3]

Poznámky

  1. ^ A b Bodlaender (1998).
  2. ^ Arnborg a Proskurowski (1989); Bern, Lawler & Wong (1987); Bodlaender (1988).
  3. ^ Thorup (1998).

Reference

  • Arnborg, S .; Proskurowski, A. (1989), „Algoritmy lineárního času pro NP-tvrdé problémy omezené na částečné k-stromy ", Diskrétní aplikovaná matematika, 23 (1): 11–24, doi:10.1016 / 0166-218X (89) 90031-0.
  • Bern, M. W .; Lawler, E. L.; Wong, A. L. (1987), „Lineární výpočet optimálních podgrafů rozložitelných grafů“, Journal of Algorithms, 8 (2): 216–235, doi:10.1016/0196-6774(87)90039-3.
  • Bodlaender, Hans L. (1988), „Dynamické programování na grafech s omezenou šířkou stromu“, Proc. 15. mezinárodní kolokvium o automatech, jazycích a programování, Přednášky v informatice, 317, Springer-Verlag, str. 105–118, doi:10.1007/3-540-19488-6_110, ISBN  978-3-540-19488-0.
  • Bodlaender, Hans L. (1998), „Částečně k-arboretum grafů s omezenou šířkou stromu ", Teoretická informatika, 209 (1–2): 1–45, doi:10.1016 / S0304-3975 (97) 00228-4, hdl:1874/18312.
  • Thorup, Mikkel (1998), „Všechny strukturované programy mají malou šířku stromu a dobrou alokaci registrů“, Informace a výpočet, 142 (2): 159–181, doi:10.1006 / inco.1997.2697.