En la teoría de grafos , el teorema del separador plano es una forma de desigualdad isoperimétrica para grafos planos , que establece que cualquier grafo plano se puede dividir en partes más pequeñas eliminando una pequeña cantidad de vértices. Específicamente, la eliminación de vértices de un -Gráfico de vértice (donde el invoca la notación O grande ) puede dividir el gráfico en subgráficos separados, cada uno de los cuales tiene como máximo vértices.
Una forma más débil del teorema del separador con vértices en el separador en lugar de fue probado originalmente por Ungar (1951) , y la forma con el límite asintótico apretado en el tamaño del separador fue probada por primera vez por Lipton y Tarjan (1979) . Desde su trabajo, el teorema del separador ha sido reprobado de varias formas diferentes, la constante en el Se ha mejorado el término del teorema y se ha ampliado a ciertas clases de gráficos no planos.
La aplicación repetida del teorema del separador produce una jerarquía de separadores que puede tomar la forma de una descomposición de árbol o una descomposición de ramas del gráfico. Las jerarquías de separadores se pueden usar para diseñar algoritmos eficientes de dividir y conquistar para gráficos planos, y la programación dinámica en estas jerarquías se puede usar para diseñar tiempo exponencial y algoritmos manejables de parámetros fijos para resolver problemas de optimización NP difíciles en estos gráficos. Las jerarquías de separadores también se pueden usar en la disección anidada , una variante eficiente de la eliminación gaussiana para resolver sistemas dispersos de ecuaciones lineales que surgen de métodos de elementos finitos .
Más allá de los gráficos planos, los teoremas del separador se han aplicado a otras clases de gráficos, incluidos los gráficos que excluyen un menor fijo , los gráficos vecinos más cercanos y las mallas de elementos finitos . La existencia de un teorema del separador para una clase de gráficos se puede formalizar y cuantificar mediante los conceptos de ancho de árbol y expansión polinomial .
Declaración del teorema
Como se suele afirmar, el teorema del separador establece que, en cualquier -Gráfico plano de vértice , existe una partición de los vértices de en tres conjuntos , , y , tal que cada uno de y tiene como máximo vértices posee vértices, y no hay bordes con un punto final en y un punto final en . No es necesario que o formar subgrafos conectados de. se llama el separador de esta partición.
Una formulación equivalente es que los bordes de cualquier -Gráfico plano de vértice puede subdividirse en dos subgrafos separados por bordes y de tal manera que ambos subgrafos tengan al menos vértices y tal que la intersección de los conjuntos de vértices de los dos subgráficos tiene vértices en él. Tal partición se conoce como separación . [1] Si se da una separación, entonces la intersección de los conjuntos de vértices forma un separador, y los vértices que pertenecen a un subgráfico pero no al otro forman subconjuntos separados que tienen cada uno como máximovértices. En la otra dirección, si a uno se le da una partición en tres conjuntos, , y que cumplen las condiciones del teorema del separador plano, entonces se puede formar una separación en la que las aristas con un punto final en pertenece a , los bordes con un punto final en pertenece a , y los bordes restantes (con ambos extremos en ) se dividen arbitrariamente.
El constante en el enunciado del teorema del separador es arbitrario y puede ser reemplazado por cualquier otro número en el intervalo abierto sin cambiar la forma del teorema: se puede obtener una partición en subconjuntos más iguales a partir de una partición menos pareja dividiendo repetidamente los conjuntos más grandes en la partición desigual y reagrupando los componentes conectados resultantes. [2]
Ejemplo
Considere un gráfico de cuadrícula con filas y columnas; el número de vértices es igual a . Por ejemplo, en la ilustración,, , y . Sies extraño, hay una sola fila central y, por lo demás, hay dos filas igualmente cerca del centro; de manera similar, sies extraño, hay una sola columna central y, por lo demás, hay dos columnas igualmente cerca del centro. Elegir para ser cualquiera de estas filas o columnas centrales, y eliminar del gráfico, divide el gráfico en dos subgráficos conectados más pequeños y , cada uno de los cuales tiene como máximo vértices. Si (como en la ilustración), luego elegir una columna central le dará un separador con vértices, y de manera similar si luego elegir una fila central dará un separador con como máximo vértices. Por lo tanto, cada gráfico de cuadrícula tiene un separador de tamaño como máximo , cuya eliminación lo divide en dos componentes conectados, cada uno de tamaño como máximo . [3]
El teorema del separador plano establece que se puede construir una partición similar en cualquier gráfico plano. El caso de los gráficos planos arbitrarios difiere del caso de los gráficos de cuadrícula en que el separador tiene un tamaño pero puede ser mayor que , el límite del tamaño de los dos subconjuntos y (en las versiones más comunes del teorema) es en vez de , y los dos subconjuntos y ellos mismos no necesitan formar subgrafos conectados.
Construcciones
Capas primero en anchura
Lipton y Tarjan (1979) aumentan el gráfico plano dado con bordes adicionales, si es necesario, de modo que se convierta en un plano máximo (cada cara en una incrustación plana es un triángulo). A continuación, realizan una búsqueda en amplitud , enraizada en un vértice arbitrario., y dividir los vértices en niveles por su distancia desde . Sies la mediana de nivel (el nivel de tal manera que el número de vértices en niveles superiores e inferiores están ambos en la mayor parte) entonces debe haber niveles y que son pasos arriba y abajo respectivamente y que contienen vértices, respectivamente, porque de lo contrario habría más de vértices en los niveles cercanos . Muestran que debe haber un separador formado por la unión de y , los extremos de un borde de que no pertenece al árbol de búsqueda de primer ancho y que se encuentra entre los dos niveles, y los vértices de las dos rutas del árbol de búsqueda de primer ancho desde los puntos finales de volver al nivel . El tamaño del separador construido de esta manera es a lo sumo . Los vértices del separador y los dos subgrafos separados se pueden encontrar en tiempo lineal . [4]
Esta prueba del teorema del separador se aplica también a las gráficas planas ponderadas, en las que cada vértice tiene un costo no negativo. El gráfico se puede dividir en tres conjuntos, , y tal que y cada uno tiene como máximo del costo total y posee vértices, sin aristas desde y . [4] Al analizar una construcción de separador similar más detenidamente, Djidjev (1982) muestra que el límite en el tamaño de se puede reducir a . [2]
Holzer y col. (2009) sugieren una versión simplificada de este enfoque: aumentan el gráfico para que sea plano máximo y construyen un primer árbol de búsqueda de amplitud como antes. Entonces, para cada borde que no es parte del árbol, forman un ciclo al combinar con la ruta del árbol que conecta sus puntos finales. Luego usan como separador los vértices de uno de estos ciclos. Aunque no se puede garantizar que este enfoque encuentre un pequeño separador para gráficos planos de gran diámetro, sus experimentos indican que supera a los métodos de estratificación de primera amplitud de Lipton-Tarjan y Djidjev en muchos tipos de gráficos planos. [5]
Separadores de ciclo simple
Para un gráfico que ya es plano máximo, es posible mostrar una construcción más fuerte de un separador de ciclo simple , un ciclo de pequeña longitud tal que el interior y el exterior del ciclo (en la incrustación plana única del gráfico) cada uno tiene en la mayoríavértices. Miller (1986) prueba esto (con un tamaño de separador de) utilizando la técnica de Lipton-Tarjan para una versión modificada de la primera búsqueda en amplitud en la que los niveles de la búsqueda forman ciclos simples. [6]
Alon, Seymour y Thomas (1994) prueban la existencia de separadores de ciclos simples de forma más directa: permiten ser un ciclo de como mucho vértices, con como máximo vértices afuera , que forma una partición lo más uniforme posible del interior y el exterior, y muestran que estos supuestos obligan a ser un separador. De lo contrario, las distancias dentro debe ser igual a las distancias en el disco encerrado por (una ruta más corta a través del interior del disco formaría parte del límite de un ciclo mejor). Adicionalmente, debe tener una longitud exacta , ya que de lo contrario podría mejorarse reemplazando uno de sus bordes por los otros dos lados de un triángulo. Si los vértices en están numerados (en el sentido de las agujas del reloj) desde a y vértice coincide con el vértice , estos pares emparejados se pueden conectar por caminos disjuntos de vértice dentro del disco, mediante una forma del teorema de Menger para gráficos planos. Sin embargo, la longitud total de estos caminos necesariamente excedería, una contradicción. Con un poco de trabajo adicional, muestran por un método similar que existe un separador de ciclo simple de tamaño como máximo. [7]
Djidjev y Venkatesan (1997) mejoraron aún más el factor constante en el teorema del separador de ciclo simple para. Su método también puede encontrar separadores de ciclo simples para gráficos con pesos de vértice no negativos, con un tamaño de separador como máximo, y puede generar separadores con un tamaño más pequeño a expensas de una partición más desigual del gráfico. [8] En biconexas grafos planos que no son máxima, existen separadores de ciclo simple con un tamaño proporcional a la norma euclidiana del vector de longitudes de cara que se pueden encontrar en tiempo casi lineal. [9]
Separadores de círculos
De acuerdo con el teorema de empaquetamiento de círculos de Koebe-Andreev-Thurston , cualquier grafo plano puede representarse mediante un empaque de discos circulares en el plano con interiores disjuntos, de modo que dos vértices en el grafo sean adyacentes si y solo si el par de discos correspondiente son mutuamente tangentes. Como Miller et al. (1997) muestran, para tal empaque, existe un círculo que tiene como máximo discos tocando o dentro de él, como máximo discos tocando o fuera de ella, y que cruza discos. [10]
Para probar esto, Miller et al. utilice la proyección estereográfica para mapear el empaquetamiento en la superficie de una esfera unitaria en tres dimensiones. Al elegir la proyección con cuidado, el centro de la esfera se puede convertir en un punto central de los centros del disco en su superficie, de modo que cualquier plano que pase por el centro de la esfera lo divide en dos medios espacios que cada uno contiene o cruza como máximo.de los discos. Si un plano que pasa por el centro se elige uniformemente al azar, se cruzará un disco con probabilidad proporcional a su radio. Por lo tanto, el número esperado de discos que se cruzan es proporcional a la suma de los radios de los discos. Sin embargo, la suma de los cuadrados de los radios es proporcional al área total de los discos, que es como mucho el área de superficie total de la esfera unitaria, una constante. Un argumento que involucra la desigualdad de Jensen muestra que, cuando la suma de cuadrados de los números reales no negativos están delimitados por una constante, la suma de los números en sí es . Por lo tanto, el número esperado de discos cruzados por un plano aleatorio esy existe un avión que atraviesa como máximo esa cantidad de discos. Este plano se cruza con la esfera en un gran círculo , que se proyecta hacia abajo a un círculo en el plano con las propiedades deseadas. La Los discos atravesados por este círculo corresponden a los vértices de un separador gráfico plano que separa los vértices cuyos discos están dentro del círculo de los vértices cuyos discos están fuera del círculo, con como máximo vértices en cada uno de estos dos subconjuntos. [11]
Este método conduce a un algoritmo aleatorio que encuentra dicho separador en tiempo lineal , [10] y un algoritmo determinista menos práctico con el mismo límite de tiempo lineal. [12] Al analizar este algoritmo cuidadosamente utilizando límites conocidos en la densidad de empaquetamiento de empaquetaduras circulares , se puede demostrar que encuentra separadores de tamaño como máximo [13]
La proyección estereográfica en Miller et al. El argumento se puede evitar considerando el círculo más pequeño que contiene una fracción constante de los centros de los discos y luego expandiéndolo por una constante elegida uniformemente en el rango. Como en Miller et al., Los discos que cruzan el círculo expandido forman un separador válido y, como se esperaba, el separador tiene el tamaño correcto. Las constantes resultantes son algo peores. [15]
Partición espectral
Los métodos de agrupamiento espectral , en los que los vértices de un gráfico se agrupan por las coordenadas de los vectores propios de las matrices derivadas del gráfico, se han utilizado durante mucho tiempo como heurística para problemas de partición de gráficos para gráficos no planos. [16] Como muestran Spielman y Teng (2007) , la agrupación espectral también se puede utilizar para derivar una prueba alternativa para una forma debilitada del teorema del separador plano que se aplica a gráficos planos con grado acotado. En su método, los vértices de un gráfico plano dado se ordenan por las segundas coordenadas de los vectores propios de la matriz laplaciana del gráfico, y este orden de clasificación se divide en el punto que minimiza la proporción del número de aristas cortadas por la partición. al número de vértices en el lado más pequeño de la partición. Como muestran, cada grafo plano de grado acotado tiene una partición de este tipo en la que la razón es. Aunque esta partición puede no estar equilibrada, repetir la partición dentro del mayor de los dos lados y tomar la unión de los cortes formados en cada repetición eventualmente conducirá a una partición equilibrada conbordes. Los extremos de estos bordes forman un separador de tamaño. [17]
Separadores de bordes
Una variación del teorema del separador plano implica separadores de bordes, pequeños conjuntos de bordes que forman un corte entre dos subconjuntos y de los vértices del gráfico. Los dos conjuntos y cada uno debe tener un tamaño como máximo una fracción constante del número de vértices del gráfico (convencionalmente, ambos conjuntos tienen un tamaño como máximo ), y cada vértice del gráfico pertenece exactamente a uno de y . El separador consta de los bordes que tienen un punto final en y un punto final en . Los límites del tamaño de un separador de aristas implican el grado de los vértices, así como el número de vértices en el gráfico: los gráficos planos en los que un vértice tiene grado, incluidos los gráficos de rueda y los gráficos en estrella , no tienen un separador de aristas con un número sublineal de aristas, porque cualquier separador de aristas tendría que incluir todas las aristas que conectan el vértice de alto grado con los vértices del otro lado del corte. Sin embargo, cada gráfico plano con grado máximo tiene un separador de bordes de tamaño . [18]
Un separador de ciclo simple en el gráfico dual de un gráfico plano forma un separador de bordes en el gráfico original. [19] La aplicación del teorema del separador de ciclo simple de Gazit y Miller (1990) al gráfico dual de un gráfico plano dado fortalece la límite para el tamaño de un separador de aristas mostrando que cada grafo plano tiene un separador de aristas cuyo tamaño es proporcional a la norma euclidiana de su vector de grados de vértice.
Papadimitriou y Sideri (1996) describen un algoritmo de tiempo polinomial para encontrar el separador de bordes más pequeño que divide un gráfico en dos subgrafos de igual tamao, cuando es un subgrafo inducido de un gráfico de cuadrícula sin agujeros o con un número constante de agujeros. Sin embargo, conjeturan que el problema es NP-completo para gráficas planas arbitrarias, y muestran que la complejidad del problema es la misma para gráficas de cuadrícula con muchos huecos arbitrarios que para gráficas planas arbitrarias.
Límites inferiores
en un gráfico de cuadrícula, un conjunto de los puntos pueden incluir un subconjunto de como máximo puntos de la cuadrícula, donde el máximo se logra organizando en una línea diagonal cerca de una esquina de la cuadrícula. Por lo tanto, para formar un separador que separe al menos de los puntos de la cuadrícula restante, necesita ser al menos .
Allí existe -Gráficos planos de vértice (para valores arbitrariamente grandes de ) tal que, para cada separador que divide el gráfico restante en subgráficos de como máximo vértices tiene al menos . [2] La construcción implica aproximar una esfera por un poliedro convexo , reemplazar cada una de las caras del poliedro por una malla triangular y aplicar teoremas isoperimétricos para la superficie de la esfera.
Jerarquías de separadores
Los separadores se pueden combinar en una jerarquía de separadores de un gráfico plano, una descomposición recursiva en gráficos más pequeños. Una jerarquía de separadores puede estar representada por un árbol binario en el que el nodo raíz representa el propio gráfico dado, y los dos hijos de la raíz son las raíces de las jerarquías de separadores construidas recursivamente para los subgráficos inducidos formados a partir de los dos subconjuntos. y de un separador.
Una jerarquía de separadores de este tipo forma la base para una descomposición de árbol del gráfico dado, en el que el conjunto de vértices asociados con cada nodo del árbol es la unión de los separadores en la ruta desde ese nodo hasta la raíz del árbol. Dado que los tamaños de los gráficos disminuyen en un factor constante en cada nivel del árbol, los límites superiores de los tamaños de los separadores también disminuyen en un factor constante en cada nivel, por lo que los tamaños de los separadores en estas rutas se suman una serie geométrica para. Es decir, un separador formado de esta manera tiene un ancho, y se puede usar para mostrar que cada gráfico plano tiene un ancho de árbol .
Construir una jerarquía de separadores directamente, atravesando el árbol binario de arriba hacia abajo y aplicando un algoritmo de separador plano de tiempo lineal a cada uno de los subgrafos inducidos asociados con cada nodo del árbol binario, tomaría un total de hora. Sin embargo, es posible construir una jerarquía de separadores completa en tiempo lineal, usando el enfoque de capas de amplitud primero de Lipton-Tarjan y usando estructuras de datos apropiadas para realizar cada paso de partición en tiempo sublineal. [20]
Si uno forma un tipo de jerarquía relacionada basada en separaciones en lugar de separadores, en la que los dos hijos del nodo raíz son raíces de jerarquías construidas recursivamente para los dos subgrafos y de una separación del gráfico dado, entonces la estructura general forma una descomposición de ramas en lugar de una descomposición de árbol. El ancho de cualquier separación en esta descomposición está, nuevamente, delimitado por la suma de los tamaños de los separadores en una ruta desde cualquier nodo hasta la raíz de la jerarquía, por lo que cualquier rama-descomposición formada de esta manera tiene anchoy cualquier gráfico plano tiene ancho de rama . Aunque muchos otros problemas relacionados con la partición de gráficos son NP-completos , incluso para gráficos planos, es posible encontrar una descomposición de rama de ancho mínimo de un gráfico plano en tiempo polinomial. [21]
Aplicando métodos de Alon, Seymour y Thomas (1994) más directamente en la construcción de descomposiciones de ramas, Fomin y Thilikos (2006a) muestran que cada grafo plano tiene un ancho de rama como máximo., con la misma constante que la del teorema del separador de ciclo simple de Alon et al. Dado que el ancho de árbol de cualquier gráfico es como máximo su ancho de rama, esto también muestra que los gráficos planos tienen un ancho de árbol como máximo .
Otras clases de gráficos
Algunos gráficos dispersos no tienen separadores de tamaño sublineal: en un gráfico expansor , eliminar hasta una fracción constante de los vértices todavía deja solo un componente conectado. [22]
Posiblemente, el teorema del separador más antiguo conocido es el resultado de Jordan (1869) de que cualquier árbol puede dividirse en subárboles de como máximovértices cada uno por la eliminación de un solo vértice. [10] En particular, el vértice que minimiza el tamaño máximo del componente tiene esta propiedad, porque si no lo hiciera, su vecino en el subárbol grande único formaría una partición aún mejor. Al aplicar la misma técnica a la descomposición de un árbol de un gráfico arbitrario, es posible mostrar que cualquier gráfico tiene un separador de tamaño como máximo igual a su ancho de árbol .
Si un gráfico no es plano, pero puede incrustarse en una superficie de género , luego tiene un separador con vértices. Gilbert, Hutchinson y Tarjan (1984) prueban esto utilizando un enfoque similar al de Lipton y Tarjan (1979) . Agrupan los vértices del gráfico en niveles de amplitud primero y encuentran dos niveles cuya eliminación deja como máximo un componente grande que consta de una pequeña cantidad de niveles. Este componente restante se puede hacer plano mediante la eliminación de una serie de trayectorias de amplitud primero proporcionales al género, después de lo cual se puede aplicar el método de Lipton-Tarjan al gráfico plano restante. El resultado se deriva de un cuidadoso equilibrio entre el tamaño de los dos niveles eliminados y el número de niveles entre ellos. Si la incrustación del gráfico se proporciona como parte de la entrada, su separador se puede encontrar en tiempo lineal . Gráficos de género también tienen separadores de bordes de tamaño . [23]
Los gráficos de género acotado forman un ejemplo de una familia de gráficos cerrados bajo la operación de tomar menores , y los teoremas del separador también se aplican a familias arbitrarias de gráficos menores cerrados. En particular, si una familia de gráficos tiene un menor prohibido con vértices, entonces tiene un separador con vértices, y tal separador se puede encontrar en el tiempo para cualquier . [24]
El método del separador de círculos de Miller et al. (1997) generaliza a las gráficas de intersección de cualquier sistema de-bolas dimensionales con la propiedad de que cualquier punto del espacio está cubierto como máximo por algún número constante de bolas, a - gráficos del vecino más cercano endimensiones, [10] ya los gráficos que surgen de mallas de elementos finitos . [25] Los separadores de esferas construidos de esta manera dividen el gráfico de entrada en subgráficos de como máximovértices. El tamaño de los separadores para-plique gráficos de intersección de bolas y para -Gráficos de vecino más cercano es . [10]
Si una familia hereditaria de gráficos tiene un teorema del separador con separadores de tamaño, para algunos , entonces necesariamente tiene expansión polinomial , un polinomio ligado a la densidad de sus menores superficiales . Por el contrario, los gráficos con expansión de polinomios tienen teoremas del separador sublineal. [26]
Aplicaciones
Divide y vencerás algoritmos
Las descomposiciones de separadores pueden ser útiles para diseñar algoritmos eficientes de divide y vencerás para resolver problemas en gráficas planas. Como ejemplo, un problema que se puede resolver de esta manera es encontrar el ciclo más corto en un dígrafo plano ponderado. Esto puede resolverse mediante los siguientes pasos:
- Partición del gráfico dado en tres subconjuntos , , según el teorema del separador plano
- Busque de forma recursiva los ciclos más cortos en y
- Utilice el algoritmo de Dijkstra para encontrar, para cada vértice en , el ciclo más corto a través en .
- Devuelve el más corto de los ciclos encontrados en los pasos anteriores.
El tiempo de las dos llamadas recursivas a y en este algoritmo está dominado por el tiempo para realizar el llamadas al algoritmo de Dijkstra, por lo que este algoritmo encuentra el ciclo más corto en hora.
Un algoritmo más rápido para el mismo problema de ciclo más corto, funcionando a tiempo , fue dada por Wulff-Nilsen (2009) . Su algoritmo usa la misma estructura de dividir y conquistar basada en separadores, pero usa separadores de ciclo simples en lugar de separadores arbitrarios, de modo que los vértices depertenecen a una sola cara de los gráficos dentro y fuera del separador de ciclos. Luego reemplaza elllamadas separadas al algoritmo de Dijkstra con algoritmos más sofisticados para encontrar las rutas más cortas de todos los vértices en una sola cara de un gráfico plano y combinar las distancias de los dos subgráficos. Para gráficos planos ponderados pero no dirigidos, el ciclo más corto es equivalente al corte mínimo en el gráfico dual y se puede encontrar entiempo, [27] y el ciclo más corto en una gráfica plana no ponderada no dirigida (su circunferencia ) se puede encontrar en el tiempo. [28] (Sin embargo, el algoritmo más rápido para gráficos no ponderados no se basa en el teorema del separador).
Frederickson propuso otro algoritmo más rápido para las rutas más cortas de una sola fuente mediante la implementación del teorema del separador en gráficos planos. [29] Esta es una mejora del algoritmo de Dijkstra con búsqueda iterativa en un subconjunto cuidadosamente seleccionado de los vértices. Esta versión lleva tiempo en un -Gráfico de vértice. Los separadores se utilizan para encontrar una división de un gráfico, es decir, una partición del conjunto de bordes en dos o más subconjuntos, llamados regiones. Se dice que un nodo está contenido en una región si algún borde de la región incide sobre el nodo. Un nodo contenido en más de una región se denomina nodo límite de las regiones que lo contienen. El método utiliza la noción de-división de un -Gráfico de nodo que es una división de gráfico en regiones, cada una conteniendo nodos incluidos nodos limítrofes. Frederickson demostró que un-división se puede encontrar en tiempo mediante la aplicación recursiva del teorema del separador.
El esquema de su algoritmo para resolver el problema es el siguiente.
- Fase de preprocesamiento: Divida el gráfico en subconjuntos de vértices cuidadosamente seleccionados y determine las rutas más cortas entre todos los pares de vértices en estos subconjuntos, donde los vértices intermedios en esta ruta no están en el subconjunto. Esta fase requiere un gráfico plano ser transformado en sin vértice que tenga un grado mayor que tres. A partir de un corolario de la fórmula de Euler , el número de vértices en el gráfico resultante será, dónde es el número de vértices en . Esta fase también asegura las siguientes propiedades de un adecuado-división. Una adecuada-división de un gráfico plano es una -división tal que,
- cada vértice del límite está contenido en como máximo tres regiones, y
- cualquier región que no esté conectada consta de componentes conectados, todos los cuales comparten vértices de límites con exactamente el mismo conjunto de una o dos regiones conectadas.
- Fase de búsqueda:
- Empuje principal: encuentre las distancias más cortas desde la fuente hasta cada vértice en el subconjunto. Cuando un vértice en el subconjunto está cerrado, la distancia tentativa debe actualizarse para todos los vértices en el subconjunto tal que existe una ruta desde a .
- Mop-up: Determine las distancias más cortas a cada vértice restante.
Henzinger y col. extendió Frederickson-Técnica de división para el algoritmo de ruta más corta de fuente única en gráficos planos para longitudes de borde no negativas y propuso un algoritmo de tiempo lineal . [30] Su método generaliza la noción de Frederickson de divisiones de grafos de modo que ahora un-división de un -El gráfico de nodo es una división en regiones, cada una conteniendo nodos, cada uno con como máximo nodos limítrofes. Si una-La división se divide repetidamente en regiones más pequeñas, lo que se denomina división recursiva. Este algoritmo utiliza aproximadamente niveles de divisiones, donde denota la función de logaritmo iterado . La división recursiva está representada por un árbol enraizado cuyas hojas están etiquetadas por un borde distinto de. La raíz del árbol representa la región que consta de todos los, los hijos de la raíz representan las subregiones en las que se divide esa región, etc. Cada hoja (región atómica) representa una región que contiene exactamente un borde.
La disección anidada es una variación de división y conquista basada en separadores de la eliminación gaussiana para resolver sistemas simétricos dispersos de ecuaciones lineales con una estructura de gráfico plano, como los que surgen del método de elementos finitos . Implica encontrar un separador para el gráfico que describe el sistema de ecuaciones, eliminando recursivamente las variables en los dos subproblemas separados entre sí por el separador y luego eliminando las variables en el separador. [31] El relleno de este método (el número de coeficientes distintos de cero de la descomposición de Cholesky resultante de la matriz) es , [32] permitiendo que este método sea competitivo con métodos iterativos para los mismos problemas. [31]
Klein, Mozes y Weimann [33] dieron una-Tiempo, algoritmo de espacio lineal para encontrar las distancias de camino más cortas desde un vértice de origen a todos los demás vértices para un gráfico plano dirigido con longitudes de arco positivas y negativas que no contienen ciclos negativos. Su algoritmo utiliza separadores de gráficos planos para encontrar una curva de Jordan. que pasa por nodos (y sin arcos) de modo que entre y los nodos están encerrados por . Nodos a través de los cualeslos pases son nodos limítrofes . El gráfico original se divide en dos subgrafos y cortando la incrustación plana a lo largo y duplicar los nodos de los límites. Los nodos de límite en cada gráfico yace en el límite de una sola cara .
A continuación se ofrece una descripción general de su enfoque.
- Llamada recursiva: la primera etapa calcula recursivamente las distancias desde dentro de cada gráfico .
- Distancias a los límites entre partes: para cada gráfico calcular todas las distancias en entre los nodos limítrofes. Esto toma hora.
- Distancias de frontera entre partes de fuente única: una ruta más corta en pasa de un lado a otro entre y para calcular las distancias en de a todos los nodos limítrofes. Las iteraciones alternas utilizan las distancias de todos los límites en y . El número de iteraciones es, y el tiempo total para esta etapa es dónde es la función inversa de Ackermann .
- Distancias entre partes de una sola fuente: Las distancias calculadas en las etapas anteriores se utilizan, junto con un cálculo de Dijkstra dentro de una versión modificada de cada G i , para calcular las distancias en de a todos los nodos. Esta etapa lleva hora.
- Redistribución de distancias de una sola fuente: las distancias desde en se transforman en longitudes no negativas, y nuevamente se usa el algoritmo de Dijkstra para calcular distancias desde . Esta etapa requiere hora.
Una parte importante de este algoritmo es el uso de funciones de precio y longitudes reducidas. Para un gráfico dirigido con longitudes de arco , una función de precio es una función de los nodos de a los números reales . Por un arco, la longitud reducida con respecto a es . Una función de precio factible es una función de precio que induce longitudes reducidas no negativas en todos los arcos de. Es útil para transformar un problema de ruta más corta que involucra longitudes positivas y negativas en uno que involucra solo longitudes no negativas, que luego se puede resolver usando el algoritmo de Dijkstra.
El paradigma de dividir y conquistar basado en separadores también se ha utilizado para diseñar estructuras de datos para algoritmos de gráficos dinámicos [34] y ubicación de puntos , [35] algoritmos para triangulación de polígonos , [20] caminos más cortos , [36] y la construcción de gráficos de vecinos más cercanos. , [37] y algoritmos de aproximación para el conjunto máximo independiente de un gráfico plano. [35]
Solución exacta de problemas de optimización NP-hard
Mediante el uso de programación dinámica en la descomposición de un árbol o la descomposición de ramas de un gráfico plano, muchos problemas de optimización NP-hard pueden resolverse en tiempo exponencial en o . Por ejemplo, los límites de esta forma son conocidos por encontrar conjuntos máximos independientes , árboles de Steiner y ciclos hamiltonianos , y por resolver el problema del viajante en gráficas planas. [38] Se pueden usar métodos similares que involucran teoremas del separador para gráficas geométricas para resolver el problema del viajante de comercio euclidiano y los problemas de construcción del árbol de Steiner en límites de tiempo de la misma forma. [39]
Para problemas parametrizados que admiten una kernelización que conserva la planicidad y reduce el gráfico de entrada a un kernel de tamaño lineal en el parámetro de entrada, este enfoque se puede utilizar para diseñar algoritmos tratables de parámetros fijos cuyo tiempo de ejecución depende polinomialmente del tamaño del parámetro. gráfico de entrada y exponencialmente en, dónde es el parámetro del algoritmo. Por ejemplo, los límites de tiempo de esta forma son conocidos por encontrar coberturas de vértices y dominar conjuntos de tamaño. [40]
Algoritmos de aproximación
Lipton y Tarjan (1980) observaron que el teorema del separador puede usarse para obtener esquemas de aproximación de tiempo polinomial para problemas de optimización NP-hard en gráficas planas como encontrar el conjunto independiente máximo . Específicamente, al truncar una jerarquía de separadores en un nivel apropiado, se puede encontrar un separador de tamaño cuya eliminación divide el gráfico en subgráficos de tamaño como máximo , para cualquier constante . Según el teorema de los cuatro colores , existe un conjunto independiente de tamaño al menos, por lo que los nodos eliminados forman una fracción insignificante del conjunto independiente máximo, y los conjuntos independientes máximos en los subgráficos restantes se pueden encontrar de forma independiente en el tiempo exponencial en su tamaño. Combinando este enfoque con métodos posteriores de tiempo lineal para la construcción de jerarquías de separadores [20] y con la búsqueda de tablas para compartir el cálculo de conjuntos independientes entre subgráficos isomórficos , se puede construir conjuntos independientes de tamaño dentro de un factor dede óptimo, en tiempo lineal. Sin embargo, para proporciones de aproximación incluso más cercanas a uno que este factor, un enfoque posterior de Baker (1994) (basado en la descomposición de árboles pero no en separadores planos) proporciona mejores compensaciones de tiempo versus calidad de aproximación.
También se han utilizado esquemas de aproximación similares basados en separadores para aproximar otros problemas difíciles como la cobertura de vértices . [41] Arora y col. (1998) utilizan separadores de una manera diferente para aproximar el problema del viajante de comercio para la métrica de la ruta más corta en gráficas planas ponderadas; su algoritmo utiliza programación dinámica para encontrar el recorrido más corto que, en cada nivel de una jerarquía de separadores, cruza el separador un número limitado de veces, y muestran que a medida que aumenta el límite de cruce, los recorridos construidos de esta manera tienen longitudes que se aproximan al óptimo excursión.
Compresión gráfica
Los separadores se han utilizado como parte de algoritmos de compresión de datos para representar gráficos planos y otros gráficos separables utilizando una pequeña cantidad de bits. El principio básico de estos algoritmos es elegir un número y subdividir repetidamente el gráfico plano dado utilizando separadores en subgrafos de tamaño como máximo , con vértices en los separadores. Con una elección adecuada de(como mucho proporcional al logaritmo de) el número de no isomorfos Los subgrafos planos de vértice es significativamente menor que el número de subgrafos en la descomposición, por lo que el gráfico se puede comprimir construyendo una tabla de todos los subgrafos no isomórficos posibles y representando cada subgrafo en la descomposición del separador por su índice en la tabla. El resto del gráfico, formado por los vértices del separador, puede representarse explícitamente o utilizando una versión recursiva de la misma estructura de datos. Con este método, los gráficos planos y muchas familias más restringidas de gráficos se pueden codificar utilizando un número de bits que es información teóricamente óptima: si hay -Gráficos de vértice en la familia de gráficos que se van a representar, luego un gráfico individual en la familia se puede representar utilizando solo bits. [42] También es posible construir representaciones de este tipo en las que se puede probar la adyacencia entre vértices, determinar el grado de un vértice y listar vecinos de vértices en tiempo constante por consulta, aumentando la tabla de subgráficos con información tabular adicional. que representa las respuestas a las consultas. [43]
Gráficos universales
Un gráfico universal para una familia de gráficos es un gráfico que contiene todos los miembros de como subgrafos. Se pueden utilizar separadores para mostrar que-Las gráficas planas de vértice tienen gráficas universales con vértices y bordes. [44]
La construcción implica una forma reforzada del teorema del separador en el que el tamaño de los tres subconjuntos de vértices en el separador no depende de la estructura del gráfico: existe un número , cuya magnitud a lo sumo tiempos constantes , de modo que los vértices de cada -El gráfico plano de vértice se puede separar en subconjuntos , , y , sin bordes de a , con , y con . Esto puede demostrarse utilizando la forma habitual del teorema del separador repetidamente para dividir el gráfico hasta que todos los componentes de la partición se puedan organizar en dos subconjuntos de menos de vértices, y luego mover los vértices de estos subconjuntos al separador según sea necesario hasta que tenga el tamaño dado.
Una vez que se muestra un teorema del separador de este tipo, se puede usar para producir una jerarquía de separadores para -Gráficos planos de vértice que nuevamente no dependen de la estructura del gráfico: la descomposición del árbol formada a partir de esta jerarquía tiene ancho y se puede utilizar para cualquier gráfico plano. El conjunto de todos los pares de vértices en esta descomposición de árbol que pertenecen a un nodo común de la descomposición de árbol forma un gráfico trivialmente perfecto con vértices que contiene cada -Gráfico plano de vértice como un subgráfico. Una construcción similar muestra que las gráficas planas de grado acotado tienen gráficas universales conbordes, donde la constante oculta en la notación O depende del límite de grado. Cualquier gráfico universal para gráficos planos (o incluso para árboles de grado ilimitado) debe tenerbordes. [44]
Esperet, Joret & Morin (2020) anunciaron que el La construcción con separadores se puede mejorar, para .
Ver también
- Separador de vértices
- Separador geométrico
Notas
- ^ Alon, Seymour y Thomas (1990) .
- ↑ a b c Djidjev (1982) .
- ^ George (1973) . En lugar de usar una fila o columna de un gráfico de cuadrícula, George divide el gráfico en cuatro partes usando la unión de una fila y una columna como separador.
- ↑ a b Lipton y Tarjan (1979) .
- ^ Holzer y col. (2009) .
- ^ Miller (1986) .
- ^ Alon, Seymour y Thomas (1994) .
- ^ Djidjev y Venkatesan (1997) .
- ^ Gazit y Miller (1990) .
- ^ a b c d e Miller y col. (1997) .
- ^ Miller y col. (1997) ; Pach y Agarwal (1995)
- ^ Eppstein, Miller y Teng (1995) .
- ^ Spielman y Teng (1996) .
- ^ Gremban, Miller y Teng (1997) .
- ^ Har-Peled (2011) .
- ^ Donath y Hoffman (1972) ; Fiedler (1973) .
- ^ Spielman y Teng (2007) .
- ↑ Miller (1986) demostró este resultado para gráficos planos de dos conexiones, y Diks et al. (1993) lo extendió a todos los gráficos planares.
- ^ Miller (1986) ; Gazit y Miller (1990) .
- ↑ a b c Goodrich (1995) .
- ^ Seymour y Thomas (1994) .
- ^ Lipton y Tarjan (1979) ; Erdős, Graham y Szemerédi (1976) .
- ^ Sýkora y Vrt'o (1993) .
- ^ Kawarabayashi y Reed (2010) . Para trabajos anteriores sobre separadores en familias menores cerradas, ver Alon, Seymour & Thomas (1990) , Plotkin, Rao & Smith (1994) y Reed & Wood (2009) .
- ^ Miller y col. (1998) .
- ^ Dvořák y Norin (2016) .
- ^ Łącki y Sankowski (2011) .
- ^ Chang y Lu (2011) .
- ^ Frederickson (1987) .
- ^ Henzinger y col. (1997) .
- ↑ a b George (1973) .
- ^ Lipton, Rose y Tarjan (1979) ; Gilbert y Tarjan (1986) .
- ^ Klein, Mozes y Weimann (2010) .
- ^ Eppstein y col. (1996) ; Eppstein y col. (1998) .
- ↑ a b Lipton y Tarjan (1980) .
- ^ Klein y col. (1994) ; Tazari y Müller-Hannemann (2009) .
- ^ Frieze, Miller y Teng (1992) .
- ^ Berna (1990) ; Deĭneko, Klinz y Woeginger (2006) ; Dorn y col. (2005) ; Lipton y Tarjan (1980) .
- ^ Smith y Wormald (1998) .
- ^ Alber, Fernau y Niedermeier (2003) ; Fomin y Thilikos (2006b) .
- ^ Bar-Yehuda y Even (1982) ; Chiba, Nishizeki y Saito (1981) .
- ^ Él, Kao y Lu (2000) .
- ^ Blandford, Blelloch y Kash (2003) ; Blelloch y Farzan (2010) .
- ^ a b Babai y col. (1982) ; Bhatt y col. (1989) ; Chung (1990) .
Referencias
- Alber, Jochen; Fernau, Henning; Niedermeier, Rolf (2003), "Separadores de gráficos: una vista parametrizada", Journal of Computer and System Sciences , 67 (4): 808–832, doi : 10.1016 / S0022-0000 (03) 00072-2
- Alon, Noga ; Seymour, Paul ; Thomas, Robin (1990), "Un teorema del separador para gráficos no planos", Journal of the American Mathematical Society , 3 (4): 801–808, doi : 10.1090 / S0894-0347-1990-1065053-0
- Alon, Noga ; Seymour, Paul ; Thomas, Robin (1994), "Separadores planos", SIAM Journal on Discrete Mathematics , 7 (2): 184-193, doi : 10.1137 / S0895480191198768
- Arora, Sanjeev ; Grigni, Miguel Ángel; Karger, David; Klein, Philip; Woloszyn, Andrzej (1998), "Un esquema de aproximación de tiempo polinomial para TSP de grafos planos ponderados", Proc. Noveno Simposio ACM-SIAM sobre algoritmos discretos (SODA '98) , págs. 33–41
- Babai, L .; Chung, FRK ; Erdős, P .; Graham, RL ; Spencer, JH (1982), "Sobre gráficos que contienen todos los gráficos dispersos", en Rosa, Alexander; Sabidussi, Gert ; Turgeon, Jean (eds.), Teoría y práctica de la combinatoria: una colección de artículos en honor a Anton Kotzig con motivo de su sexagésimo cumpleaños (PDF) , Annals of Discrete Mathematics, 12 , págs. 21-26
- Baker, Brenda S. (1994), "Algoritmos de aproximación para problemas NP-completos en gráficas planas", Journal of the ACM , 41 (1): 153–180, doi : 10.1145 / 174644.174650
- Bar-Yehuda, R .; Incluso, S. (1982), "Sobre la aproximación de una cobertura de vértice para grafos planos", Proc. XIV Simposio ACM sobre Teoría de la Computación (STOC '82) , págs. 303–309, doi : 10.1145 / 800070.802205 , ISBN 0-89791-070-2
- Bern, Marshall (1990), "Algoritmos exactos más rápidos para árboles Steiner en redes planas", Networks , 20 (1): 109–120, doi : 10.1002 / net.3230200110
- Bhatt, Sandeep N .; Chung, Fan RK ; Leighton, FT ; Rosenberg, Arnold L. (1989), "Gráficos universales para árboles de grados acotados y gráficos planos" (PDF) , SIAM Journal on Discrete Mathematics , 2 (2): 145, doi : 10.1137 / 0402014
- Blandford, Daniel K .; Blelloch, Guy E .; Kash, Ian A. (2003), "Representaciones compactas de gráficos separables", Proc. XIV Simposio ACM-SIAM sobre algoritmos discretos (SODA '03) (PDF) , págs. 679–688
- Blelloch, Guy E .; Farzan, Arash (2010), "Representaciones sucintas de gráficos separables", en Amir, Amihood; Parida, Laxmi (eds.), Proc. 21er Simposio sobre Coincidencia Combinatoria de Patrones , Lecture Notes in Computer Science, 6129 , Springer-Verlag, págs. 138-150, Bibcode : 2010LNCS.6129..138B , CiteSeerX 10.1.1.307.6710 , doi : 10.1007 / 978-3-642 -13509-5_13 , ISBN 978-3-642-13508-8
- Chalermsook, Parinya; Fakcharoenphol, Jittat; Nanongkai, Danupon (2004), "Un algoritmo determinista de tiempo casi lineal para encontrar cortes mínimos en gráficos planares", Proc. 15º Simposio ACM – SIAM sobre algoritmos discretos (SODA'04) , págs. 828–829
- Chang, Hsien-Chih; Lu, Hsueh-I (2011), "Calculando la circunferencia de un gráfico plano en tiempo lineal", SIAM Journal on Computing , 42 (3): 1077–1094, arXiv : 1104.4892 , doi : 10.1137 / 110832033
- Chiba, Norishige; Nishizeki, Takao ; Saito, Nobuji (1981), "Aplicaciones del teorema del separador plano de Lipton y Tarjan" (PDF) , Journal of Information Processing , 4 (4): 203-207
- Chung, Fan RK (1990), "Teoremas del separador y sus aplicaciones", en Korte, Bernhard ; Lovász, László ; Prömel, Hans Jürgen; et al. (eds.), Paths, Flows, and VLSI-Layout , Algorithms and Combinatorics, 9 , Springer-Verlag, págs. 17–34 , ISBN 978-0-387-52685-0
- Deĭneko, Vladimir G .; Klinz, Bettina; Woeginger, Gerhard J. (2006), "Algoritmos exactos para el problema del ciclo hamiltoniano en gráficas planas", Cartas de investigación de operaciones , 34 (3): 269-274, doi : 10.1016 / j.orl.2005.04.013
- Diks, K .; Djidjev, HN; Sýkora, O .; Vrt'o, I. (1993), "Separadores de bordes de grafos planos y planos externos con aplicaciones", Journal of Algorithms , 14 (2): 258-279, doi : 10.1006 / jagm.1993.1013
- Djidjev, HN (1982), "On the problem of particioning planar graphs", SIAM Journal on Algebraic and Discrete Methods , 3 (2): 229-240, doi : 10.1137 / 0603022
- Djidjev, Hristo N .; Venkatesan, Shankar M. (1997), "Constantes reducidas para la separación de gráficos de ciclos simples", Acta Informatica , 34 (3): 231–243, doi : 10.1007 / s002360050082
- Donath, NOSOTROS; Hoffman, AJ (1972), "Algoritmos para la partición de gráficos y lógica informática basados en vectores propios de matrices de conexión", IBM Techn. Divulgación Bull. , 15 : 938–944, citado por Spielman & Teng (2007)
- Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L .; Fomin, Fedor V. (2005), "Algoritmos exactos eficientes en grafos planos: explotando descomposiciones de ramas cortadas por esferas", Proc. 13th European Symposium on Algorithms (ESA '05) , Lecture Notes in Computer Science, 3669 , Springer-Verlag, págs. 95–106, doi : 10.1007 / 11561071_11 , ISBN 978-3-540-29118-3
- Dvořák, Zdeněk; Norin, Sergey (2016), "Separadores fuertemente sublineales y expansión polinomial", SIAM Journal on Discrete Mathematics , 30 (2): 1095-1101, arXiv : 1504.04821 , doi : 10.1137 / 15M1017569 , MR 3504982
- Eppstein, David ; Galil, Zvi ; Italiano, Giuseppe F .; Spencer, Thomas H. (1996), "Esparsificación basada en separadores. I. Pruebas de planaridad y árboles de expansión mínima", Journal of Computer and System Sciences , 52 (1): 3-27, doi : 10.1006 / jcss.1996.0002
- Eppstein, David ; Galil, Zvi ; Italiano, Giuseppe F .; Spencer, Thomas H. (1998), "Esparsificación basada en separadores. II. Conectividad de vértices y bordes", SIAM Journal on Computing , 28 : 341, doi : 10.1137 / S0097539794269072
- Eppstein, David ; Miller, Gary L .; Teng, Shang-Hua (1995), "Un algoritmo de tiempo lineal determinista para separadores geométricos y sus aplicaciones" , Fundamenta Informaticae , 22 (4): 309–331, doi : 10.3233 / FI-1995-2241
- Erdős, Paul ; Graham, Ronald ; Szemerédi, Endre (1976), "En gráficos dispersos con caminos largos y densos", Computadoras y matemáticas con aplicaciones (PDF) , Oxford: Pergamon, págs. 365–369
- Esperet, Louis; Joret, Gwenaël; Morin, Pat (2020), Gráficos universales dispersos para planaridad , arXiv : 2010.05779
- Fiedler, Miroslav (1973), "Conectividad algebraica de gráficos", Checoslovaco Mathematical Journal , 23 (98): 298–305, doi : 10.21136 / CMJ.1973.101168 , hdl : 10338.dmlcz / 101168 , MR 0318007
- Fomin, Fedor V .; Thilikos, Dimitrios M. (2006a), "Nuevos límites superiores en la descomponibilidad de gráficos planos" (PDF) , Journal of Graph Theory , 51 (1): 53–81, doi : 10.1002 / jgt.20121
- Fomin, Fedor V .; Thilikos, Dimitrios M. (2006b), "Conjuntos dominantes en gráficos planos: ancho de rama y aceleración exponencial", SIAM Journal on Computing , 36 (2): 281, doi : 10.1137 / S0097539702419649
- Frederickson, Greg N. (1987), "Algoritmos rápidos para rutas más cortas en gráficos planos, con aplicaciones", SIAM Journal on Computing , 16 (6): 1004–1022, doi : 10.1137 / 0216064 , MR 0917037
- Frieze, Alan ; Miller, Gary L .; Teng, Shang-Hua (1992), "Divide y vencerás en paralelo basado en separadores en geometría computacional", Proc. 4to Simposio de ACM sobre arquitectura y algoritmos paralelos (SPAA '92) (PDF) , págs. 420–429, doi : 10.1145 / 140901.141934 , ISBN 0-89791-483-X
- Gazit, Hillel; Miller, Gary L. (1990), "Separadores planos y la norma euclidiana", Proc. Simposio internacional sobre algoritmos (SIGAL'90) (PDF) , Lecture Notes in Computer Science, 450 , Springer-Verlag, págs. 338–347, doi : 10.1007 / 3-540-52921-7_83 , ISBN 978-3-540-52921-7
- George, J. Alan (1973), "Disección anidada de una malla regular de elementos finitos", SIAM Journal on Numerical Analysis , 10 (2): 345–363, doi : 10.1137 / 0710032 , JSTOR 2156361
- Gilbert, John R .; Hutchinson, Joan P .; Tarjan, Robert E. (1984), "Un teorema del separador para gráficas de género acotado", Journal of Algorithms , 5 (3): 391–407, doi : 10.1016 / 0196-6774 (84) 90019-1 , hdl : 1813 / 6346
- Gilbert, John R .; Tarjan, Robert E. (1986), "El análisis de un algoritmo de disección anidado", Numerische Mathematik , 50 (4): 377–404, doi : 10.1007 / BF01396660
- Goodrich, Michael T. (1995), "Separadores planos y triangulación de polígonos paralelos", Journal of Computer and System Sciences , 51 (3): 374–389, doi : 10.1006 / jcss.1995.1076
- Gremban, Keith D .; Miller, Gary L .; Teng, Shang-Hua (1997), "Momentos de inercia y separadores de gráficos" (PDF) , Journal of Combinatorial Optimization , 1 (1): 79-104, doi : 10.1023 / A: 1009763020645
- Har-Peled, Sariel (2011), una prueba simple de la existencia de un separador planar , arXiv : 1105.0103 , bibcode : 2011arXiv1105.0103H
- Él, Xin; Kao, Ming-Yang; Lu, Hsueh-I (2000), "Una metodología general rápida para la codificación de gráficos de información teóricamente óptima", SIAM Journal on Computing , 30 (3): 838–846, arXiv : cs / 0101021 , doi : 10.1137 / S0097539799359117
- Henzinger, Monika R .; Klein, Philip; Rao, Satish; Subramanian, Sairam (1997), "Algoritmos de ruta más corta más rápida para gráficos planos", Journal of Computer and System Sciences , 55 (1, parte 1): 3–23, doi : 10.1006 / jcss.1997.1493 , MR 1473046
- Holzer, Martin; Schulz, Frank; Wagner, Dorothea ; Prasinos, Grigorios; Zaroliagis, Christos (2009), "Algoritmos de separadores planos de ingeniería" , Journal of Experimental Algorithmics , 14 : 1.5–1.31, doi : 10.1145 / 1498698.1571635
- Jordan, Camille (1869), "Sur les assemblages des lignes" , Journal für die reine und angewandte Mathematik , 70 : 185-190, citado por Miller et al. (1997)
- Kawarabayashi, Ken-Ichi ; Reed, Bruce (2010), "Un teorema del separador en clases cerradas menores", Proc. 51 ° Simposio anual del IEEE sobre fundamentos de la informática , doi : 10.1109 / FOCS.2010.22
- Klein, Philip N .; Mozes, Shay; Weimann, Oren (2010), "Rutas más cortas en gráficos planos dirigidos con longitudes negativas: un espacio lineal-algoritmo de tiempo ", ACM Transactions on Algorithms , 6 (2): Art. 30, 18, doi : 10.1145 / 1721837.1721846 , MR 2675697
- Klein, Philip; Rao, Satish; Rauch, Monika; Subramanian, Sairam (1994), "Algoritmos más rápidos de ruta más corta para gráficos planos", Proc. 26 ° Simposio ACM sobre Teoría de la Computación (STOC '94) , págs. 27–37, doi : 10.1145 / 195058.195092 , ISBN 0-89791-663-8
- Łącki, Jakub; Sankowski, Piotr (2011), "Min-cortes y ciclos más cortos en gráficos planares entime ", Proc. 19º Simposio Europeo Anual sobre Algoritmos , Lecture Notes in Computer Science, 6942 , Springer-Verlag, págs. 155-166, arXiv : 1104.4890 , doi : 10.1007 / 978-3-642-23719-5_14 , ISBN 978-3-642-23718-8
- Lipton, Richard J .; Rose, Donald J .; Tarjan, Robert E. (1979), "Disección anidada generalizada", SIAM Journal on Numerical Analysis , 16 (2): 346–358, doi : 10.1137 / 0716027 , JSTOR 2156840
- Lipton, Richard J .; Tarjan, Robert E. (1979), "Un teorema del separador para gráficas planas", SIAM Journal on Applied Mathematics , 36 (2): 177–189, doi : 10.1137 / 0136016
- Lipton, Richard J .; Tarjan, Robert E. (1980), "Aplicaciones de un teorema del separador plano", SIAM Journal on Computing , 9 (3): 615–627, doi : 10.1137 / 0209046
- Miller, Gary L. (1986), "Encontrar pequeños separadores de ciclo simple para gráficos planos de 2 conectados" (PDF) , Journal of Computer and System Sciences , 32 (3): 265-279, doi : 10.1016 / 0022-0000 ( 86) 90030-9
- Miller, Gary L .; Teng, Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1997), "Separadores para empaquetaduras de esferas y gráficos de vecinos más cercanos", Journal of the ACM , 44 (1): 1–29, doi : 10.1145 / 256292.256294
- Miller, Gary L .; Teng, Shang-Hua ; Thurston, William ; Vavasis, Stephen A. (1998), "Separadores geométricos para mallas de elementos finitos", SIAM Journal on Scientific Computing , 19 (2): 364–386, CiteSeerX 10.1.1.307.2357 , doi : 10.1137 / S1064827594262613
- Pach, János ; Agarwal, Pankaj K. (1995), "Teorema del separador de Lipton-Tarjan", Geometría combinatoria , John Wiley & Sons, págs. 99-102
- Papadimitriou, CH ; Sideri, M. (1996), "The bisection width of grid graphs", Theory of Computing Systems , 29 (2): 97-110, doi : 10.1007 / BF01305310
- Plotkin, Serge; Rao, Satish; Smith, Warren D. (1994), "Menores excluidos superficiales y descomposiciones gráficas mejoradas", Proc. 5to Simposio ACM-SIAM sobre algoritmos discretos (SODA '94) , págs. 462–470
- Reed, Bruce ; Wood, David R. (2009), "Un algoritmo de tiempo lineal para encontrar un separador en un gráfico excluyendo un menor", ACM Transactions on Algorithms , 5 (4): 1–16, doi : 10.1145 / 1597036.1597043
- Seymour, Paul D .; Thomas, Robin (1994), "Call routing and the ratcatcher", Combinatorica , 14 (2): 217–241, doi : 10.1007 / BF01215352
- Smith, Warren D .; Wormald, Nicholas C. (1998), "Teoremas y aplicaciones del separador geométrico", 39 ° Simposio anual sobre fundamentos de la informática (FOCS '98), 8-11 de noviembre de 1998, Palo Alto, California, EE . UU. , IEEE Computer Society, págs. .232–243, doi : 10.1109 / SFCS.1998.743449
- Spielman, Daniel A .; Teng, Shang-Hua (1996), "Empaquetaduras de disco y separadores planos", Proc. 12 ° Simposio ACM sobre geometría computacional (SCG '96) (PDF) , págs. 349–358, doi : 10.1145 / 237218.237404 , ISBN 0-89791-804-5
- Spielman, Daniel A .; Teng, Shang-Hua (2007), "La partición espectral funciona: gráficos planos y mallas de elementos finitos", Álgebra lineal y sus aplicaciones , 421 (2–3): 284–305, doi : 10.1016 / j.laa.2006.07.020
- Sýkora, Ondrej; Vrt'o, Imrich (1993), "Separadores de bordes para gráficos de géneros acotados con aplicaciones", Informática teórica , 112 (2): 419–429, doi : 10.1016 / 0304-3975 (93) 90031-N
- Tazari, Siamak; Müller-Hannemann, Matthias (2009), "Rutas más cortas en tiempo lineal en clases de gráficos menores cerrados, con una aplicación a la aproximación del árbol de Steiner", Matemáticas aplicadas discretas , 157 (4): 673–684, doi : 10.1016 / j. presa.2008.08.002
- Ungar, Peter (1951), "Un teorema sobre gráficas planas", Revista de la Sociedad Matemática de Londres , 1 (4): 256, doi : 10.1112 / jlms / s1-26.4.256
- Weimann, Oren; Yuster, Raphael (2010), "Calcular la circunferencia de un gráfico plano entime ", SIAM Journal on Discrete Mathematics , 24 (2): 609, CiteSeerX 10.1.1.156.5730 , doi : 10.1137 / 090767868
- Wulff-Nilsen, Christian (2009), Circunferencia de un dígrafo plano con pesos de borde reales entiempo , arXiv : 0908.0697 , código Bib : 2009arXiv0908.0697W