Ancho de ruta

Representación de un gráfico como un gráfico de ruta "espesado" en cierta cantidad

En teoría de grafos , una descomposición de camino de un gráfico G es, informalmente, una representación de G como un gráfico de camino "engrosado" , [ ^1] y el ancho de camino de G es un número que mide cuánto se engrosó el camino para formar  G. Más formalmente, una descomposición de ruta es una secuencia de subconjuntos de vértices de G tal que los puntos finales de cada arista aparecen en uno de los subconjuntos y tal que cada vértice aparece en una subsecuencia contigua de los subconjuntos, ^[2] y el ancho de ruta es uno menos que el tamaño del conjunto más grande en tal descomposición. El ancho de ruta también se conoce como espesor de intervalo (uno menos que el tamaño máximo de camarilla en un supergrafo de intervalo de G ), número de separación de vértices o número de búsqueda de nodos . ^[3]

El ancho de ruta y las descomposiciones de ruta son muy análogos al ancho de árbol y las descomposiciones de árbol . Desempeñan un papel clave en la teoría de grafos menores : las familias de grafos que están cerradas bajo grafos menores y no incluyen todos los bosques pueden caracterizarse por tener un ancho de camino acotado, ^{[2] y los "vórtices" que aparecen en la} teoría de la estructura general. para familias de gráficos menores cerrados tienen un ancho de ruta limitado. ^[4] El ancho de ruta y los gráficos de ancho de ruta acotado también tienen aplicaciones en el diseño VLSI , dibujo de gráficos y lingüística computacional .

Es NP-difícil encontrar el ancho de ruta de gráficos arbitrarios, o incluso aproximarlo con precisión. ^{[5] [6]} Sin embargo, el problema es manejable con parámetros fijos : probar si un gráfico tiene un ancho de ruta k se puede resolver en una cantidad de tiempo que depende linealmente del tamaño del gráfico pero superexponencialmente de  k . ^[7] Además, para varias clases especiales de gráficos, como árboles , el ancho de ruta se puede calcular en tiempo polinómico sin depender de  k . ^{[8] [9]} Muchos problemas en algoritmos de gráficos se pueden resolver eficientemente en gráficos de ancho de ruta acotado, mediante el uso de programación dinámica en una descomposición de ruta del gráfico. ^[10] La descomposición de rutas también se puede utilizar para medir la complejidad espacial de algoritmos de programación dinámica en gráficos de ancho de árbol acotado . ^[11]

Definición

Un gráfico de ejemplo G con ancho de ruta 2 y su descomposición de ruta de ancho 2. La parte inferior de la imagen es el mismo gráfico y descomposición de ruta con color agregado para énfasis. (Este ejemplo es una adaptación del gráfico presentado en Bodlaender (1994a), énfasis añadido)

En el primero de su famosa serie de artículos sobre grafos menores , Neil Robertson y Paul Seymour  (1983) definen una descomposición de caminos de un grafo G como una secuencia de subconjuntos Xi _de vértices de G , con dos propiedades:

1. Para cada arista de G , existe una i tal que ambos puntos finales de la arista pertenecen al subconjunto Xi _, y
2. Por cada tres índices i ≤ j ≤ k , ${\displaystyle X_{i}\cap X_{k}\subseteq X_{j}.}$

La segunda de estas dos propiedades equivale a exigir que los subconjuntos que contienen cualquier vértice particular formen una subsecuencia contigua de la secuencia completa. En el lenguaje de los artículos posteriores en la serie menor de gráficos de Robertson y Seymour, una descomposición de ruta es una descomposición de árbol ( X , T ) en la que el árbol subyacente T de la descomposición es un gráfico de ruta .

El ancho de una descomposición de ruta se define de la misma manera que para las descomposiciones de árbol, como max _i | X _yo | − 1 , y el ancho de ruta de G es el ancho mínimo de cualquier descomposición de ruta de  G . La resta de uno del tamaño de X _i en esta definición hace poca diferencia en la mayoría de las aplicaciones de ancho de ruta, pero se utiliza para hacer que el ancho de ruta de un gráfico de ruta sea igual a uno.

Caracterizaciones alternativas

Como describe Bodlaender (1998), el ancho de ruta se puede caracterizar de muchas maneras equivalentes.

Secuencias de pegado

Una descomposición de caminos se puede describir como una secuencia de gráficos Gi que _se pegan identificando pares de vértices de gráficos consecutivos en la secuencia, de modo que el resultado de realizar todos estos pegados es G. Los gráficos G _i pueden tomarse como los subgrafos inducidos de los conjuntos X _i en la primera definición de descomposiciones de trayectorias, con dos vértices en subgrafos inducidos sucesivos pegados cuando son inducidos por el mismo vértice en G y en la otra dirección. se pueden recuperar los conjuntos X _i como conjuntos de vértices de los gráficos G _i . El ancho de la descomposición del camino es entonces uno menos que el número máximo de vértices en uno de los gráficos G _i . ^[2]

Grosor del intervalo

Un gráfico de intervalo con un ancho de ruta dos, uno menor que la cardinalidad de sus cuatro camarillas máximas ABC , ACD , CDE y CDF .

El ancho de ruta de cualquier gráfico G es igual a uno menos que el número de camarilla más pequeño de un gráfico de intervalo que contiene G como subgrafo. ^[12] Es decir, para cada descomposición de trayectoria de G se puede encontrar un supergrafo de intervalo de G , y para cada supergrafo de intervalo de G se puede encontrar una descomposición de trayectoria de G , tal que el ancho de la descomposición sea uno menos que la camarilla número del gráfico de intervalo.

En una dirección, supongamos que se da una descomposición de trayectoria de G. Entonces se pueden representar los nodos de la descomposición como puntos en una línea (en orden de trayectoria) y representar cada vértice v como un intervalo cerrado que tiene estos puntos como puntos finales. De esta manera, los nodos de descomposición de caminos que contienen v corresponden a los puntos representativos en el intervalo para v . El gráfico de intersección de los intervalos formados a partir de los vértices de G es un gráfico de intervalo que contiene G como subgrafo. Sus camarillas máximas están dadas por los conjuntos de intervalos que contienen los puntos representativos, y su tamaño máximo de camarilla es uno más el ancho de ruta de G.

En la otra dirección, si G es un subgrafo de un gráfico de intervalo con número de camarilla p + 1 , entonces G tiene una descomposición de camino de ancho p cuyos nodos están dados por las camarillas máximas del gráfico de intervalo. Por ejemplo, el gráfico de intervalos que se muestra con su representación de intervalos en la figura tiene una descomposición de trayectoria con cinco nodos, correspondientes a sus cinco camarillas máximas ABC , ACD , CDE , CDF y FG ; el tamaño máximo de camarilla es tres y el ancho de esta descomposición del camino es dos.

