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( , , )

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

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.

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.

Poznámky

  1. Demaine, Hajiaghayi, Kawarabayashi, 2005 .
  2. Demaine, Hajiaghayi, Kawarabayashi, 2011 .

Literatura