ANCHO DE RUTA , CONTINUACIÓN I
Cálculo de descomposiciones de ruta [ editar ]
Está completo NP para determinar si el ancho de ruta de un gráfico dado es como máximo k , cuando k es una variable dada como parte de la entrada. [5] Los límites de tiempo más conocidos en el peor de los casos para calcular el ancho de ruta de los gráficos de n- vértices arbitrarios son de la forma O (2 n n c ) para alguna c constante . [33] Sin embargo, se conocen varios algoritmos para calcular las descomposiciones de ruta de manera más eficiente cuando el ancho de ruta es pequeño, cuando la clase de gráficos de entrada es limitada, o aproximadamente.
Trazabilidad de parámetros fijos [ editar ]
El ancho de ruta es manejable con parámetros fijos : para cualquier constante k , es posible probar si el ancho de ruta es como máximo k , y si es así, encontrar una descomposición de ruta de ancho k , en tiempo lineal. [7] En general, estos algoritmos operan en dos fases. En la primera fase, la suposición de que el gráfico tiene un ancho de ruta k se utiliza para encontrar una descomposición de ruta o descomposición de árbol que no es óptima, pero cuyo ancho puede limitarse en función de k . En la segunda fase, una programación dinámica.El algoritmo se aplica a esta descomposición para encontrar la descomposición óptima. Sin embargo, los límites de tiempo para algoritmos conocidos de este tipo son exponenciales en k 2 , poco prácticos excepto para los valores más pequeños de k . [34] Para el caso k = 2, de Fluiter (1997) proporciona un algoritmo explícito de tiempo lineal basado en una descomposición estructural de gráficos de ancho de ruta-2 .
Clases especiales de gráficos [ editar ]
Bodlaender (1994) analiza la complejidad de calcular el ancho de ruta en varias clases especiales de gráficos. Determinar si el ancho de ruta de un gráfico G es como máximo k permanece NP-completo cuando G está restringido a gráficos de grado acotado, [35] gráficos planos , [35] gráficos planos de grado acotado, [35] gráficos cordales , [36] dominó cordal, [37] los complementos de los gráficos de comparabilidad , [30] y gráficos bipartitos de distancia hereditaria . [38]Se deduce de inmediato que también es NP-completo para las familias de gráficos que contienen los gráficos hereditarios de distancia bipartitos, incluidos los gráficos bipartitos, los gráficos bipartitos cordales, los gráficos hereditarios de distancia y los gráficos circulares . [38]
Sin embargo, el ancho de ruta puede calcularse en tiempo lineal para árboles y bosques. [9] También se puede calcular en tiempo polinómico para gráficos de ancho de árbol acotado, incluidos gráficos de serie paralela , gráficos de plano exterior y gráficos de Halin , [7] así como para gráficos divididos , [39] para los complementos de gráficos cordales, [ 40] para gráficos de permutación , [29] para gráficos , [28] para gráficos de arco circular , [41] para los gráficos de comparabilidad de órdenes de intervalo, [31] y, por supuesto, paragráficos de intervalos en sí, ya que en ese caso el ancho de ruta es solo uno menos que el número máximo de intervalos que cubren cualquier punto en una representación de intervalo del gráfico.
Algoritmos de aproximación [ editar ]
Es NP-difícil aproximar el ancho de ruta de un gráfico a una constante aditiva. [6] La relación de aproximación más conocida de un algoritmo de aproximación de tiempo polinómico para el ancho de ruta es O ((log n ) 3/2 ). [42] Para algoritmos de aproximación anteriores para el ancho de ruta , ver Bodlaender et al. (1992) y Guha (2000) . Para aproximaciones sobre clases restringidas de gráficos, ver Kloks y Bodlaender (1992) .
Gráfico de menores [ editar ]
Un menor de un gráfico G es otro gráfico formado a partir de G al contraer bordes, eliminar bordes y eliminar vértices. Las gráficas menores tienen una teoría profunda en la cual varios resultados importantes involucran ancho de ruta.
Excluyendo un bosque [ editar ]
Si una familia F de gráficos se cierra al tomar menores (cada menor de un miembro de F también está en F ), entonces, según el teorema de Robertson-Seymour, F puede caracterizarse como los gráficos que no tienen ningún menor en X , donde X es un conjunto finito de menores prohibidos . [43] Por ejemplo, el teorema de Wagner establece que las gráficas planas son las gráficas que no tienen ni la gráfica completa K 5 ni la gráfica bipartita completa K 3,3 como menores. En muchos casos, las propiedades de Fy las propiedades de X están estrechamente relacionadas, y el primer resultado de este tipo fue de Robertson y Seymour (1983) , [2] y relaciona el ancho de camino limitado con la existencia de un bosque en la familia de menores prohibidos. Específicamente, defina una familia F de gráficos para tener un ancho de ruta limitado si existe una constante p tal que cada gráfico en F tenga un ancho de ruta como máximo p . Luego, una familia F cerrada menor tiene un ancho de ruta limitado si y solo si el conjunto X de menores prohibidos para F incluye al menos un bosque.
En una dirección, este resultado es fácil de probar: si X no incluye al menos un bosque, entonces los gráficos libres de X no tienen ancho de ruta limitado. Porque, en este caso, los gráficos sin X menor incluyen todos los bosques, y en particular incluyen los árboles binarios perfectos . Pero un árbol binario perfecto con 2 k + 1 niveles tiene ancho de ruta k , por lo que en este caso los gráficos X -menores libres tienen un ancho de ruta ilimitado. En la otra dirección, si X contiene un bosque n- vértice, entonces los gráficos libres de X -menor tienen ancho de ruta como máximo n - 2. [44]
Obstrucciones al ancho de ruta acotado [ editar ]
La propiedad de tener un ancho de ruta en la mayoría de las p es, en sí misma, cerrada al tomar menores: si G tiene una descomposición de ruta con un ancho en la mayoría de p , entonces la misma descomposición de ruta sigue siendo válida si se elimina cualquier borde de G , y cualquier vértice puede ser eliminado de G y de su descomposición de ruta sin aumentar el ancho. La contracción de un borde, también, se puede lograr sin aumentar el ancho de la descomposición, al fusionar las subrutas que representan los dos puntos finales del borde contraído. Por lo tanto, los gráficos de ancho de ruta en la mayoría de los p pueden caracterizarse por un conjunto X p de menores excluidos. [43] [45]
Aunque X p necesariamente incluye al menos un bosque, no es cierto que todos los gráficos en X p sean bosques: por ejemplo, X 1 consta de dos gráficos, un árbol de siete vértices y el triángulo K 3 . Sin embargo, el conjunto de árboles en X p puede caracterizarse con precisión: estos árboles son exactamente los árboles que se pueden formar a partir de tres árboles en X p - 1 conectando un nuevo vértice raíz por un borde a un vértice elegido arbitrariamente en cada uno de los Tres árboles más pequeños. Por ejemplo, el árbol de siete vértices en X 1 se forma de esta manera a partir del árbol de dos vértices (un solo borde) enX 0 . Según esta construcción, se puede demostrar que el número de menores prohibidos en X p es al menos ( p !) 2 . [45] Se ha calculado el conjunto completo X 2 de menores prohibidos para gráficos de ancho de ruta-2; Contiene 110 gráficos diferentes. [46]
Teoría de la estructura [ editar ]
El teorema de la estructura del gráfico para familias de gráficos cerrados menores establece que, para cualquiera de estas familias F , los gráficos en F se pueden descomponer en sumas clásicas de gráficos que se pueden incrustar en superficies de género acotado, junto con un número limitado de vértices y vórtices para cada componente de la suma de la camarilla. Un vértice es un vértice que puede estar adyacente a cualquier otro vértice en su componente, mientras que un vórtice es un gráfico de ancho de ruta acotado que está pegado en una de las caras del género incrustado de un componente. El orden cíclico de los vértices alrededor de la cara en la que está incrustado un vórtice debe ser compatible con la descomposición del camino del vórtice, en el sentido de que romper el ciclo para formar un orden lineal debe conducir a un orden con un número de separación de vértices acotado. [4] Esta teoría, en la cual el ancho de ruta está íntimamente conectado a familias arbitrarias de gráficos menores cerrados, tiene importantes aplicaciones algorítmicas. [47]
Aplicaciones [ editar ]
VLSI [ editar ]
En el diseño VLSI , el problema de separación de vértices se estudió originalmente como una forma de dividir los circuitos en subsistemas más pequeños, con una pequeña cantidad de componentes en el límite entre los subsistemas. [35]
Ohtsuki y col. (1979) usan el grosor de intervalo para modelar el número de pistas necesarias en un diseño unidimensional de un circuito VLSI, formado por un conjunto de módulos que necesitan ser interconectados por un sistema de redes. En su modelo, uno forma un gráfico en el que los vértices representan redes, y en el que dos vértices están conectados por un borde si sus redes se conectan al mismo módulo; es decir, si los módulos y las redes se interpretan como formando los nodos y las hiperestaciones de una hipergrafía, entonces el gráfico formado a partir de ellos es su gráfico lineal . Una representación de intervalo de una supergrafía de este gráfico lineal, junto con una coloraciónde la supergrafía, describe una disposición de las redes a lo largo de un sistema de pistas horizontales (una pista por color) de tal manera que los módulos se pueden colocar a lo largo de las pistas en un orden lineal y conectarse a las redes apropiadas. El hecho de que los gráficos de intervalo sean gráficos perfectos [48] implica que el número de colores necesarios, en una disposición óptima de este tipo, es el mismo que el número de camarilla de la finalización del intervalo del gráfico neto.
El diseño de matriz de puerta [49] es un estilo específico de diseño CMOS VLSI para circuitos lógicos booleanos . En los diseños de matriz de puerta, las señales se propagan a lo largo de "líneas" (segmentos de línea vertical) mientras que cada puerta del circuito está formada por una secuencia de características del dispositivo que se encuentran a lo largo de un segmento de línea horizontal. Por lo tanto, el segmento de línea horizontal para cada puerta debe cruzar los segmentos verticales para cada una de las líneas que forman entradas o salidas de la puerta. Como en los diseños de Ohtsuki et al. (1979) , se puede encontrar un diseño de este tipo que minimiza el número de pistas verticales en las que se organizarán las líneas calculando el ancho de ruta de un gráfico que tiene las líneas como sus vértices y pares de líneas que comparten una puerta como su bordes [50]El mismo enfoque algorítmico también se puede utilizar para modelar problemas de plegado en matrices lógicas programables . [51]
Dibujo gráfico [ editar ]
- Los gráficos mínimos que tienen un número de cruce dado tienen un ancho de ruta limitado por una función de su número de cruce. [52]
- El número de líneas paralelas en las que se pueden dibujar los vértices de un árbol sin cruces de bordes (bajo varias restricciones naturales sobre las formas en que se pueden colocar los vértices adyacentes con respecto a la secuencia de líneas) es proporcional al ancho del camino del árbol. [53]
- Un dibujo de la capa h que cruza k de un gráfico G es una colocación de los vértices de G en h líneas horizontales distintas, con bordes enrutados como caminos poligonales monótonos entre estas líneas, de tal manera que haya como máximo k cruces. Los gráficos con dichos dibujos tienen un ancho de ruta limitado por una función de h y k . Por lo tanto, cuando h y k son constantes, es posible en tiempo lineal determinar si un gráfico tiene un dibujo de capa h que cruza k . [54]
- Un gráfico con n vértices y ancho de ruta p se puede incrustar en una cuadrícula tridimensional de tamaño p × p × n de tal manera que no se crucen dos bordes (representados como segmentos de línea recta entre puntos de cuadrícula). Por lo tanto, los gráficos de ancho de ruta limitado tienen incorporaciones de este tipo con volumen lineal. [55]
Diseño del compilador [ editar ]
En la compilación de lenguajes de programación de alto nivel , el ancho de ruta surge en el problema de reordenar secuencias de código de línea recta (es decir, código sin ramas o bucles de flujo de control ) de tal manera que todos los valores calculados en el código puedan ser colocado en los registros de la máquina en lugar de tener que ser derramado en la memoria principal. En esta aplicación, uno representa el código que se compilará como un gráfico acíclico dirigido en el que los nodos representan los valores de entrada al código y los valores calculados por las operaciones dentro del código. Un borde del nodo x al nodo y en este DAG representa el hecho de que el valor xes una de las entradas a la operación y . Un orden topológico de los vértices de este DAG representa un reordenamiento válido del código, y el número de registros necesarios para evaluar el código en un orden dado viene dado por el número de separación de vértices del orden. [56]
Para cualquier número fijo w de registros de máquina, es posible determinar en tiempo lineal si un fragmento de código de línea recta puede reordenarse de tal manera que pueda evaluarse con la mayoría de los registros w . Porque, si el número de separación de vértices de un ordenamiento topológico es como máximo w , la separación mínima de vértices entre todos los ordenamientos no puede ser mayor, por lo que el gráfico no dirigido formado al ignorar las orientaciones del DAG descrito anteriormente debe tener una trayectoria como máximo w . Es posible probar si este es el caso, utilizando los algoritmos conocidos manejables de parámetros fijos para el ancho de ruta, y si es así para encontrar una descomposición de ruta para el gráfico no dirigido, en tiempo lineal dado el supuesto de que wEs una constante. Una vez que se ha encontrado una descomposición de ruta, se puede encontrar un orden topológico de ancho w (si existe) usando programación dinámica, nuevamente en tiempo lineal. [56]
Lingüística [ editar ]
Kornai y Tuza (1992) describen una aplicación de ancho de ruta en el procesamiento del lenguaje natural . En esta aplicación, las oraciones se modelan como gráficos, en los que los vértices representan palabras y los bordes representan relaciones entre palabras; por ejemplo, si un adjetivo modifica un sustantivo en la oración, entonces el gráfico tendría un borde entre esas dos palabras. Debido a la capacidad limitada de la memoria humana a corto plazo, [57] Kornai y Tuza argumentan que este gráfico debe tener un ancho de ruta limitado (más específicamente, argumentan, ancho de ruta como máximo seis), ya que de lo contrario los humanos no podrían analizar el habla correctamente .
Algoritmos exponenciales [ editar ]
Muchos problemas en los algoritmos de gráficos pueden resolverse eficientemente en gráficos de bajo ancho de ruta , mediante el uso de programación dinámica en una descomposición de ruta del gráfico. [10] Por ejemplo, si se da un orden lineal de los vértices de un gráfico de n -vértices G , con un número de separación de vértices w , entonces es posible encontrar el conjunto independiente máximo de G en el tiempo O (2 w n ). [32] En los gráficos de ancho de ruta limitado, este enfoque conduce a algoritmos manejables de parámetros fijos, parametrizados por el ancho de ruta. [50]Tales resultados no se encuentran con frecuencia en la literatura porque están subsumidos por algoritmos similares parametrizados por el ancho del árbol; sin embargo, el ancho de ruta surge incluso en algoritmos de programación dinámica basados en el ancho de árbol para medir la complejidad espacial de estos algoritmos. [11]
El mismo método de programación dinámica también se puede aplicar a gráficos con ancho de ruta ilimitado, lo que lleva a algoritmos que resuelven problemas de gráficos no parametrizados en tiempo exponencial . Por ejemplo, la combinación de este enfoque de programación dinámica con el hecho de que los gráficos cúbicos tienen ancho de ruta n / 6 + o ( n ) muestra que, en un gráfico cúbico, el conjunto independiente máximo se puede construir en el tiempo O (2 n / 6 + o ( n ) ), más rápido que los métodos conocidos anteriores. [32] Un enfoque similar conduce a algoritmos de tiempo exponencial mejorados para el corte máximo y los problemas de conjuntos dominantes mínimos en gráficos cúbicos, [32]y para varios otros problemas de optimización NP-hard.
No hay comentarios:
Publicar un comentario