Esta equivalencia entre el ancho de la ruta y el espesor del intervalo es muy análoga a la equivalencia entre el ancho del árbol y el número mínimo de camarilla (menos uno) de un gráfico cordal del cual el gráfico dado es un subgrafo. Los gráficos de intervalos son un caso especial de gráficos de cuerdas, y los gráficos de cuerdas se pueden representar como gráficos de intersección de subárboles de un árbol común, generalizando la forma en que los gráficos de intervalo son gráficos de intersección de subtrayectos de una ruta.

Número de separación de vértices

El número de separación de vértices de G con respecto a un ordenamiento lineal de los vértices de G es el número más pequeño s tal que, para cada vértice v , como máximo s vértices son anteriores a v en el ordenamiento pero que tienen v o un vértice posterior como un vecino. El número de separación de vértices de G es el número de separación de vértices más pequeño de G con respecto a cualquier ordenamiento lineal de G. El número de separación de vértices fue definido por Ellis, Sudborough y Turner (1983) y es igual al ancho de ruta de G. ^[13] Esto se desprende de la equivalencia anterior con los números de camarilla del gráfico de intervalo: si G es un subgrafo de un gráfico de intervalo I , representado (como en la figura) de tal manera que todos los puntos finales del intervalo sean distintos, entonces el orden de la izquierda Los puntos finales de los intervalos de I tienen una separación de vértices número uno menor que el número de camarilla de I. Y en la otra dirección, a partir de un ordenamiento lineal de G se puede derivar una representación de intervalo en la que el punto extremo izquierdo del intervalo para un vértice v es su posición en el ordenamiento y el punto extremo derecho es la posición del vecino de v que viene último en el pedido.

Número de búsqueda de nodo

El juego de búsqueda de nodos en un gráfico es una forma de persecución-evasión en la que un conjunto de buscadores colaboran para localizar a un fugitivo escondido en un gráfico. Los buscadores se colocan en los vértices del gráfico, mientras que el fugitivo puede estar en cualquier borde del gráfico, y la ubicación y los movimientos del fugitivo están ocultos para los buscadores. En cada turno, algunos o todos los buscadores pueden moverse (arbitrariamente, no necesariamente a lo largo de los bordes) de un vértice a otro, y luego el fugitivo puede moverse a lo largo de cualquier camino en el gráfico que no pase por un vértice ocupado por el buscador. El fugitivo es capturado cuando ambos extremos de su borde están ocupados por buscadores. El número de búsqueda de nodos de un gráfico es el número mínimo de buscadores necesarios para garantizar que se pueda garantizar la captura del fugitivo, sin importar cómo se mueva. Como muestran Kirousis y Papadimitriou (1985), el número de búsqueda de nodos de un gráfico es igual al espesor del intervalo. La estrategia óptima para los buscadores es moverlos de modo que en turnos sucesivos formen conjuntos de separación de un orden lineal con un número mínimo de separación de vértices.

Límites

Un árbol de oruga , un gráfico máximo con un ancho de ruta uno.

Cada gráfico de n -vértices con ancho de ruta k tiene como máximo k ( n − k + ( k − 1)/2) aristas, y los gráficos de ancho de ruta máximo k (gráficos a los que no se pueden agregar más aristas sin aumentar el ancho de ruta) tienen exactamente esta cantidad de bordes. Un gráfico de ancho de ruta máximo k debe ser un k camino o una k oruga, dos tipos especiales de k árbol. Un k -árbol es un gráfico cordal con exactamente n - k camarillas máximas , cada una de las cuales contiene k + 1 vértices; en un k -árbol que no es en sí mismo una camarilla ( k + 1) , cada camarilla máxima separa el gráfico en dos o más componentes, o contiene un vértice de una sola hoja, un vértice que pertenece a una sola camarilla máxima. Un k -camino es un k -árbol con como máximo dos k -hojas, y una k -oruga es un k -árbol que se puede dividir en un k -camino y un conjunto de k -hojas, cada una adyacente a un separador k - camarilla del k -camino. En particular, las gráficas máximas de ancho de camino uno son exactamente los árboles de orugas . ^[14]

Dado que las descomposiciones de ruta son un caso especial de descomposición de árboles, el ancho de ruta de cualquier gráfico es mayor o igual que su ancho de árbol . El ancho de ruta también es menor o igual que el ancho de corte , el número mínimo de aristas que cruzan cualquier corte entre los vértices con números más bajos y más altos en una disposición lineal óptima de los vértices de un gráfico; esto se debe a que el número de separación de vértices, el número de vértices con números más bajos con vecinos con números más altos, puede como máximo igualar el número de aristas cortadas. ^[15] Por razones similares, el ancho de corte es como máximo el ancho de ruta multiplicado por el grado máximo de los vértices en un gráfico determinado. ^[dieciséis]

Cualquier bosque de n -vértices tiene un ancho de ruta O (log n ) . ^[17] Porque, en un bosque, siempre se puede encontrar un número constante de vértices cuya eliminación deja un bosque que puede dividirse en dos subbosques más pequeños con como máximo 2 n ⁄ 3 vértices cada uno. Una disposición lineal formada al dividir recursivamente cada uno de estos dos subbosques, colocando los vértices de separación entre ellos, tiene un número de búsqueda de vértices logarítmico. La misma técnica, aplicada a una descomposición en árbol de un gráfico, muestra que, si el ancho de árbol de un gráfico de n vértices G es t , entonces el ancho de ruta de G es O ( t log n ) . ^[18] Dado que los gráficos de planos exteriores , los gráficos de series-paralelas y los gráficos de Halin tienen un ancho de árbol acotado, todos también tienen como máximo un ancho de ruta logarítmico.

Además de sus relaciones con el ancho del árbol, el ancho de ruta también está relacionado con el ancho de camarilla y el ancho de corte , a través de gráficos de líneas ; el gráfico lineal L ( G ) de un gráfico G tiene un vértice para cada arista de G y dos vértices en L ( G ) son adyacentes cuando los dos aristas correspondientes de G comparten un punto final. Cualquier familia de gráficos tiene un ancho de ruta acotado si y solo si sus gráficos lineales tienen un ancho de camarilla lineal acotado, donde el ancho de camarilla lineal reemplaza la operación de unión disjunta de ancho de camarilla con la operación de unir un único vértice nuevo. ^[19] Si un gráfico conectado con tres o más vértices tiene un grado máximo de tres, entonces su ancho de corte es igual al número de separación de vértices de su gráfico lineal. ^[20]

