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, hvorpå vi vil demonstrere Brenda Bakers teknik, er problemet med at finde maksimum af et vægtet uafhængigt sæt .
UAFHÆNGIGT SÆT( , , )
Vælg et vilkårligt toppunkt Find bredden - første søgeniveauer for grafen med rod :Bemærk, at ovenstående algoritme er plausibel, da hvert sæt er foreningen af usammenhængende uafhængige sæt.
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.