Técnica Brenda Baker

La técnica de Brenda Baker es un método para construir esquemas de tiempo polinomial aproximados (PTAS) para problemas en gráficos planos . El método lleva el nombre de Brenda Baker una científica informática estadounidense que informó sobre el método en una conferencia de 1983 y publicó un artículo en el Journal of the ACM en 1994.

La idea de la técnica de Brenda Baker es dividir el gráfico en niveles para que el problema se pueda resolver de manera óptima en cada nivel, luego las soluciones en cada nivel se combinan de manera satisfactoria, lo que da como resultado una solución realista. Esta técnica ha dado SSW para los siguientes problemas: el problema del subgrafo isomorfo , el problema del conjunto independiente máximo , el problema de la cobertura de vértices , el conjunto dominante mínimo , el conjunto dominante de borde mínimo y muchos otros.

La teoría de la bidimensionalidad Eric Demaine , Fedor Fomin, Mohammed Hadzhigaya y Dimitros Tilikos y su rama de descomposición simplificada [1] [2] generaliza y amplía significativamente el alcance de la técnica de Brenda Baker a un vasto conjunto de problemas en planos y, de manera más general, a los gráficos que no contienen un menor definido , como los gráficos con género limitado, así como a otras clases de gráficos que no son menores cerrados, como los gráficos de 1 plano .

Un ejemplo de la técnica

Un ejemplo sobre el que demostraremos la técnica de Brenda Baker es el problema de encontrar el máximo de un conjunto independiente ponderado .

Algoritmo

CONJUNTO INDEPENDIENTE( , , ) $GRAMO$ $w$ $\epsilon$

Elija un vértice arbitrario Encuentre los niveles de búsqueda primero en anchura para el gráfico con raíz :

r

k=1/\épsilon

GRAMO

r

{\ estilo de visualización {\ pmod {k))}

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

{\ estilo de visualización \ ell = 0, \ ldots, k-1}

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

GRAMO

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

Tenga en cuenta que el algoritmo anterior es plausible, ya que cada conjunto es la unión de conjuntos independientes disjuntos. ${\displaystyle S^{\ell ))$

Programación dinámica

La programación dinámica se utiliza para calcular un conjunto independiente de pesos máximos para cada uno . Este problema de programación dinámica funciona porque cada gráfico es -outerplanar . Muchos problemas NP-completos se pueden resolver mediante programación dinámica en gráficos planos exteriores. ${\displaystyle G_{i}^{\ell ))$ ${\displaystyle G_{i}^{\ell ))$ $k$ $k$

Notas

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

Literatura

B. Panadero. Algoritmos de aproximación para problemas NP-completos en grafos planos // Journal of the ACM . - 1994. - T. 41 , núm. 1 . — S. 153–180 . -doi : 10.1145/ 174644.174650 .
B. Panadero. Algoritmos de aproximación para problemas NP-completos en grafos planos // FOCS. - 1983. - T. 24 .
H. Bodlaender. Programación dinámica en grafos con ancho de árbol acotado // ICALP. - 1988. - doi : 10.1007 / 3-540-19488-6_110 .
E. Demaine, M. Hajiaghayi, K. Kawarabayashi. Teoría menor de grafos algorítmicos: Descomposición, aproximación y coloreado // FOCS. - 2005. - T. 46 . -doi : 10.1109/ SFCS.2005.14 .
E. Demaine, M. Hajiaghayi, K. Kawarabayashi. Descomposición de contracción en grafos libres de H-menor y aplicaciones algorítmicas // STOC. - 2011. - T. 43 . -doi : 10.1145/ 1993636.1993696 .
E. Demaine, M. Hajiaghayi, N. Nishimura, P. Ragde, D. Thilikos. Algoritmos de aproximación para clases de grafos excluyendo grafos de cruce simple como menores. // J. Cómputo. sist. Sci.. - 2004. - T. 69 . -doi : 10.1016/ j.jcss.2003.12.001 .
D.Eppstein. Diámetro y ancho de árbol en familias de grafos cerrados menores. // Algorítmica. - 2000. - T. 27 . -doi : 10.1007/ s004530010020 . -arXiv : matemáticas / 9907126v1 .
D.Eppstein. Isomorfismo de subgrafos en grafos planos y problemas relacionados. //SODA. - 1995. - T. 6 .
Alexander Grigoriev, Hans L. Bodlaender. Algoritmos para grafos embebibles con pocos cruces por arista // Algorithmica. - 2007. - T. 49 , núm. 1 . — P. 1–11 . -doi : 10.1007 / s00453-007-0010-x .