En cualquier gráfico plano , el ancho del camino es como máximo proporcional a la raíz cuadrada del número de vértices. ^[21] Una forma de encontrar una descomposición de caminos con este ancho es (de manera similar a la descomposición de caminos de bosques de ancho logarítmico descrita anteriormente) usar el teorema del separador plano para encontrar un conjunto de vértices O ( √ n ) la eliminación de que separa el gráfico en dos subgrafos de como máximo 2 norte ⁄ 3 vértices cada uno, y concatena descomposiciones de rutas construidas recursivamente para cada uno de estos dos subgrafos. La misma técnica se aplica a cualquier clase de gráficas para las que se cumpla un teorema de separación similar. ^[22] Dado que, al igual que los gráficos planos, los gráficos en cualquier familia de gráficos fijos menores cerrados tienen separadores de tamaño O ( √ n ) , ^[23] se deduce que el ancho de ruta de los gráficos en cualquier familia fija menor cerrada es nuevamente O ( √ norte ) . Para algunas clases de gráficos planos, el ancho de ruta del gráfico y el ancho de ruta de su gráfico dual deben estar dentro de un factor constante entre sí: los límites de esta forma son conocidos para gráficos planos externos biconectados ^[24] y para gráficos poliédricos. ^[25] Para gráficos planos de 2 conectados, el ancho de ruta del gráfico dual es menor que el ancho de ruta del gráfico lineal. ^[26] Queda abierto si el ancho de ruta de un gráfico plano y su dual están siempre dentro de un factor constante entre sí en los casos restantes.

En algunas clases de gráficos, se ha demostrado que el ancho de ruta y el ancho de árbol son siempre iguales entre sí: esto es cierto para los cografos , ^[27] los gráficos de permutación , ^[28] los complementos de los gráficos de comparabilidad , ^[29] y los gráficos de comparabilidad. de órdenes de intervalo . ^[30]

Problema no resuelto en matemáticas :

¿Cuál es el mayor ancho de ruta posible de un gráfico cúbico de n vértices ?

(más problemas sin resolver en matemáticas)

En cualquier gráfico cúbico , o más generalmente en cualquier gráfico con un grado máximo de vértice tres, el ancho de ruta es como máximo n ⁄ 6 + o( n ) , donde n es el número de vértices en el gráfico. Existen gráficos cúbicos con un ancho de ruta de 0,082 n , pero no se sabe cómo reducir esta brecha entre este límite inferior y el n ⁄ 6 límite superior. ^[31]

Computar descomposiciones de caminos

Es NP-completo 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 del peor de los casos más conocidos para calcular el ancho de ruta de gráficos arbitrarios de n -vértices son de la forma O (2 ⁿ n ^c ) para alguna constante  c . ^[32] Sin embargo, se conocen varios algoritmos que calculan las descomposiciones de caminos de manera más eficiente cuando el ancho de camino es pequeño, cuando la clase de gráficos de entrada es limitada, o aproximadamente.

Tratabilidad de parámetros fijos

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, de ser así, encontrar una descomposición de ruta del 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, se aplica un algoritmo de programación dinámica 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 ² , poco prácticos excepto para los valores más pequeños de k . ^[33] 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.

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 sigue siendo NP-completo cuando G está restringido a gráficos de grados acotados, ^[34] gráficos planos , ^[34] gráficos planos de grado acotado, ^[34] gráficos cordales , ^[35] dominó cordal, ^[36] los complementos de gráficos de comparabilidad , ^[29] y gráficos bipartitos de distancia-hereditaria . ^[37] Se deduce inmediatamente que también es NP-completo para las familias de gráficos que contienen los gráficos bipartitos hereditarios de distancia, incluidos los gráficos bipartitos, los gráficos bipartitos cordales, los gráficos hereditarios de distancia y los gráficos circulares . ^[37]

Sin embargo, el ancho del camino se puede calcular 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 en series paralelas , gráficos planos externos y gráficos de Halin , ^[7] así como para gráficos divididos , ^[38] para los complementos de gráficos cordales, ^{[ 39]} para gráficos de permutación , ^[28] para cografos , ^[27] para gráficos de arco circular , ^[40] para gráficos de comparabilidad de órdenes de intervalo, ^[30] y por supuesto para los propios gráficos de intervalo , 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

Es NP-difícil aproximar el ancho de ruta de un gráfico dentro de una constante aditiva. ^{[6] La} relación de aproximación más conocida de un algoritmo de aproximación de tiempo polinomial para el ancho de ruta es O ((log n ) ^3/2 ) . ^[41] Para algoritmos de aproximación anteriores para el ancho de ruta, consulte Bodlaender et al. (1992) y Guha (2000). Para aproximaciones sobre clases restringidas de gráficos, consulte Kloks y Bodlaender (1992).

Graficar menores

Un menor de un gráfico G es otro gráfico formado a partir de G contrayendo aristas, eliminando aristas y eliminando vértices. Los grafos menores tienen una teoría profunda en la que varios resultados importantes involucran el ancho de ruta.

Excluyendo un bosque

Si una familia F de grafos es cerrada tomando 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 grafos que no tienen ningún menor en X , donde X es un conjunto finito de menores prohibidos . ^[42] Por ejemplo, el teorema de Wagner establece que los gráficos planos son los gráficos que no tienen ni el gráfico completo K ₅ ni el gráfico bipartito completo K _3,3 como menores. En muchos casos, las propiedades de F y las propiedades de X están estrechamente relacionadas, y el primer resultado de este tipo fue el de Robertson & Seymour (1983), ^[2] y relaciona el ancho de camino acotado con la existencia de un bosque en la familia de menores prohibidos. Específicamente, defina una familia F de gráficos para que tenga un ancho de ruta acotado si existe una p constante tal que cada gráfico en F tenga un ancho de ruta como máximo p . Entonces, una familia F cerrada con menores tiene un ancho de camino acotado si y sólo si el conjunto X de menores prohibidos para F incluye al menos un bosque.

En una dirección, este resultado es sencillo de probar: si X no incluye al menos un bosque, entonces los gráficos libres de X no tienen un ancho de ruta acotado. Porque, en este caso, los gráficos libres de 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 un ancho de ruta k , por lo que en este caso los gráficos libres menores de X tienen un ancho de ruta ilimitado. En la otra dirección, si X contiene un bosque de n -vértices, entonces los gráficos libres de X -menores tienen un ancho de ruta como máximo n − 2 . ^[43]

