Teknik Brenda Baker

Brenda Baker-teknikken er en metode til at konstruere tilnærmede polynomielle tidsskemaer (PTAS) for problemer på plane grafer . Metoden er opkaldt efter Brenda Baker en amerikansk datalog, der rapporterede om metoden på en konference i 1983 og publicerede en artikel i Journal of the ACM i 1994.

Ideen med Brenda Bakers teknik er at bryde grafen op i niveauer, så problemet kan løses optimalt på hvert niveau, hvorefter løsningerne på hvert niveau kombineres på en tilfredsstillende måde, hvilket resulterer i en realistisk løsning. Denne teknik har givet SSW for følgende problemer: det isomorfe subgrafproblem , det maksimale uafhængige sætproblem , toppunktsdækningsproblemet , det minimale dominerende sæt , det minimale kantdominerende sæt og mange andre.

Teorien om todimensionalitet Eric Demaine , Fedor Fomin, Mohammed Hadzhigaya og Dimitros Tilikos og dens forenklede nedbrydninger [1] [2] generaliserer og udvider omfanget af Brenda Bakers teknik til et stort sæt problemer på plan grafer og mere generelt til grafer, der ikke indeholder en bestemt minor , såsom grafer med begrænset slægt, såvel som andre klasser af grafer, der ikke er mindre-lukkede, såsom 1-planære grafer .

Et eksempel på teknikken

Et eksempel, hvorpå vi vil demonstrere Brenda Bakers teknik, er problemet med at finde maksimum af et vægtet uafhængigt sæt .

Algoritme

UAFHÆNGIGT SÆT( , , ) $G$ $w$ $\epsilon$

Vælg et vilkårligt toppunkt Find bredden - første søgeniveauer for grafen med rod :

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

{\displaystyle 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 ^{*}}

Bemærk, at ovenstående algoritme er plausibel, da hvert sæt er foreningen af usammenhængende uafhængige sæt. ${\displaystyle S^{\ell ))$

Dynamisk programmering

Dynamisk programmering bruges til at beregne et uafhængigt sæt af maksimalvægte for hver . Dette dynamiske programmeringsproblem virker , fordi hver graf er -outerplanar . Mange NP-komplette problemer kan løses ved hjælp af dynamisk programmering på -ydreplanære grafer. ${\displaystyle G_{i}^{\ell ))$ ${\displaystyle G_{i}^{\ell ))$ $k$ $k$

Noter

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

Litteratur

B. Bager. Approksimationsalgoritmer for NP-komplette problemer på plane grafer // Journal of the ACM . - 1994. - T. 41 , no. 1 . — S. 153–180 . - doi : 10.1145/174644.174650 .
B. Bager. Approksimationsalgoritmer for NP-komplette problemer på plane grafer // FOCS. - 1983. - T. 24 .
H. Bodlaender. Dynamisk programmering på grafer med afgrænset træbredde // ICALP. - 1988. - doi : 10.1007 / 3-540-19488-6_110 .
E. Demaine, M. Hajiaghayi, K. Kawarabayashi. Algoritmisk graf mindre teori: Dekomponering, tilnærmelse og farvelægning // FOCS. - 2005. - T. 46 . - doi : 10.1109/SFCS.2005.14 .
E. Demaine, M. Hajiaghayi, K. Kawarabayashi. Sammentrækningsnedbrydning i H-mol-fri grafer og algoritmiske applikationer // STOC. - 2011. - T. 43 . - doi : 10.1145/1993636.1993696 .
E. Demaine, M. Hajiaghayi, N. Nishimura, P. Ragde, D. Thilikos. Approksimationsalgoritmer for klasser af grafer undtagen enkeltkrydsende grafer som mindreårige. // J. Comput. Syst. Sci.. - 2004. - T. 69 . - doi : 10.1016/j.jcss.2003.12.001 .
D. Eppstein. Diameter og træbredde i mindre lukkede graffamilier. // Algoritmik. - 2000. - T. 27 . - doi : 10.1007/s004530010020 . - arXiv : math/9907126v1 .
D. Eppstein. Undergrafisomorfi i plane grafer og relaterede problemer. //SODA. - 1995. - T. 6 .
Alexander Grigoriev, Hans L. Bodlaender. Algoritmer til grafer, der kan integreres med få krydsninger pr. kant // Algoritmisk. - 2007. - T. 49 , no. 1 . — S. 1–11 . - doi : 10.1007/s00453-007-0010-x .