Technika Brenda Baker

Technika Brendy Bakerové je metoda pro konstrukci přibližných polynomiálních časových schémat (PTAS) pro problémy na rovinných grafech . Metoda je pojmenována po Brendě Baker americké počítačové vědkyni , která o metodě informovala na konferenci v roce 1983 a publikovala článek v Journal of the ACM v roce 1994.

Myšlenkou techniky Brendy Bakerové je rozdělit graf na úrovně tak, aby bylo možné problém optimálně vyřešit na každé úrovni, poté jsou řešení na každé úrovni uspokojivým způsobem kombinována, což vede k realistickému řešení. Tato technika poskytla SSW pro následující problémy: problém isomorfního podgrafu , problém maximální nezávislé množiny , problém pokrytí vrcholů , minimální dominující množina , minimální množina dominující hrany a mnoho dalších.

Teorie dvojrozměrnosti Eric Demaine , Fedor Fomin, Mohammed Hadzhigaya a Dimitros Tilikos a její odnož zjednodušených rozkladů [1] [2] zobecňuje a významně rozšiřuje záběr techniky Brendy Bakerové na rozsáhlou množinu problémů na rovině grafy a obecněji ke grafům, které neobsahují určitou minoritní , jako jsou grafy s omezeným rodem, a také k dalším třídám grafů, které nejsou uzavřeny mollovými, jako jsou 1-rovinné grafy .

Příklad techniky

Příkladem, na kterém si ukážeme techniku Brendy Bakerové, je problém nalezení maxima vážené nezávislé množiny .

Algoritmus

NEZÁVISLÁ SADA( , , ) $G$ $w$ $\epsilon$

Vyberte libovolný vrchol Najděte úrovně prohledávání grafu nejprve na šířku s kořenem : _

r

k=1/\epsilon

G

r

{\pmod {k))

\{V_{0},V_{1},\ldots ,V_{k-1}\}

\ell =0,\ldots ,k-1

G_{1}^{\ell },G_{2}^{\ell },\ldots ,

G

{\displaystyle V_{\ell ))

i=1,2,\ldots

S_{i}^{\ell }

{\displaystyle G_{i}^{\ell ))

{\displaystyle S^{\ell }=\cup _{i}S_{i}^{\ell ))

S^{\ell ^{*}}

\{S^{0},S^{1},\ldots ,S^{k-1}\}

S^{\ell ^{*}}

Všimněte si, že výše uvedený algoritmus je přijatelný, protože každá množina je spojením disjunktních nezávislých množin. ${\displaystyle S^{\ell ))$

Dynamické programování

Dynamické programování se používá k výpočtu nezávislé sady maximálních vah pro každou . Tento problém dynamického programování funguje, protože každý graf je -outerplanar . Mnoho NP-úplných problémů lze vyřešit pomocí dynamického programování na -mimoplanárních grafech. ${\displaystyle G_{i}^{\ell ))$ ${\displaystyle G_{i}^{\ell ))$ $k$ $k$

Poznámky

↑ Demaine, Hajiaghayi, Kawarabayashi, 2005 .
↑ Demaine, Hajiaghayi, Kawarabayashi, 2011 .

Literatura

B. Baker. Aproximační algoritmy pro NP-úplné problémy na rovinných grafech // Journal of the ACM . - 1994. - T. 41 , no. 1 . — S. 153–180 . - doi : 10.1145/174644.174650 .
B. Baker. Aproximační algoritmy pro NP-úplné problémy na rovinných grafech // FOCS. - 1983. - T. 24 .
H. Bodlaender. Dynamické programování na grafech s omezenou šířkou stromu // ICALP. - 1988. - doi : 10.1007 / 3-540-19488-6_110 .
E. Demaine, M. Hajiaghayi, K. Kawarabayashi. Vedlejší teorie algoritmických grafů: Dekompozice, aproximace a barvení // FOCS. - 2005. - T. 46 . - doi : 10.1109/SFCS.2005.14 .
E. Demaine, M. Hajiaghayi, K. Kawarabayashi. Dekompozice kontrakce v grafech bez H-minor a algoritmických aplikacích // STOC. - 2011. - T. 43 . - doi : 10.1145/1993636.1993696 .
E. Demaine, M. Hajiaghayi, N. Nishimura, P. Ragde, D. Thilikos. Aproximační algoritmy pro třídy grafů s výjimkou grafů s jedním křížením jako vedlejších. // J. Výpočet. Syst. Sci.. - 2004. - T. 69 . - doi : 10.1016/j.jcss.2003.12.001 .
D. Eppstein. Průměr a šířka stromu v malých uzavřených rodinách grafů. // Algoritmus. - 2000. - T. 27 . - doi : 10.1007/s004530010020 . - arXiv : math/9907126v1 .
D. Eppstein. Izomorfismus podgrafů v rovinných grafech a související problémy. //SODA. - 1995. - T. 6 .
Alexander Grigoriev, Hans L. Bodlaender. Algoritmy pro vnořitelné grafy s několika kříženími na hraně // Algorithmica. - 2007. - T. 49 , no. 1 . — S. 1–11 . - doi : 10.1007/s00453-007-0010-x .