Obstrucciones al ancho de camino acotado

Los menores prohibidos para gráficos de ancho de ruta 1.

La propiedad de tener un ancho de camino como máximo p es, en sí misma, cerrada al tomar menores: si G tiene una descomposición de camino con un ancho como máximo p , entonces la misma descomposición de camino 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 caminos sin aumentar el ancho. La contracción de un borde también se puede lograr sin aumentar el ancho de la descomposición, fusionando las subtrayectorias que representan los dos puntos finales del borde contraído. Por lo tanto, las gráficas de ancho de ruta como máximo p pueden caracterizarse por un conjunto X _p de menores excluidos. ^{[42] [44]}

Aunque X _p incluye necesariamente al menos un bosque, no es cierto que todos los gráficos en X _p sean bosques: por ejemplo, X ₁ consta de dos gráficos, un árbol de siete vértices y el triángulo K ₃ . Sin embargo, el conjunto de árboles en X _p puede caracterizarse con precisión: estos árboles son exactamente los árboles que pueden formarse a partir de tres árboles en X _{p − 1} conectando un nuevo vértice raíz mediante una arista 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 ₁ se forma de esta manera a partir del árbol de dos vértices (una arista única) en X ₀ . Con base en esta construcción, se puede demostrar que el número de menores prohibidos en X _p es al menos ( p !) ² . ^[44] Se ha calculado el conjunto completo X ₂ de menores prohibidos para gráficos de ancho de ruta-2; Contiene 110 gráficos diferentes. ^[45]

Teoría de la estructura

El teorema de estructura de grafos para familias de grafos cerrados menores establece que, para cualquier familia de este tipo F , los gráficos en F se pueden descomponer en sumas de gráficos que se pueden incrustar en superficies de género acotado , junto con un número acotado de vértices y vórtices para cada componente de la suma camarilla. Un vértice es un vértice que puede ser 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 de la incrustación de género acotado de un componente. El ordenamiento 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 ordenamiento lineal debe conducir a un ordenamiento con un número de separación de vértices acotado. ^[4] Esta teoría, en la que el ancho de ruta está íntimamente conectado con familias arbitrarias de gráficos menores cerrados, tiene importantes aplicaciones algorítmicas. ^[46]

Aplicaciones

VLSI

En el diseño VLSI , el problema de separación de vértices se estudió originalmente como una forma de dividir circuitos en subsistemas más pequeños, con una pequeña cantidad de componentes en el límite entre los subsistemas. ^[34]

Ohtsuki et al. (1979) utilizan el espesor del 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 deben estar interconectados mediante un sistema de redes. En su modelo, se 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 ambas redes se conectan al mismo módulo; es decir, si se interpreta que los módulos y las redes forman los nodos e hiperbordes de un hipergrafo , entonces el gráfico formado a partir de ellos es su gráfico lineal . Una representación de intervalo de un supergrafo de este gráfico lineal, junto con un color del supergrafo, 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 orden lineal y conectar a las redes apropiadas. El hecho de que los gráficos de intervalo sean gráficos perfectos ^[47] 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 del intervalo completado del gráfico neto.

El diseño de matriz de puertas ^[48] es un estilo específico de diseño CMOS VLSI para circuitos lógicos booleanos . En los diseños de matriz de puertas, las señales se propagan a lo largo de "líneas" (segmentos de línea verticales), 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. Así, el segmento de línea horizontal de cada compuerta debe cruzar los segmentos verticales de cada una de las líneas que forman las entradas o salidas de la compuerta. Como en los diseños de Ohtsuki et al. (1979), se puede encontrar un diseño de este tipo que minimice 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 vértices y pares de líneas que comparten una puerta como punto de partida. bordes. ^[49] El mismo enfoque algorítmico también se puede utilizar para modelar problemas de plegado en matrices lógicas programables . ^[50]

dibujo gráfico

Pathwidth tiene varias aplicaciones para dibujar gráficos :

• Los gráficos mínimos que tienen un número de cruce determinado tienen un ancho de ruta limitado por una función de su número de cruce. ^[51]
• 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. ^[52]
• Un dibujo de k -cruce de h -capa de un gráfico G es una colocación de los vértices de G en h líneas horizontales distintas, con bordes trazados como caminos poligonales monótonos entre estas líneas, de tal manera que hay como máximo k cruces. Los gráficos con tales 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 . ^[53]
• 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 haya dos aristas (representadas como segmentos de línea recta entre puntos de la cuadrícula) que se crucen entre sí. Por tanto, las gráficas de ancho de camino acotado tienen incrustaciones de este tipo con volumen lineal. ^[54]

Diseño del compilador

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 en 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 colocados en los registros de la máquina en lugar de tener que derramarse en la memoria principal. En esta aplicación, se representa el código que se va a 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 x es una de las entradas a la operación y . Un ordenamiento 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 determinado viene dado por el número de separación de vértices del ordenamiento. ^[55]

Para cualquier número fijo w de registros de máquina, es posible determinar en tiempo lineal si un fragmento de código lineal se puede reordenar de tal manera que se pueda evaluar con como máximo w registros. 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 ignorando las orientaciones del DAG descrito anteriormente debe tener un ancho de ruta como máximo w . Es posible probar si este es el caso, utilizando los algoritmos manejables de parámetros fijos conocidos para el ancho de ruta y, de ser así, encontrar una descomposición de ruta para el gráfico no dirigido, en tiempo lineal, dado el supuesto de que w es una constante. Una vez que se ha encontrado una descomposición de ruta, se puede encontrar un ordenamiento topológico de ancho w (si existe) usando programación dinámica, nuevamente en tiempo lineal. ^[55]

Lingüística

Kornai y Tuza (1992) describen una aplicación del 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 una ventaja entre esas dos palabras. Debido a la capacidad limitada de la memoria humana a corto plazo, ^[56] Kornai y Tuza argumentan que este gráfico debe tener un ancho de ruta acotado (más específicamente, argumentan, un ancho de ruta como máximo seis), ya que de lo contrario los humanos no serían capaces de analizar el habla correctamente. .

Algoritmos exponenciales

Muchos problemas en algoritmos de gráficos se pueden resolver de manera eficiente en gráficos de ancho de ruta bajo, 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 G de n -vértices , con 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 ). ^[31] En gráficos de ancho de ruta acotado, este enfoque conduce a algoritmos manejables de parámetros fijos, parametrizados por el ancho de ruta. ^[49] Estos resultados no se encuentran con frecuencia en la literatura porque están incluidos en 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 ancho de árbol al 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, combinar este enfoque de programación dinámica con el hecho de que los gráficos cúbicos tienen un 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. ^[31] Un enfoque similar conduce a algoritmos de tiempo exponencial mejorados para los problemas de corte máximo y conjunto dominante mínimo en gráficos cúbicos, ^[31] y para varios otros problemas de optimización NP-hard. ^[57]

Ver también

• Boxicity , una forma diferente de medir la complejidad de un gráfico arbitrario en términos de gráficos de intervalo
• Cutwidth , el ancho mínimo posible de un ordenamiento lineal de los vértices de un gráfico.
• Profundidad del árbol , un número acotado para una familia de gráficos menores cerrados si y solo si la familia excluye una ruta
• Degeneración , una medida de la escasez de un gráfico que es como máximo igual a su ancho de ruta
• Ancho de banda del gráfico , un problema de optimización NP completo diferente que involucra diseños lineales de gráficos
• Número de Strahler , una medida de la complejidad de los árboles enraizados definida de manera similar al ancho de camino de los árboles sin raíces

Notas

1. Diestel y Kühn (2005).
2. Robertson y Seymour (1983).
3. Bodlaender (1998).
4. Robertson y Seymour (2003).
5. Kashiwabara y Fujisawa (1979); Ohtsuki et al. (1979); Lengauer (1981); Arnborg, Corneil y Proskurowski (1987).
6. Bodlaender y col. (1992).
7. Bodlaender (1996); Bodlaender y Kloks (1996)
8. Bodlaender (1994).
9. Möhring (1990); Scheffler (1990); Ellis, Sudborough y Turner (1994); Peng et al. (1998); Skodinis (2000); Skodinis (2003); Coudert, Huc y Mazauric (2012).
10. Arnborg (1985).
11. Aspvall, Proskurowski y Telle (2000).
12. Bodlaender (1998), Teorema 29, pág. 13.
13. Kinnersley (1992); Bodlaender (1998), Teorema 51.
14. Proskurowski y Telle (1999).
15. Koraj y Solel (1993), Lema 3 p.99; Bodlaender (1998), Teorema 47, pág. 24.
16. Koraj y Solel (1993), Lema 1, pág. 99; Bodlaender (1998), Teorema 49, pág. 24.
17. Koraj y Solel (1993), Teorema 5, p. 99; Bodlaender (1998), Teorema 66, pág. 30. Scheffler (1992) proporciona un límite superior más estricto de log ₃ (2 n + 1) en el ancho de camino de un bosque de n vértices.
18. Koraj y Solel (1993), Teorema 6, p. 100; Bodlaender (1998), Corolario 24, p.10.
19. Gurski y Wanke (2007).
20. Golovach (1993).
21. Bodlaender (1998), Corolario 23, p. 10.
22. Bodlaender (1998), Teorema 20, p. 9.
23. Alon, Seymour y Thomas (1990).
24. Bodlaender y Fomin (2002); Coudert, Huc y Sereni (2007).
25. Fomín y Thilikos (2007); Amini, Huc y Pérennes (2009).
26. Fomín (2003).
27. Bodlaender y Möhring (1990).
28. Bodlaender, Kloks y Kratsch (1993).
29. Habib y Möhring (1994).
30. Garbe (1995).
31. Fomin y Høie (2006).
32. Fomín y col. (2008).
33. Downey y compañeros (1999), p.12.
34. Monien y Sudborough (1988).
35. Gustedt (1993).
36. Kloks, Kratsch y Müller (1995). Un dominó cordal es un gráfico cordal en el que cada vértice pertenece como máximo a dos camarillas máximas.
37. Kloks et al. (1993).
38. Kloks y Bodlaender (1992); Gustedt (1993).
39. Garbe (1995) atribuye este resultado al Ph.D. tesis de Ton Kloks; El algoritmo de tiempo polinomial de Garbe para gráficos de comparabilidad de órdenes de intervalo generaliza este resultado, ya que cualquier gráfico cordal debe ser un gráfico de comparabilidad de este tipo.
40. Suchan y Todinca (2007).
41. Feige, Hajiaghayi y Lee (2005).
42. Robertson y Seymour (2004).
43. Bienstock y otros. (1991); Diestel (1995); Cattell, Dinneen y compañeros (1996).
44. Kinnersley (1992); Takahashi, Ueno y Kajitani (1994); Bodlaender (1998), pág. 8.
45. Kinnersley y Langston (1994).
46. Demaine, Hajiaghayi y Kawarabayashi (2005).
47. Bergé (1967).
48. López y Law (1980).
49. Fellows y Langston (1989).
50. Mohring (1990); Ferreira y Canción (1992).
51. Hliněny (2003).
52. Suderman (2004).
53. Dujmović y otros. (2008).
54. Dujmović, Morin y Wood (2003).
55. Bodlaender, Gustedt y Telle (1998).
56. Molinero (1956).
57. Kneis y col. (2005); Björklund y Husfeldt (2008).

Referencias

• Alón, Noga ; Seymour, Pablo ; Thomas, Robin (1990), "Un teorema del separador para grafos con un menor excluido y sus aplicaciones", Proc. 22º Simposio ACM. sobre teoría de la informática (STOC 1990) , págs. 293–299, doi : 10.1145/100216.100254 , ISBN 0897913612, S2CID  17521329.
• Amini, Omid; Huc, Florián; Pérennes, Stéphane (2009), "Sobre el ancho de trayectoria de los gráficos planos", Revista SIAM de Matemáticas Discretas , 23 (3): 1311–1316, doi :10.1137/060670146.
• Arnborg, Stefan (1985), "Algoritmos eficientes para problemas combinatorios en gráficos con descomponibilidad acotada - Una encuesta", BIT , 25 (1): 2–23, doi :10.1007/BF01934985, S2CID  122263659.
• Arnborg, Stefan; Corneil, Derek G .; Proskurowski, Andrzej (1987), "Complejidad de encontrar incrustaciones en un árbol k ", Revista SIAM sobre métodos algebraicos y discretos , 8 (2): 277–284, doi :10.1137/0608024.
• Aspvall, Bengt; Proskurowski, Andrzej; Telle, Jan Arne (2000), "Requisitos de memoria para cálculos de tablas en algoritmos de árbol k parciales ", Algorithmica , 27 (3): 382–394, doi :10.1007/s004530010025, S2CID  9690525.
• Berge, Claude (1967), "Algunas clases de grafos perfectos", Teoría de grafos y física teórica , Nueva York: Academic Press, págs..
• Bienstock, Dan; Robertson, Neil ; Seymour, Pablo ; Thomas, Robin (1991), "Excluyendo rápidamente un bosque", Journal of Combinatorial Theory, Serie B , 52 (2): 274–283, doi : 10.1016/0095-8956(91)90068-U.
• Björklund, Andreas; Husfeldt, Thore (2008), "Algoritmos exactos para la satisfacibilidad exacta y el número de coincidencias perfectas", Algorithmica , 52 (2): 226–249, doi :10.1007/s00453-007-9149-8, S2CID  37693881.
• Bodlaender, Hans L. (1994), "Una guía turística a través del ancho de los árboles", en Dassow, Jürgen; Kelemenová, Alisa (eds.), Developments in Theoretical Computer Science (Proc. Séptimo encuentro internacional de jóvenes informáticos, Smolenice, 16 a 20 de noviembre de 1992) , Topics in Computer Mathematics, vol. 6, Gordon y Breach, págs. 1-20.
• Bodlaender, Hans L. (1994a). "Una guía turística a través del ancho de los árboles". Acta Cibernética . 11 : 1–2.
• Bodlaender, Hans L. (1996), "Un algoritmo de tiempo lineal para encontrar descomposiciones de árboles de ancho pequeño", SIAM Journal on Computing , 25 (6): 1305–1317, doi :10.1137/S0097539793251219, hdl : 1874/16670.
• Bodlaender, Hans L. (1998), "Un k -arboreto parcial de gráficos con ancho de árbol acotado", Ciencias de la Computación Teórica , 209 (1–2): 1–45, doi : 10.1016/S0304-3975(97)00228-4.
• Bodlaender, Hans L .; Fomin, Fedor V. (2002), "Aproximación del ancho de ruta de gráficos planos externos", Journal of Algorithms , 43 (2): 190–200, doi :10.1016/S0196-6774(02)00001-9.
• Bodlaender, Hans L .; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton (1992), "Aproximación del ancho del árbol, el ancho de la ruta y la altura mínima del árbol de eliminación", Conceptos teóricos de grafos en informática , Apuntes de conferencias en informática , vol. 570, págs. 1 a 12, doi :10.1007/3-540-55121-2_1, hdl : 1874/17927 , ISBN 978-3-540-55121-8.
• Bodlaender, Hans L .; Gustedt, Jens; Telle, Jan Arne (1998), "Asignación de registros en tiempo lineal para un número fijo de registros", Proc. Noveno Simposio ACM-SIAM sobre algoritmos discretos (SODA '98) (PDF) , págs..
• Bodlaender, Hans L .; Kloks, Ton (1996), "Algoritmos eficientes y constructivos para el ancho de ruta y el ancho de árbol de gráficos", Journal of Algorithms , 21 (2): 358–402, doi :10.1006/jagm.1996.0049, hdl : 1874/16538.
• Bodlaender, Hans L .; Kloks, tonelada; Kratsch, Dieter (1993), "Ancho de árbol y ancho de ruta de gráficos de permutación", Proc. XX Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 1993) , Lecture Notes in Computer Science, vol. 700, Springer-Verlag, págs. 114-125, doi :10.1007/3-540-56939-1_66, hdl : 1874/16657 , ISBN 978-3-540-56939-8.
• Bodlaender, Hans L .; Möhring, Rolf H. (1990), "El ancho de ruta y el ancho de árbol de los cografos", Proc. Segundo taller escandinavo sobre teoría de algoritmos , Apuntes de conferencias sobre informática, vol. 447, Springer-Verlag, págs. 301–309, doi :10.1007/3-540-52846-6_99, hdl : 1874/16625 , ISBN 978-3-540-52846-3.
• Cattell, Kevin; Dinneen, Michael J.; Fellows, Michael R. (1996), "Un algoritmo simple de tiempo lineal para encontrar descomposiciones de caminos de ancho pequeño", Information Processing Letters , 57 (4): 197–203, arXiv : math/9410211 , doi : 10.1016/0020 -0190(95)00190-5, S2CID  2442557.
• Coudert, David; Huc, Florián; Mazauric, Dorian (2012), "Un algoritmo distribuido para calcular el número de búsqueda de nodos en árboles" (PDF) , Algorithmica , 63 (1): 158–190, doi :10.1007/s00453-011-9524-3.
• Coudert, David; Huc, Florián; Sereni, Jean-Sébastien (2007), "Ancho de ruta de gráficos planos externos" (PDF) , Journal of Graph Theory , 55 (1): 27–41, doi :10.1002/jgt.20218.
• Diestel, Reinhard (1995), "Graph Minors I: una breve demostración del teorema del ancho de camino", Combinatoria, probabilidad y computación , 4 (1): 27–30, doi :10.1017/S0963548300001450.
• Diestel, Reinhard; Kühn, Daniela (2005), "Gráfico de jerarquías menores", Matemáticas aplicadas discretas , 145 (2): 167–182, doi : 10.1016/j.dam.2004.01.010.
• Demaine, Erik D .; Hajiaghayi, Mohammad Taghi ; Kawarabayashi, Ken-ichi (2005), "Teoría menor del grafo algorítmico: descomposición, aproximación y coloración", Proc. 46.º Simposio del IEEE sobre fundamentos de la informática (FOCS 2005) , págs. 637–646, doi :10.1109/SFCS.2005.14, ISBN 0-7695-2468-0, S2CID  13238254.
• Downey, Rod G .; Fellows, Michael R. (1999), Complejidad parametrizada , Springer-Verlag, ISBN 0-387-94883-X.
• Dujmović, V .; Becarios, señor ; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; Whitesides, S .; Wood, David R. (2008), "Sobre la complejidad parametrizada del dibujo de gráficos en capas", Algorithmica , 52 (2): 267–292, doi :10.1007/s00453-007-9151-1, S2CID  2298634.
• Dujmović, Vida ; Morín, Pat ; Wood, David R. (2003), "Dibujos de gráficos de cuadrícula de líneas rectas tridimensionales y de ancho de camino" (PDF) , Proc. Décimo Simposio Internacional sobre Dibujo de Gráficos (GD 2002) , Lecture Notes in Computer Science, vol. 2528, Springer-Verlag, págs. 42-53.
• Ellis, JA; Sudborough, Illinois; Turner, JS (1983), "Separación de gráficos y número de búsqueda", Proc. 1983 Conferencia Allerton. sobre Comunicación, Control y Computación. Según lo citado por Monien y Sudborough (1988).
• Ellis, JA; Sudborough, Illinois; Turner, JS (1994), "La separación de vértices y el número de búsqueda de un árbol", Información y Computación , 113 (1): 50–79, doi : 10.1006/inco.1994.1064.
• Feige, Uriel ; Hajiaghayi, Mohammadtaghi ; Lee, James R. (2005), "Algoritmos de aproximación mejorados para separadores de vértices de peso mínimo", Proc. 37º Simposio ACM sobre Teoría de la Computación (STOC 2005) , págs. 563–572, doi :10.1145/1060590.1060674, ISBN 1581139608, S2CID  14097859.
• Becarios, Michael R .; Langston, Michael A. (1989), "Sobre la decisión de búsqueda y la eficiencia de los algoritmos de tiempo polinomial", Proc. XXI Simposio ACM sobre Teoría de la Computación , págs. 501–512, doi : 10.1145/73007.73055 , ISBN 0897913078, S2CID  1854173.
• Ferreira, Alfonso G.; Song, Siang W. (1992), "Lograr la optimización para el diseño de la matriz de puertas y el plegado de PLA: un enfoque teórico de grafos", Proc. 1er Simposio Latinoamericano de Informática Teórica (LATIN '92) , Lecture Notes in Computer Science, vol. 583, Springer-Verlag, págs. 139-153, doi :10.1007/BFb0023825, hdl : 10068/43314 , ISBN 3-540-55284-7.
• de Fluiter, Babette (1997), Algoritmos para gráficos de ancho de árbol pequeño (PDF) , Ph.D. tesis, Universidad de Utrecht , ISBN 90-393-1528-0, archivado desde el original (PDF) el 24 de julio de 2011 , consultado el 6 de mayo de 2010.
• Fomin, Fedor V. (2003), "Ancho de ruta de gráficos planos y lineales", Gráficos y combinatoria , 19 (1): 91–99, doi :10.1007/s00373-002-0490-z, S2CID  43123449.
• Fomin, Fedor V.; Høie, Kjartan (2006), "Ancho de ruta de gráficos cúbicos y algoritmos exactos", Cartas de procesamiento de información , 97 (5): 191–196, doi :10.1016/j.ipl.2005.10.012.
• Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve (2008), "Algoritmos exactos para ancho de árbol y relleno mínimo", SIAM Journal on Computing , 38 (3): 1058–1079, doi :10.1137/050643350, hdl : 1956/1151.
• Fomin, Fedor V.; Thilikos, Dimitrios M. (2007), "Sobre la dualidad propia del ancho de ruta en incrustaciones de gráficos poliédricos", Journal of Graph Theory , 55 (1): 42–54, doi :10.1002/jgt.20219.
• Garbe, Renate (1995), "Ancho de árbol y ancho de ruta de gráficos de comparabilidad de órdenes de intervalo", Proc. XX Taller internacional Conceptos de teoría de grafos en informática (WG'94) , Lecture Notes in Computer Science, vol. 903, Springer-Verlag, págs. 26–37, doi :10.1007/3-540-59071-4_35, ISBN 978-3-540-59071-2.
• Golovach, PA (1993), "El ancho de corte de un gráfico y el número de separación de vértices del gráfico lineal", Matemáticas y aplicaciones discretas , 3 (5): 517–522, doi :10.1515/dma.1993.3.5.517, S2CID  120745961.
• Guha, Sudipto (2000), "Algoritmos de aproximación y disección de gráficos anidados", Proc. 41.º Simposio del IEEE sobre fundamentos de la informática (FOCS 2000) , p. 126, doi :10.1109/SFCS.2000.892072, ISBN 0-7695-0850-2, S2CID  9854056.
• Gurski, Frank; Wanke, Egon (2007), "Gráficos de líneas de ancho de camarilla acotado", Matemáticas discretas , 307 (22): 2734–2754, doi : 10.1016/j.disc.2007.01.020.
• Gustedt, Jens (1993), "Sobre el ancho de ruta de los gráficos cordales", Matemáticas aplicadas discretas , 45 (3): 233–248, doi : 10.1016/0166-218X(93)90012-D.
• Habib, Michel; Möhring, Rolf H. (1994), "Ancho de árbol de gráficos de cocomparabilidad y un nuevo parámetro de teoría de orden", Orden , 11 (1): 47–60, doi :10.1007/BF01462229, S2CID  2648030.
• Hliněny, Petr (2003), "Los gráficos críticos de números cruzados tienen un ancho de ruta acotado", Journal of Combinatorial Theory, Serie B , 88 (2): 347–367, doi : 10.1016/S0095-8956(03)00037-6.
• Kashiwabara, T.; Fujisawa, T. (1979), "NP-completitud del problema de encontrar un gráfico de intervalo de número de camarilla mínimo que contenga un gráfico dado como subgrafo", Proc. Simposio internacional sobre circuitos y sistemas , págs. 657–660.
• Kinnersley, Nancy G. (1992), "El número de separación de vértices de un gráfico es igual a su ancho de ruta", Cartas de procesamiento de información , 42 (6): 345–350, doi : 10.1016/0020-0190(92)90234-M.
• Kinnersley, Nancy G.; Langston, Michael A. (1994), "Aislamiento del conjunto de obstrucciones para el problema de diseño de la matriz de puertas", Matemáticas Aplicadas Discretas , 54 (2–3): 169–213, doi : 10.1016/0166-218X(94)90021-3.
• Kirousis, Lefteris M.; Papadimitriou, Christos H. (1985), "Gráficos de intervalos y búsqueda" (PDF) , Matemáticas discretas , 55 (2): 181–184, doi : 10.1016/0012-365X(85)90046-9 , archivado desde el original ( PDF) el 2011-07-21.
• Kloks, tonelada; Bodlaender, Hans L. (1992), "Aproximación del ancho de árbol y del ancho de ruta de algunas clases de gráficos perfectos", Proc. 3er Simposio Internacional sobre Algoritmos y Computación (ISAAC'92) , Lecture Notes in Computer Science, vol. 650, Springer-Verlag, págs. 116-125, doi :10.1007/3-540-56279-6_64, hdl : 1874/16672 , ISBN 978-3-540-56279-5.
• Kloks, T.; Bodlaender, H .; Müller, H.; Kratsch, D. (1993), "Cálculo del ancho del árbol y el relleno mínimo: todo lo que necesita son los separadores mínimos", Proc. 1er Simposio europeo sobre algoritmos (ESA'93) (Apuntes de conferencias sobre informática) , vol. 726, Springer-Verlag, págs. 260–271, doi :10.1007/3-540-57273-2_61.
• Kloks, tonelada; Kratsch, Dieter; Müller, H. (1995), "Dominó", Proc. XX Taller internacional Conceptos de teoría de grafos en informática (WG'94) , Lecture Notes in Computer Science, vol. 903, Springer-Verlag, págs. 106–120, doi :10.1007/3-540-59071-4_41, ISBN 978-3-540-59071-2.
• Kneis, Joaquín; Molle, Daniel; Richter, Stefan; Rossmanith, Peter (2005), "Algoritmos basados ​​en el ancho de árbol de gráficos dispersos", Proc. 31º Taller internacional sobre conceptos de teoría de grafos en informática (WG 2005) , Lecture Notes in Computer Science, vol. 3787, Springer-Verlag, págs. 385–396, doi :10.1007/11604686_34, ISBN 978-3-540-31000-6.
• Koraj, Efraín; Solel, Nir (1993), "Ancho de árbol, ancho de ruta y ancho de corte", Matemáticas aplicadas discretas , 43 (1): 97–101, doi : 10.1016/0166-218X(93)90171-J.
• Kornai, András; Tuza, Zsolt (1992), "Estrechez, ancho de ruta y su aplicación en el procesamiento del lenguaje natural", Matemáticas Aplicadas Discretas , 36 (1): 87–92, doi : 10.1016/0166-218X(92)90208-R.
• Lengauer, Thomas (1981), "Guijarros blancos y negros y separación de gráficos", Acta Informatica , 16 (4): 465–475, doi :10.1007/BF00264496, S2CID  19415148.
• López, Alejandro D.; Law, Hung-Fai S. (1980), "Un método de diseño de matriz de puerta densa para MOS VLSI", IEEE Transactions on Electron Devices , 27 (8): 1671–1675, Bibcode :1980ITED...27.1671L, doi :10.1109 /T-ED.1980.20086, S2CID  64469353, también en la edición conjunta, IEEE Journal of Solid-State Circuits 15 (4): 736–740, 1980.
• Miller, George A. (1956), "El número mágico siete, más o menos dos", Psychological Review , 63 (2): 81–97, doi :10.1037/h0043158, hdl : 11858/00-001M-0000-002C -4646-B , PMID  13310704.
• Möhring, Rolf H. (1990), "Problemas de gráficos relacionados con el diseño de la matriz de la puerta y el plegado de PLA", en Tinhofer, G.; Mayr, E.; Noltemeier, H.; et al. (eds.), Teoría de grafos computacionales , Computing Supplementum, vol. 7, Springer-Verlag, págs. 17–51, ISBN 3-211-82177-5.
• Monien, B.; Sudborough, IH (1988), "El corte mínimo es NP completo para árboles ponderados por los bordes", Ciencias de la Computación Teórica , 58 (1–3): 209–229, doi : 10.1016/0304-3975(88)90028-X.
• Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio (1979), "Gráficos de intervalo y asignación de puertas lógicas unidimensionales", IEEE Transactions on Circuits and Systems , 26 (9): 675–684, doi :10.1109/TCS.1979.1084695.
• Peng, Sheng-Lung; Ho, Chin-Wen; Hsu, Tsan-sheng; Ko, Ming-Tat; Tang, Chuan Yi (1998), "Un algoritmo de tiempo lineal para construir una estrategia óptima de búsqueda de nodos de un árbol", en Hsu, Wen-Lian; Kao, Ming-Yang (eds.), Computing and Combinatorics, 4th Annual International Conference, COCOON '98, Taipei, Taiwán, República de China, 12 al 14 de agosto de 1998, Actas , Lecture Notes in Computer Science, vol. 1449, Springer, págs. 279–288, doi :10.1007/3-540-68535-9_32
• Proskurowski, Andrzej; Telle, Jan Arne (1999), "Clases de gráficos con modelos de intervalo restringido" (PDF) , Matemáticas discretas e informática teórica , 3 : 167–176.
• Robertson, Neil ; Seymour, Paul (1983), "Gráficos menores. I. Excluyendo un bosque", Journal of Combinatorial Theory, Serie B , 35 (1): 39–61, doi : 10.1016/0095-8956(83)90079-5.
• Robertson, Neil ; Seymour, Paul (2003), "Gráficos menores. XVI. Excluyendo un gráfico no plano", Journal of Combinatorial Theory, Serie B , 89 (1): 43–76, doi : 10.1016/S0095-8956(03)00042- X.
• Robertson, Neil ; Seymour, Paul D. (2004), "Graph Minors. XX. Conjetura de Wagner", Journal of Combinatorial Theory, Serie B , 92 (2): 325–357, doi : 10.1016/j.jctb.2004.08.001.
• Scheffler, Petra (1990), "Un algoritmo lineal para el ancho de camino de los árboles", en Bodendiek, R.; Henn, R. (eds.), Temas de combinatoria y teoría de grafos , Physica-Verlag, págs..
• Scheffler, Petra (1992), "Incrustación óptima de un árbol en un gráfico de intervalo en tiempo lineal", en Nešetřil, Jaroslav ; Fiedler, Miroslav (eds.), Cuarto Simposio checoslovaco sobre combinatoria, gráficos y complejidad , Elsevier.
• Skodinis, Konstantin (2000), "Cálculo de diseños lineales óptimos de árboles en tiempo lineal", Proc. Octavo Simposio Europeo sobre Algoritmos (ESA 2000) , Lecture Notes in Computer Science, vol. 1879, Springer-Verlag, págs. 403–414, doi :10.1007/3-540-45253-2_37, ISBN 978-3-540-41004-1.
• Skodinis, Konstantin (2003), "Construcción de diseños de árboles lineales que son óptimos con respecto a la separación de vértices en tiempo lineal", Journal of Algorithms , 47 (1): 40–59, doi :10.1016/S0196-6774(02) 00225-0.
• Suchan, Karol; Todinca, Ioan (2007), "Ancho de ruta de gráficos de arco circular", Proc. 33º Taller internacional sobre conceptos de teoría de grafos en informática (WG 2007) , Lecture Notes in Computer Science, vol. 4769, Springer-Verlag, págs. 258–269, doi :10.1007/978-3-540-74839-7_25.
• Suderman, Matthew (2004), "Pathwidth and Layered Drawings of Trees" (PDF) , Revista Internacional de Geometría y Aplicaciones Computacionales , 14 (3): 203–225, doi :10.1142/S0218195904001433, archivado desde el original (PDF) en 2003-05-03.
• Takahashi, Atsushi; Ueno, Shûichi; Kajitani, Yoji (1994), "Menores acíclicos mínimos prohibidos para la familia de gráficos con ancho de ruta acotado", Matemáticas discretas , 127 (1–3): 293–304, doi : 10.1016/0012-365X(94)90092- 2.