Ancho de pista

En la teoría de grafos, la descomposición del camino de un gráfico G  es, de manera informal, la representación de un gráfico G como un camino "engrosado" [1] , y el ancho del camino de un gráfico G  es un número que mide cuánto se ha desplazado el gráfico G. espesado Más formalmente, una descomposición de caminos es una secuencia de vértices de un subconjunto del grafo G tal que los vértices finales de cada arista aparecen en uno de los subconjuntos y cada vértice pertenece a (al menos) uno de los conjuntos [2] , y el ancho del camino 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 el grosor del intervalo (uno menos que el tamaño de la camarilla más grande del supergráfico de intervalo del gráfico G ), el valor de separación de vértice o el número de búsqueda de vértice [3] [4] .

El ancho del camino y la descomposición del camino son muy similares al ancho del árbol y la descomposición del árbol . Desempeñan un papel clave en la teoría de grafos menores  : las familias de grafos que están cerrados bajo grafos menores y no incluyen todos los bosques se pueden caracterizar por tener un ancho de ruta limitado [2] , y los "vórtices" que surgen en la estructura general. teoría de las familias de grafos cerrados con respecto a los menores, tienen un ancho de camino limitado [5] . Los gráficos de ancho de ruta y de ancho de ruta acotado tienen aplicaciones en ingeniería VLSI , visualización de gráficos y lingüística computacional .

El problema de encontrar el ancho de ruta de gráficos arbitrarios es NP-difícil . Además, incluso el problema de aproximar exactamente el ancho del camino es NP-difícil [6] [7] . Sin embargo, este problema tiene una solución paramétrica fija:  probar si un gráfico tiene un ancho de ruta k se puede resolver en un tiempo que es lineal en el tamaño del gráfico pero superexponencial en k [8] Además, para algunas clases especiales de gráficos, como árboles , el ancho de la ruta se puede calcular en tiempo polinomial independiente de k [9] [10] . Muchos problemas de la teoría de grafos se pueden resolver de manera efectiva en gráficos con un ancho de ruta limitado usando programación dinámica en la descomposición de la ruta del gráfico [11] . La descomposición del árbol también se puede utilizar para estimar la complejidad de la capacidad de los algoritmos de programación dinámica en gráficos con un ancho de árbol limitado [12] .

Definición

En la primera serie famosa de artículos sobre grafos menores, Robertson y Seymour [2] definieron una descomposición de caminos de un grafo G como una secuencia de subconjuntos Xi de vértices del grafo G con dos propiedades:

1. Para cada arista G , existe i tal que ambos extremos de la arista pertenecen al subconjunto X i
2. Para tres índices i ≤ j ≤ k , X i ∩ X k ⊆ X j .

La segunda de estas dos propiedades es equivalente al requisito de que los subconjuntos que contienen cualquier vértice formen una subsecuencia continua de la secuencia completa. En el lenguaje de las últimas series de Robertson y Seymour sobre grafos menores, una descomposición de trayectoria es una descomposición en árbol de ( X , T ) en la que el árbol de descomposición subyacente T es una trayectoria .

El ancho de la descomposición del camino se define de la misma manera que para la descomposición del árbol, como max i  | X yo | − 1, y el ancho del camino del gráfico G es igual al ancho mínimo de todas las descomposiciones del camino del gráfico G . Restar uno del tamaño de X i en esta definición tiene poco efecto en la mayoría de las aplicaciones de ancho de ruta, pero hace que el ancho de ruta sea igual a uno.

Descripciones alternativas

Como escribe Bodlaender [3] , el ancho de ruta se puede describir de muchas maneras equivalentes.

Secuencias de pegado

Una descomposición en árbol se puede describir como una secuencia de gráficos G i , que se pegan identificando pares de vértices en gráficos adyacentes de la secuencia y, como resultado de este pegado, se forma un gráfico G . Como grafos G i podemos tomar subgrafos generados de conjuntos X i en la primera definición de descomposición de caminos, con vértices pegados en subgrafos generados vecinos, si estos vértices son generados por el mismo vértice de G . En otra dirección, se puede tomar X i como los conjuntos de vértices de los gráficos G i . El ancho de la descomposición del árbol 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

El ancho de la ruta de cualquier gráfico G es uno menos que el número de camarilla más pequeño del gráfico de intervalo que contiene a G como un subgráfico [14] . Es decir, para cualquier descomposición en árbol del gráfico G , uno puede encontrar un supergráfico de intervalo, y para cualquier supergráfico de intervalo G , uno puede encontrar una descomposición en árbol del gráfico G cuyo ancho de descomposición es uno menos que el número clique del gráfico de intervalo .

En una dirección, suponga que se da una descomposición en árbol de un gráfico G. Entonces uno puede representar los vértices de la descomposición como puntos en la línea (en el orden en que entran en el camino) y representar cada vértice v como un intervalo cerrado que tiene estos puntos como extremos. Por ejemplo, sea ( X 1 , . . . , X r ) una descomposición de caminos del gráfico G , puntos en la recta [1, . . . , r], entonces la representación del vértice v es el intervalo . Luego, la descomposición en árbol de los vértices que contienen v corresponde a la representación (es decir, puntos finales) del intervalo para v . El gráfico de intersección de intervalos formado a partir de los vértices de G es un gráfico de intervalos que contiene a G como subgráfico. Sus camarillas máximas están dadas por el conjunto de intervalos que contienen los puntos de representación, y su tamaño de camarilla más grande es uno mayor que el ancho del camino del gráfico G .

En el otro sentido, si G es un subgrafo de un grafo de intervalo con número de camarilla p  + 1, entonces G tiene una descomposición en árbol de ancho p cuyos vértices están dados por las camarillas máximas del grafo 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 en árbol con cinco vértices correspondientes a las cinco camarillas máximas ABC , ACD , CDE , CDF y FG . El tamaño de la camarilla máxima es tres, y el ancho de esta descomposición en árbol es dos.

Esta equivalencia entre el ancho del camino y el grosor del intervalo es una analogía cercana 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 subgráfico. Los gráficos de intervalos son un caso especial de los gráficos de cuerdas, y los gráficos de cuerdas se pueden representar como gráficos de intersección de subárboles de árboles generales, lo que generaliza el enfoque en el que los gráficos de intervalos se interpretan como gráficos de intersección de subtrayectorias.

Cantidad de división de vértice

Suponga que los vértices del gráfico G están ordenados linealmente . Entonces la magnitud de la partición de vértice de G es el número más pequeño s tal que, para cada vértice v , como máximo s vértices preceden a v en el ordenamiento que tiene v o uno de los siguientes vértices en su vecindad. El valor de división de vértices del gráfico G es el valor mínimo de división de vértices de cualquier orden lineal del gráfico G . El valor de división de vértices fue introducido por Ellis, Sudborough y Turner [15] y es igual al ancho de ruta del gráfico G [16] [17] . Esto se deriva de la equivalencia mencionada anteriormente de gráficos de intervalos y números de camarilla: si G es un subgráfico de un gráfico de intervalos I , representado (como en la figura) de tal manera que todos los extremos de los intervalos son diferentes, entonces el orden de los extremos izquierdos de los intervalos del gráfico I tiene un valor de separación de vértices uno menos que los números de camarilla de la columna I. En la otra dirección, a partir de una ordenación lineal de G , se puede obtener una representación de intervalo en la que el extremo izquierdo del intervalo para el vértice v es la posición en la ordenación, y el extremo derecho es la posición del último vecino de v en el ordenamiento

Número de búsqueda de vértice

El juego de búsqueda superior en un gráfico es un tipo de juego de persecución y evitación en el que varios perseguidores trabajan juntos para localizar a un fugitivo escondido en un gráfico. Los perseguidores se colocan en los vértices del gráfico, mientras que el fugitivo se puede ubicar en cualquier borde del gráfico, su ubicación y movimientos no son visibles para los perseguidores. Durante el siguiente movimiento, algunos (o todos) de los perseguidores pueden moverse (arbitrariamente, no necesariamente a lo largo de los bordes) de un vértice a otro, y el fugitivo luego se mueve a lo largo de cualquier camino en el gráfico, pero no puede pasar a través de los vértices ocupados por el perseguidores Se atrapa a un fugitivo cuando ambos extremos del arco en el que se encuentra están ocupados por perseguidores. El número de búsqueda de vértices de un gráfico es el número mínimo de perseguidores necesarios para garantizar la captura de un fugitivo, independientemente de su comportamiento. Como mostraron Kyrouzis y Panadimitriou [18] , el número de búsqueda de vértice de un gráfico es igual al grosor de su intervalo. La estrategia óptima para los perseguidores son los movimientos en los que los perseguidores forman sucesivamente conjuntos separados de ordenación lineal con la mínima separación de vértices.

Bordes

Cualquier gráfico con n vértices y ancho de camino k tiene como máximo k ( n − k + ( k − 1)/2)) bordes, y los gráficos máximos con ancho de camino k (gráficos a los que no se les puede agregar un borde sin aumentar el camino ancho) tienen precisión es el número de aristas. El gráfico máximo con ancho de ruta k debe ser una ruta k o una oruga k , es decir uno de los dos tipos especiales de k -tree. Un árbol k es un grafo cordal con exactamente n − k camarillas máximas , cada una de las cuales contiene k + 1 vértices. En un árbol k que no es en sí mismo una camarilla ( k + 1) , cada camarilla máxima divide el gráfico en dos o más componentes o contiene un vértice de una sola hoja, un vértice que pertenece solo a una camarilla máxima. Un k -camino es un k -árbol con dos hojas como máximo, y un k -oruga es un k - árbol que se puede dividir en un k -camino y un conjunto de k -hojas, cada uno adyacente al separador k-clique del camino k . En particular, los gráficos máximos de ancho de camino uno son exactamente gráficos de oruga [19] .

Dado que las descomposiciones de ruta son casos especiales de descomposición de árbol, el ancho de ruta de cualquier gráfico es mayor o igual que el ancho de su árbol . El ancho de ruta también es menor o igual que el ancho de corte, el número mínimo de aristas que intersecan cualquier corte entre vértices con un índice más bajo y un índice más alto en el ordenamiento lineal óptimo de los vértices del gráfico. Esto se deriva del hecho de que la magnitud de la división de vértices, el número de vértices con un índice más bajo con vecinos con un índice más alto, no es mayor que el número de aristas cortantes [20] [21] . Por la misma razón, el ancho de corte no excede el ancho del camino multiplicado por el grado máximo de vértices en el gráfico dado [22] [23] .

Cualquier bosque con n vértices tiene un ancho de ruta de O(log  n ) [24] [25] [26] . Para un bosque, siempre se puede encontrar un número constante de vértices cuya eliminación da como resultado un bosque que se puede dividir en dos bosques más pequeños con un máximo de 2 n /3 vértices en cada uno de estos bosques. El ordenamiento lineal formado al aplicar recursivamente tal partición tiene un número de búsqueda logarítmico para los vértices. La misma técnica, aplicada a la descomposición en árbol de un gráfico, muestra que si el ancho del árbol de un gráfico G de n vértices es t , entonces el ancho del camino de G es O( t  log  n ) [27] [28] . Debido a que los gráficos de planos exteriores , los gráficos paralelos en serie y los gráficos de Halin tienen un ancho de árbol acotado, todos tienen un ancho de ruta logarítmico máximo.

Además de estar relacionado con el ancho del árbol, el ancho de la ruta está relacionado con el ancho del clic y el ancho del corte a través de gráficos de líneas . Un 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 si las dos aristas correspondientes tienen G extremos en común. Cualquier familia de gráficos tiene un ancho de ruta acotado si y solo si sus gráficos de línea tienen un ancho de camarilla lineal acotado, donde el ancho de camarilla lineal reemplaza la operación de unión en la definición de ancho de camarilla con la operación de adjuntar un único vértice nuevo [29] . Si un gráfico conectado con tres o más vértices tiene un grado máximo de 3, su ancho de corte es igual a la división de vértices de su gráfico lineal [30] .

En cualquier gráfico plano , el ancho de la ruta es, en el peor de los casos, proporcional a la raíz cuadrada del número de vértices [31] . Una forma de encontrar una descomposición de caminos con este ancho es (similar a la descomposición de caminos de ancho logarítmico descrita anteriormente) usar el teorema de partición plana para encontrar el conjunto de vértices O(√ n ) cuya eliminación divide el gráfico en dos subgrafos con un máximo de 2 n /3 vértices en cada uno, y conecte las descomposiciones de camino construidas recursivamente para estos dos subgrafos. La misma técnica se aplica a cualquier clase de gráficos para los que se cumple un teorema de partición similar [32] . Dado que cualquier familia de grafos cerrados tomando menores, como en el caso de grafos planos, tiene un conjunto de vértices divisorios de tamaño O(√ n ) [33] , se deduce que el ancho de ruta de los grafos en cualquier familia fija cerrada bajo menores es de nuevo O(√ n ). 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 en un intervalo cuyos límites dependen linealmente de los valores; dichos límites se conocen para gráficos planos exteriores doblemente conectados [34] [35] y para politopos . gráficos [36] [37] . Para gráficos planares doblemente conectados, el ancho de ruta del gráfico dual es menor que el ancho de ruta del gráfico lineal [38] . Sigue siendo una pregunta abierta si los anchos de ruta del gráfico plano y su dual están siempre en límites lineales para el resto de los casos.

Para algunas clases de gráficos, se ha demostrado que el ancho del camino y el ancho del árbol son siempre iguales entre sí; esto es cierto para cographs [39] , gráficos de permutación [40] , complementos de gráficos de comparabilidad [41] y gráficos de comparabilidad de órdenes de intervalo [42] .

En cualquier gráfico cúbico , o más generalmente cualquier gráfico con un grado de vértice máximo de 3, 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. Hay gráficos cúbicos con un ancho de camino de 0.082 n , pero no se sabe cómo cerrar esta brecha entre el límite inferior y el límite superior n /6 [43] .

Cálculo de descomposiciones de rutas

Determinar si el ancho de ruta excede un valor dado k para un gráfico dado es NP-completo si k es una entrada [6] . Los límites de tiempo más conocidos ( en el peor de los casos ) para calcular el ancho de ruta de un gráfico arbitrario con n vértices son O(2 n  n c ) para alguna constante c [44] . Sin embargo, se sabe que algunos algoritmos de descomposición de rutas son más eficientes si el ancho de la ruta es pequeño, si la clase del gráfico de entrada está restringida o si es necesario aproximar el ancho de la ruta.

Resolubilidad paramétrica fija

El ancho de la ruta se puede resolver paramétricamente : para cualquier constante k , se puede verificar si el ancho de la ruta excede k y, si no lo hace, encontrar una descomposición de la ruta del ancho k en tiempo lineal [8] . En general, estos algoritmos funcionan en dos etapas. El primer paso utiliza la suposición de que el gráfico tiene un ancho de ruta k para encontrar una descomposición de ruta o descomposición de árbol. Esta descomposición no es óptima, pero su ancho puede estar limitado por una función de k . En la segunda etapa, se aplica un algoritmo de programación dinámica para encontrar la descomposición óptima. Sin embargo, los límites de tiempo para algoritmos conocidos de este tipo son exponenciales en k 2 y no tienen ningún interés práctico, excepto quizás para pequeños valores de k [45] . Para el caso k  = 2, Fleiter proporcionó un algoritmo de tiempo lineal basado en la descomposición estructural de gráficos con un ancho de ruta de 2 [46] .

Clases especiales de grafos

Bodlaender [9] dio una visión general de la complejidad de los problemas de ancho de ruta en varias clases especiales de gráficos. Determinar si el ancho de ruta de un gráfico G excede k sigue siendo un problema NP-completo si G se toma de gráficos de grado acotado [47] , gráficos planos [47] , gráficos planos de grado acotado [47] , gráficos cordales [48] , dominós cordales [49] , complementos de gráficos de comparabilidad [41] y gráficos bipartitos heredados de la distancia [50] . Esto implica inmediatamente que el problema también es NP-completo para familias de grafos que contienen grafos bipartitos heredados de la distancia , incluidos grafos bipartitos, grafos bipartitos cordales, grafos heredados de la distancia y grafos circulares [50] .

Sin embargo, el ancho de la ruta se puede calcular en tiempo lineal para árboles y bosques [10] . Es posible calcular este valor en tiempo polinomial para grafos de ancho de árbol acotado, que incluyen grafos secuenciales paralelos , grafos planos externos y grafos de Halin [8] , así como grafos divididos [51] [48] , complementos de grafos cordales [ 52] , gráficos de permutación [40] , cographs [39] , gráficos de arco circular [53] , gráficos de comparabilidad de orden de intervalo [42] y, por supuesto , gráficos de intervalo en sí mismos , porque para ellos el ancho de ruta es simplemente uno menos que la cobertura máxima de intervalo número de cualquier punto en el gráfico de representación de intervalos.

Algoritmos de aproximación

Un problema NP-difícil es la aproximación del ancho de ruta de un gráfico por una constante aditiva [7] . El coeficiente de aproximación más conocido de los algoritmos de aproximación de tiempo polinomial para el ancho de ruta es O((log  n ) 3/2 ) [54] . Los primeros algoritmos de aproximación de ancho de ruta se pueden encontrar en Bodlaender, Gilbert, Hafsteinsson, Klox [7] y Gooh [55] . Para una aproximación de clases restringidas de gráficos, consulte el libro de Clox y Bodlaender [51] .

Contar menores

Un menor de un grafo G es otro grafo formado a partir de G contrayendo aristas, borrando aristas y vértices. Los menores de Graph tienen una teoría profunda en la que algunos resultados importantes usan el ancho de ruta.

Exclusión forestal

Si la familia F de grafos se cierra bajo la operación de tomar menores (cualquier menor de un miembro de la familia F también está contenido en F ), entonces por el teorema de Robertson-Seymour, la familia F puede caracterizarse como grafos que no contienen menores de edad de X , donde X es un conjunto finito de menores prohibidos [ 56 ] . Por ejemplo, el teorema de Wagner establece que las gráficas planas son gráficas que no contienen ni la gráfica completa K 5 ni la gráfica bipartita completa K 3,3 como menores. En muchos casos, las propiedades de F y las propiedades de X están íntimamente relacionadas, y el primer resultado de este tipo lo obtuvieron Robertson y Seymour [2] y relaciona la existencia de un ancho de vía acotado con la presencia de un bosque en el familia de menores prohibidos. Más específicamente, definimos una familia F de gráficos con un ancho de ruta acotado si existe una constante p tal que cualquier gráfico en F tenga un ancho de ruta como máximo p . Entonces, una familia F cerrada a menores tiene un ancho de ruta acotado si y solo si el conjunto X de menores prohibidos para F incluye al menos un bosque.

En una dirección, este resultado se puede probar directamente, a saber, que si X no contiene al menos un bosque, entonces los gráficos libres de X -menor no tienen un ancho de ruta acotado. En este caso, los gráficos libres de X -menor incluyen todos los bosques y, en particular, los árboles binarios perfectos . Pero los árboles binarios perfectos con 2k  + 1 niveles tienen un ancho de ruta k , por lo que en este caso los gráficos libres de X -menor tienen un ancho de ruta ilimitado. En la dirección opuesta, si X contiene un bosque con n vértices, entonces los gráficos libres de X -menor tienen un ancho de ruta como máximo n  − 2 [57] [58] [59] .

Estimaciones de ancho de vía

La propiedad de tener un ancho de ruta como máximo p es, en sí misma, una propiedad cerrada menor: si G tiene una descomposición de ruta con ancho como máximo p , entonces la misma descomposición de ruta sigue siendo verdadera si se elimina cualquier borde de G , también como cualquier vértice, se puede eliminar de G y su descomposición de trayectoria sin aumentar el ancho. También se puede completar una contracción de borde sin aumentar el ancho de la descomposición fusionando los subtrayectos que representan los dos extremos del borde que se está contrayendo. Por lo tanto, los grafos con ancho de ruta como máximo p pueden caracterizarse por el conjunto X p de menores prohibidos [56] [16] [60] [61] .

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 1 consta de dos gráficos, un árbol con siete vértices y un triángulo K 3 . Sin embargo, el conjunto de árboles en X p se puede describir exactamente: estos son exactamente los árboles que se pueden formar a partir de tres árboles de X p  − 1 formando una nueva raíz y conectándola con bordes a vértices elegidos arbitrariamente de árboles más pequeños. Por ejemplo, un árbol con siete vértices en X 1 se forma a partir de árboles con dos vértices (una arista) de X 0 . Con base en esta construcción, se puede demostrar que el número de menores prohibidos en X p no es menor que ( p !) 2 [16] [60] [61] . Se ha calculado el conjunto completo X 2 de menores prohibidos para grafos con ancho de ruta 2. Este conjunto contiene 110 gráficos diferentes [62] .

Teoría estructural

El teorema de la estructura de grafos para familias de grafos cerrados menores establece que para cualquier familia F en la que los grafos se puedan descomponer en sumas de clique, grafos 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 de la camarilla. Un vértice es un vértice adyacente a todos los vértices del componente, y un vórtice es un gráfico de ancho de camino acotado que se pega a la cara del componente con una inyección de género acotado. El orden cíclico de los vértices alrededor de la cara en la que se anida el vórtice debe ser compatible con la descomposición en árbol del vórtice en el sentido de que romper el ciclo para formar un orden lineal debe dar como resultado un orden con una cantidad limitada de separación de vértices [ 5] . Esta teoría, en la que el ancho de ruta está estrechamente relacionado con familias arbitrarias de grafos cerrados por menores, tiene una importante aplicación algorítmica [63] .

Aplicaciones

VLSI

Durante el desarrollo de VLSI , el problema de dividir vértices se estudió originalmente como una forma de dividir cadenas en subsistemas más pequeños con una pequeña cantidad de componentes en el límite entre sistemas [47] .

Otsuki, Mori, Kuh y Kashiwabara [64] utilizaron el espesor de intervalo para modelar el número de conductores necesarios en una disposición unidimensional de circuitos VLSI formados por múltiples módulos que se conectarán mediante un sistema de red. En su modelo, se puede formar un gráfico en el que los vértices representan cadenas y en el que dos vértices están conectados por una arista si sus cadenas están conectadas al mismo módulo. Es decir, si los módulos y las cadenas se entienden como vértices e hiperaristas de una hipergrafía , entonces el grafo formado a partir de ellos es una gráfica lineal de una hipergrafía . La representación del intervalo del supergráfico de este gráfico de líneas, junto con la coloración del supergráfico, describe la disposición de las redes a lo largo de las pistas horizontales (una pista para cada color), de modo que los módulos se pueden organizar a lo largo de las pistas en un orden lineal y conectarse al redes deseadas. Del hecho de que los gráficos de intervalos son perfectos [65] , se deduce que el número de colores requerido para un diseño óptimo de este tipo es igual al número de camarilla del complemento de intervalo del gráfico de cadena.

El apilamiento de matriz de interruptores [66] es un tipo específico de apilamiento CMOS VLSI para circuitos de álgebra lógica . En el apilamiento matricial de interruptores, la señal se propaga a lo largo de "líneas" (segmentos verticales), mientras que cada interruptor está formado por una secuencia de elementos ubicados en un segmento horizontal. Por lo tanto, los segmentos horizontales de cada interruptor deben cruzarse con los segmentos verticales de cada línea que sirve como entrada o salida del interruptor. Al igual que en los apilamientos de Otsuki, Mori, Kuha y Kashiwabara [64] , este tipo de apilamiento, que minimiza el número de líneas verticales, se puede calcular calculando el ancho de ruta de un gráfico que tiene líneas como vértices y un par de líneas que pertenecen a un interruptor como bordes [67] . El mismo enfoque algorítmico también se puede utilizar para modelar problemas de apilamiento en circuitos integrados de lógica programable [68] [69] .

Visualización de gráficos

Pathwidth tiene varias aplicaciones de visualización de gráficos :

• Los gráficos mínimos que tienen un número dado de intersecciones tienen un ancho de ruta limitado por una función del número de intersecciones [70] .
• El número de líneas paralelas en las que se pueden colocar los vértices del árbol sin cruzar los bordes (bajo varias restricciones naturales sobre las formas en que se pueden colocar los vértices adyacentes en las líneas dada una secuencia de líneas) es proporcional al ancho de la ruta del árbol [71] .
• El dibujo de un gráfico G a nivel h con intersección k es una disposición de los vértices del gráfico G en h diferentes líneas horizontales con bordes en forma de caminos monótonos (representados por líneas discontinuas) entre las líneas, en las que hay al menos la mayoría de las k intersecciones. Los gráficos con esta representación tienen un ancho de ruta acotado por una función de h y k . Así, si los valores de h y k son constantes, es posible determinar en tiempo lineal si el gráfico tiene un dibujo de nivel h k cruzado [72] .
• Un gráfico con n vértices y ancho de camino p se puede incrustar en una red tridimensional de tamaño p × p × n de tal manera que no haya dos bordes (representados por segmentos de línea recta entre puntos de red) que se crucen entre sí. Por lo tanto, los gráficos de ancho de ruta acotado tienen incrustaciones de este tipo con volumen lineal [73] .

Diseño del compilador

Al traducir lenguajes de programación de alto nivel, el ancho de ruta surge en el problema de reordenar el código lineal (es decir, código sin lógica de control - transiciones y bucles) de tal manera que todos los valores calculados en el código puedan estar en registros de máquina , y no forzado a la memoria principal. En esta aplicación, el código traducido se representa como un gráfico acíclico dirigido (DAG), en el que los vértices representan los valores de entrada para el código y los valores calculados como resultado de las operaciones dentro del código. Un borde del nodo x al nodo y en este NAG representa el hecho de que el valor x es una de las entradas de la operación y . La ordenación topológica de los vértices en este NAG representa la ordenación correcta del código, y el número de registros necesarios para ejecutar el código en ese orden viene dado por la división de vértices de la ordenación [74] .

Para cualquier número fijo w de registros en una máquina, se puede determinar en tiempo lineal si una pieza de código lineal se puede reordenar de modo que el código requiera como máximo w registros. Si la separación de vértices de una ordenación topológica es como máximo w , la separación mínima de vértices entre todas las ordenaciones no puede ser mayor, por lo que los gráficos no dirigidos formados ignorando la orientación de la NAG descrita anteriormente deben tener un ancho de ruta como máximo w . Se puede verificar si esto es cierto utilizando algoritmos conocidos de ancho de ruta decidible de parámetro fijo y, si es cierto, encontrar una descomposición de ruta para gráficos no dirigidos en tiempo lineal, suponiendo que w es una constante. Una vez que se ha encontrado la descomposición del árbol, el ordenamiento topológico con ancho w (si existe) se puede encontrar usando programación dinámica, nuevamente en tiempo lineal [74] .

Lingüística

Karnai y Tutsa [75] describieron la aplicación del ancho de ruta al procesamiento del lenguaje natural . En esta aplicación, las oraciones se modelan como gráficos donde los vértices representan palabras y los bordes representan relaciones entre palabras. Por ejemplo, si un adjetivo modifica un sustantivo, entonces el gráfico tiene un borde entre las dos palabras. Debido a la capacidad limitada de la memoria humana a corto plazo, Miller [76] , Kornai y Tutsa argumentan que este gráfico debe tener un ancho de ruta limitado (más específicamente, afirman que este ancho de ruta no excede seis), de lo contrario las personas no podrían para reconocer el habla correctamente.

Algoritmos Exponenciales

Muchos problemas de la teoría de grafos se pueden resolver de manera efectiva en gráficos con un ancho de ruta pequeño utilizando programación dinámica , basada en la descomposición de la ruta del gráfico [11] . Por ejemplo, si se da el ordenamiento lineal de los vértices de un grafo G con n vértices y el valor de separación de vértices es igual a w , entonces es posible encontrar el conjunto independiente más grande del grafo G en O(2 w n ) tiempo [43] . En un gráfico con ancho de ruta acotado, este enfoque conduce a algoritmos parametrizados de ancho de ruta decidibles paramétricamente fijos [67] . Tales resultados no se encuentran a menudo en la literatura, ya que pertenecen a un grupo de algoritmos similares parametrizados por el ancho del árbol. Sin embargo, el ancho de ruta aparece incluso en algoritmos de programación dinámica basados ​​en el ancho de árbol cuando se mide la complejidad de la capacidad de estos algoritmos [12] .

La misma técnica de programación dinámica se puede aplicar a gráficos con un ancho de ruta ilimitado, lo que lleva a algoritmos que resuelven problemas no parametrizados en gráficos en tiempo exponencial . Por ejemplo, combinar el enfoque de programación dinámica con el hecho de que los gráficos cúbicos tienen un ancho de ruta de n /6 + o( n ) muestra que para gráficos cúbicos el conjunto independiente máximo se puede construir en O(2 n /6 + o( n ) ) tiempo, que es más rápido que los métodos previamente conocidos [43] . Un enfoque similar conduce a algoritmos de tiempo exponencial mejorados para los problemas de corte máximo y conjunto dominante mínimo para gráficos cúbicos [43] y para algunos otros problemas de optimización NP-hard [77] [78] .

Véase también

• Dimensión de gráfico de intervalo , otra forma de medir la complejidad de gráficos arbitrarios en términos de gráficos de intervalo
• Profundidad del árbol , un número que está acotado para familias de gráficos cerradas menores si y solo si la familia no contiene una ruta
• Degeneración , una medida de la dispersión de un gráfico que no es mayor que el ancho de ruta del gráfico
• Graph ribbon width , otro problema de optimización NP-completo usando apilamientos de gráficos lineales
• Número de Strahler , una medida de la densidad de árboles enraizados, definida de manera similar al ancho de ruta de los árboles no dirigidos

Notas

1. ↑ Diestel, Kühn, 2005 .
2. ↑ 1 2 3 4 5 Robertson, Seymour, 1983 .
3. ↑ 1 2 Bodlaender, 1998 .
4. ↑ Muchos de los términos utilizados en el artículo se pueden encontrar en la introducción a la disertación de F. V. Fomin (( Fomin 1996 ))
5. ↑ 12 Robertson , Seymour, 2003 .
6. ↑ 1 2 Kashiwabara, Fujisawa, 1979 ; Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979 ; Lengauer 1981 ; Arnborg, Corneil, Proskurowski, 1987 .
7. ↑ 1 2 3 Bodlaender, Gilbert, Hafsteinsson, Kloks, 1992 .
8. ↑ 1 2 3 Bodlaender (1996 ); Bodlaender, Kloks (1996 )
9. ↑ 1 2 Bodlaender, 1994 .
10. ↑ 12 Möhring , 1990 ; Scheffler, 1990 ; Ellis, Sudborough, Turner, 1994 ; Coudert, Huc, Mazaurico, 1998 ; Peng, Ho, Hsu, Ko, Tang, 1998 ; Skodinis, 2000 ; Skodinis (2003 ).
11. ↑ 12 Arnborg , 1985 .
12. ↑ 1 2 Aspvall, Proskurowski, Telle, 2000 .
13. ↑ Bodlaender, 1994 , pág. 1–2.
14. ↑ Bodlaender, 1998 , pág. 13, Teorema 29.
15. ↑ Ellis, Sudborough, Turner, 1983 .
16. ↑ 1 2 3 Kinnersley, 1992 .
17. ↑ Bodlaender, 1998 , pág. Teorema 51.
18. ↑ Kirousis, Papadimitriou, 1985 .
19. ↑ Proskurowski, Telle, 1999 .
20. ↑ Koraj, Solel, 1993 , p. 99, Lema 3.
21. ↑ Bodlaender, 1998 , pág. 24, Teorema 47.
22. ↑ Koraj, Solel, 1993 , p. 99, Lema 1.
23. ↑ Bodlaender, 1998 , pág. 24, Teorema 49.
24. ↑ Koraj, Solel, 1993 , p. 99, Teorema 5.
25. ↑ Bodlaender, 1998 , pág. 30, Teorema 66.
26. ↑ Scheffler (1992 ) proporciona un límite más fuerte en el  ancho de ruta log 3 (2 n + 1) de un bosque de n vértices.
27. ↑ Koraj, Solel, 1993 , p. 100, Teorema 6.
28. ↑ Bodlaender, 1998 , pág. 10, Corolario 24.
29. ↑ Gurski, Wanke, 2007 .
30. ↑ Golovach, 1993 .
31. ↑ Bodlaender, 1998 , pág. 10, Corolario 23.
32. ↑ Bodlaender, 1998 , pág. 9, Teorema 20.
33. ↑ Alon, Seymour, Thomas, 1990 .
34. ↑ Bodlaender, Fomin, 2002 .
35. ↑ Coudert, Huc, Sereni, 2007 .
36. ↑ Fomin, Thilikos, 2007 .
37. ↑ Amini, Huc, Perennes, 2009 .
38. ↑ Fomín, 2003 .
39. ↑ 1 2 Bodlaender, Möhring, 1990 .
40. ↑ 1 2 Bodlaender, Kloks, Kratsch, 1993 .
41. ↑ 1 2 Habib, Möhring, 1994 .
42. ↑ 12 Garbe , 1995 .
43. ↑ 1 2 3 4 Fomin, Hoie, 2006 .
44. ↑ Fomin, Kratsch, Todinca, Villanger, 2008 .
45. ↑ Downey, Fellows, 1999 , pág. 12
46. ↑ de Fluiter, 1997 .
47. ↑ 1 2 3 4 Monien, Sudborough, 1988 .
48. ↑ 12 Gusted , 1993 .
49. ↑ Kloks, Kratsch, Müller, 1995 . Un dominó cordal es un grafo cordal en el que cualquier vértice pertenece como máximo a dos camarillas máximas
50. ↑ 1 2 Kloks, Bodlaender, Müller, Kratsch, 1993 .
51. ↑ 1 2 Kloks, Bodlaender, 1992 .
52. ↑ Garbe (1995 ) atribuye este resultado a las tesis de disertación de 1993 de Ton Clox. El algoritmo de tiempo polinomial de Garbe para gráficos de comparabilidad de órdenes de intervalos generaliza este resultado, ya que cualquier gráfico cordal debe ser un gráfico de comparabilidad de este tipo.
53. ↑ Suchan, Todinca, 2007 .
54. ↑ Feige, Hajiaghayi, Lee, 2005 .
55. ↑ Guha, 2000 .
56. ↑ 12 Robertson , Seymour, 2004 .
57. ↑ Bienstock, Robertson, Seymour, Thomas, 1991 .
58. ↑ Diestel, 1995 .
59. ↑ Cattell, Dinneen, Fellows, 1996 .
60. ↑ 1 2 Takahashi, Ueno, Kajitani, 1994 .
61. ↑ 1 2 Bodlaender, 1998 , p. ocho.
62. ↑ Kinnersley, Langston, 1994 .
63. ↑ Demaine, Hajiaghayi, Kawarabayashi, 2005 .
64. ↑ 1 2 Ohtsuki, Mori, Kuh, Kashiwabara, Fujisawa, 1979 .
65. ↑ Bergé, 1967 .
66. ↑ López, Ley, 1980 .
67. ↑ 12 becarios , Langston, 1989 .
68. ↑ Mohring, 1990 .
69. ↑ Ferreira, Canción, 1992 .
70. ↑ Hlineny, 2003 .
71. ↑ Sudermann, 2004 .
72. ↑ Dujmović, Fellows, Kitching et al., 2008 .
73. ↑ Dujmovic, Morin, Wood, 2003 .
74. ↑ 1 2 Bodlaender, Gustedt, Telle, 1998 .
75. ↑ Kornai, Tuza, 1992 .
76. ↑ Molinero, 1956 .
77. ↑ Kneis, Mölle, Richter, Rossmanith, 2005 .
78. ↑ Björklund, Husfeldt, 2008 .

Literatura

• Noga Alon, Paul Seymour, Robin Thomas. proc. 22º ACM Symp. sobre Teoría de la Computación (STOC 1990) . - 1990. - S.  293 -299. — ISBN 0897913612 . -doi : 10.1145/ 100216.100254 . .
• Omid Amini, Florian Huc, Stephane Perennes. Sobre el ancho de ruta de grafos planos // SIAM Journal on Discrete Mathematics . - 2009. - T. 23 , núm. 3 . - S. 1311-1316 . -doi : 10.1137/ 060670146 . .
• Stefan Arnborg. Algoritmos eficientes para problemas combinatorios en grafos con descomposición acotada: una encuesta // BIT. - 1985. - T. 25 , núm. 1 . - S. 2-23 . -doi : 10.1007/ BF01934985 . .
• Stefan Arnborg, Derek G. Corneil, Andrzej Proskurowski. Complejidad de encontrar incrustaciones en un árbol $k$ // SIAM Journal on Algebraic and Discrete Methods. - 1987. - T. 8 , núm. 2 . - S. 277-284 . -doi : 10.1137/ 0608024 . .
• Bengt Aspvall, Andrzej Proskurowski, Jan Arne Telle. Requisitos de memoria para cálculos de tablas en algoritmos de árboles k parciales // Algorithmica . - 2000. - T. 27 , núm. 3 . - S. 382-394 . -doi : 10.1007/ s004530010025 . .
• Claude Bergé. Teoría de Grafos y Física Teórica. - Nueva York: Academic Press, 1967. - P. 155-165. .
• .
• Andreas Björklund, Thore Husfeldt. Algoritmos exactos para la satisfacibilidad exacta y el número de coincidencias perfectas // Algorithmica . - 2008. - T. 52 , núm. 2 . - S. 226-249 . -doi : 10.1007/ s00453-007-9149-8 . .
• Hans L. Bodlaender. Una guía turística a través del ancho de los árboles // Acta Cybernetica. - 1994. - T. 11 .
• Hans L. Bodlaender. Desarrollos en informática teórica (Proc. 7.º Encuentro internacional de jóvenes informáticos, Smolenice, 16–20 de noviembre de 1992) / Jürgen Dassow, Alisa Kelemenová. - Gordon y Breach, 1994. - V. 6. - S. 1-20. - (Temas de Matemática Informática). .
• Hans L. Bodlaender. Un algoritmo de tiempo lineal para encontrar descomposiciones de árbol de ancho de árbol pequeño // SIAM Journal on Computing . - 1996. - T. 25 , núm. 6 _ - S. 1305-1317 . -doi : 10.1137/ S0097539793251219 . .
• Hans L. Bodlaender. Un k -arboretum parcial de gráficos con ancho de árbol acotado  // Ciencias de la computación  teórica. - 1998. - vol. 209 , edición. 1-2 . - Pág. 1-45 . - doi : 10.1016/S0304-3975(97)00228-4 . .
• Hans L. Bodlaender, Fedor V. Fomin. Aproximación del ancho de ruta de gráficos de planos exteriores // Journal of Algorithms. - 2002. - T. 43 , núm. 2 . - S. 190-200 . - doi : 10.1016/S0196-6774(02)00001-9 . .
• Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, Ton Kloks. Conceptos de Teoría de Grafos en Informática. - 1992. - T. 570. - S. 1-12. — ( Apuntes de clase en informática ). - ISBN 978-3-540-55121-8 . -doi : 10.1007 / 3-540-55121-2_1 . .
• Hans L. Bodlaender, Jens Gustedt, Jan Arne Telle. proc. 9º Simposio ACM–SIAM sobre Algoritmos Discretos (SODA '98). - 1998. - S. 574-583. .
• Hans L. Bodlaender, Ton Kloks. Algoritmos eficientes y constructivos para el ancho de ruta y el ancho de árbol de gráficos // Journal of Algorithms. - 1996. - T. 21 , núm. 2 . - S. 358-402 . -doi : 10.1006/ jagm.1996.0049 . .
• Hans L. Bodlaender, Ton Kloks, Dieter Kratsch. proc. XX Coloquio Internacional de Autómatas, Lenguajes y Programación (ICALP 1993) . - Springer-Verlag, 1993. - T. 700. - S. 114-125. — (Apuntes de clase en informática). — ISBN 978-3-540-56939-8 . -doi : 10.1007/ 3-540-56939-1_66 . .
• Hans L. Bodlaender, Rolf H. Möhring. proc. 2º Taller Escandinavo de Teoría de Algoritmos . - Springer-Verlag, 1990. - T. 447. - S. 301-309. — (Apuntes de clase en informática). — ISBN 978-3-540-52846-3 . -doi : 10.1007 / 3-540-52846-6_99 . .
• Kevin Cattell, Michael J. Dinneen, Michael R. Fellows. Un algoritmo simple de tiempo lineal para encontrar descomposiciones de rutas de ancho pequeño // Letras de procesamiento de información . - 1996. - T. 57 , núm. 4 . - S. 197-203 . -doi : 10.1016 / 0020-0190(95)00190-5 . .
• David Coudert, Florian Huc, Dorian Mazauric. proc. 22 Int. Síntoma Computación distribuída. - Springer-Verlag, 1998. - T. 5218. - S. 500-501. — (Apuntes de clase en informática). - ISBN 978-3-540-87778-3 . -doi : 10.1007 / 978-3-540-87779-0_36 . .
• David Coudert, Florian Huc, Jean-Sébastien Sereni. Ancho de ruta de gráficos de planos exteriores // Journal of Graph Theory . - 2007. - T. 55 , núm. 1 . - S. 27-41 . -doi : 10.1002/ jgt.20218 . .
• Reinhard Diestel. Graph Minors I: una breve prueba del teorema del ancho de la ruta // Combinatoria, probabilidad y computación . - 1995. - T. 4 , núm. 1 . - S. 27-30 . -doi : 10.1017/ S0963548300001450 . .
• Reinhard Diestel, Daniela Kühn. Graficar jerarquías menores // Matemática Aplicada Discreta . - 2005. - T. 145 , núm. 2 . - S. 167-182 . -doi : 10.1016/ j.dam.2004.01.010 . .
• Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi. proc. 46º Simposio IEEE sobre Fundamentos de Ciencias de la Computación (FOCS 2005) . - 2005. - S. 637-646. — ISBN 0-7695-2468-0 . -doi : 10.1109/ SFCS.2005.14 . .
• Rod G. Downey, Michael R. Fellows. Complejidad parametrizada. - Springer-Verlag, 1999. - ISBN 0-387-94883-X . .
• V. Dujmović, M. R. Fellows, M. Kitching, G. Liotta, C. McCartin, N. Nishimura, P. Ragde, F. Rosamond, S. Whitesides, David R. Wood. Sobre la complejidad parametrizada del dibujo de grafos en capas // Algorithmica . - 2008. - T. 52 , núm. 2 . - S. 267-292 . -doi : 10.1007/ s00453-007-9151-1 . .
• Vida Dujmovic, Pat Morin, David R. Wood. proc. 10º Simposio Internacional de Dibujo Gráfico (GD 2002) . - Springer-Verlag, 2003. - T. 2528. - S. 42-53. — (Apuntes de clase en informática). .
• JA Ellis, IH Sudborough, JS Turner. proc. 1983 Conferencia de Allerton. en Comunicación, Control y Computación. — 1983. . Citado por Monien & Sudborough (1988 ).
• JA Ellis, IH Sudborough, JS Turner. La separación de vértices y el número de búsqueda de un árbol // Información y Cómputo . - 1994. - T. 113 , núm. 1 . - S. 50-79 . -doi : 10.1006/ inco.1994.1064 . .
• Uriel Feige, Mohammadtaghi Hajiaghayi, James R. Lee. proc. 37º Simposio ACM sobre Teoría de la Computación (STOC 2005) . - 2005. - S. 563-572. — ISBN 1581139608 . -doi : 10.1145/ 1060590.1060674 . .
• Michael R. Fellows, Michael A. Langston. proc. XXI Simposio ACM de Teoría de la Computación . - 1989. - S. 501-512. — ISBN 0897913078 . -doi : 10.1145/ 73007.73055 . .
• Afonso G. Ferreira, Siang W. Song. proc. 1er Simposio Latinoamericano de Informática Teórica (LATIN '92). - Springer-Verlag, 1992. - T. 583. - S. 139-153. — (Apuntes de clase en informática). — ISBN 3-540-55284-7 . -doi : 10.1007/ BFb0023825 . .
• Babette de Fluiter. Algoritmos para gráficos de ancho de árbol pequeño . - Universidad de Utrecht , 1997. - (Tesis doctoral). — ISBN 90-393-1528-0 . .
• Fedor V. Fomin. Ancho de ruta de gráficos planos y lineales // Gráficos y combinatoria . - 2003. - T. 19 , núm. 1 . - S. 91-99 . -doi : 10.1007 / s00373-002-0490-z . .
• Fedor V. Fomin, Kjartan Hoie. Ancho de ruta de grafos cúbicos y algoritmos exactos // Letras de procesamiento de información . - 2006. - T. 97 , núm. 5 . - S. 191-196 . -doi : 10.1016/ j.ipl.2005.10.012 . .
• Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, Yngve Villanger. Algoritmos exactos para el ancho del árbol y el relleno mínimo // SIAM Journal on Computing . - 2008. - T. 38 , núm. 3 . - S. 1058-1079 . -doi : 10.1137/ 050643350 . .
• Fedor V. Fomin, Dimitrios M. Thilikos. Sobre la dualidad propia del ancho de ruta en incrustaciones de gráficos poliédricos // Journal of Graph Theory . - 2007. - T. 55 , núm. 1 . - S. 42-54 . -doi : 10.1002/ jgt.20219 . .
• Renate Garbé. proc. 20th Workshop Internacional Conceptos Teóricos de Grafos en Informática (WG'94). - Springer-Verlag, 1995. - T. 903. - S. 26-37. — (Apuntes de clase en informática). — ISBN 978-3-540-59071-2 . -doi : 10.1007/ 3-540-59071-4_35 . .
• P. A. Golovach. El ancho de corte de un gráfico y el número de separación de vértices del gráfico lineal // Matemáticas discretas y aplicaciones. - 1993. - Vol. 3 , número. 5 . - S. 517-522 . -doi : 10.1515/ dma.1993.3.5.517 . .
• Sudipto Guha. proc. 41º Simposio IEEE sobre Fundamentos de Ciencias de la Computación (FOCS 2000) . - 2000. - Pág. 126. - ISBN 0-7695-0850-2 . -doi : 10.1109/ SFCS.2000.892072 . .
• Frank Gurski, Egon Wanke. Gráficos lineales de ancho de camarilla acotado // Matemáticas discretas . - 2007. - T. 307 , núm. 22 . - S. 2734-2754 . -doi : 10.1016/ j.disco.2007.01.020 . .
• Jens Gusted. Sobre el ancho de ruta de los grafos cordales // Matemática aplicada discreta . - 1993. - T. 45 , núm. 3 . - S. 233-248 . - doi : 10.1016/0166-218X(93)90012-D . .
• Michel Habib, Rolf H. Möhring. Treewidth de gráficos de cocomparabilidad y un nuevo parámetro teórico de orden // Order . - 1994. - T. 11 , núm. 1 . - S. 47-60 . -doi : 10.1007/ BF01462229 . .
• Petr Hlineny. Los gráficos críticos de números cruzados tienen un ancho de ruta acotado // Journal of Combinatorial Theory, Serie B . - 2003. - T. 88 , núm. 2 . - S. 347-367 . - doi : 10.1016/S0095-8956(03)00037-6 . .
• T. Kashiwabara, T. Fujisawa. proc. Simposio Internacional de Circuitos y Sistemas . - 1979. - S. 657-660. .
• Nancy G. Kinnersley. El número de separación de vértices de un gráfico es igual a su ancho de ruta // Letras de procesamiento de información . - 1992. - T. 42 , núm. 6 _ - S. 345-350 . -doi : 10.1016 / 0020-0190(92)90234-M . .
• Nancy G. Kinnersley, Michael A. Langston. Aislamiento del conjunto de obstrucciones para el problema de disposición de la matriz de compuertas // Matemática aplicada discreta . - 1994. - T. 54 , núm. 2-3 . - S. 169-213 . - doi : 10.1016/0166-218X(94)90021-3 . .
• Lefteris M. Kirousis, Christos H. Papadimitriou. Gráficas de intervalos y búsquedas // Matemáticas Discretas . - 1985. - T. 55 , núm. 2 . - S. 181-184 . - doi : 10.1016/0012-365X(85)90046-9 .  (enlace no disponible) .
• Ton Kloks, Hans L. Bodlaender. proc. 3er Simposio Internacional de Algoritmos y Computación (ISAAC'92). - Springer-Verlag, 1992. - T. 650. - S. 116-125. — (Apuntes de clase en informática). — ISBN 978-3-540-56279-5 . -doi : 10.1007/ 3-540-56279-6_64 . .
• T. Kloks, H. Bodlaender, H. Müller, D. Kratsch. proc. 1er Simposio Europeo de Algoritmos (ESA'93) . - Springer-Verlag, 1993. - T. 726. - S. 260-271. — (Apuntes de clase en informática). -doi : 10.1007 / 3-540-57273-2_61 . .
• Ton Kloks, Dieter Kratsch, H. Müller. proc. 20th Workshop Internacional Conceptos Teóricos de Grafos en Informática (WG'94). - Springer-Verlag, 1995. - T. 903. - S. 106-120. — (Apuntes de clase en informática). — ISBN 978-3-540-59071-2 . -doi : 10.1007/ 3-540-59071-4_41 . .
• Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith. proc. 31º Taller Internacional sobre Conceptos Teóricos de Grafos en Ciencias de la Computación (WG 2005). - Springer-Verlag, 2005. - T. 3787. - S. 385-396. — (Apuntes de clase en informática). - ISBN 978-3-540-31000-6 . -doi : 10.1007/ 11604686_34 . .
• Ephraim Kóraj, Nir Solel. Tree-width, path-width y cutwidth // Matemáticas Aplicadas Discretas . - 1993. - T. 43 , núm. 1 . - S. 97-101 . - doi : 10.1016/0166-218X(93)90171-J . .
• Andras Kornai, Zsolt Tuza. Estrechez, ancho de ruta y su aplicación en el procesamiento del lenguaje natural // Matemáticas discretas aplicadas . - 1992. - T. 36 , núm. 1 . - S. 87-92 . - doi : 10.1016/0166-218X(92)90208-R . .
• Tomás Lengauer. Guijarros blanco y negro y separación gráfica  // Acta Informatica . - 1981. - T. 16 , núm. 4 . - S. 465-475 . -doi : 10.1007/ BF00264496 . .
• Alexander D. López, Hung-Fai S. Law. Un método de diseño de matriz de puerta densa para MOS VLSI // Transacciones IEEE en dispositivos electrónicos. - 1980. - T. ED-27 , núm. 8 _ - S. 1671-1675 . -doi : 10.1109 / T-ED.1980.20086 . .
• Jorge A. Miller. El mágico número siete, más o menos dos // Reseña psicológica . - 1956. - T. 63 , núm. 2 . - S. 81-97 . -doi : 10.1037/ h0043158 . — PMID 13310704 . .
• Rolf H. Mohring. Teoría de grafos computacionales / G. Tinhofer, E. Mayr, H. Noltemeier, M. Sysło. - Springer-Verlag, 1990. - T. 7. - S. 17-51. - (Suplemento de Computación). — ISBN 3-211-82177-5 . .
• B. Monien, IH Sudborough. El corte mínimo es NP completo para árboles ponderados por borde  // Ciencias de la computación  teórica. - 1988. - vol. 58 , edición. 1-3 . - pág. 209-229 . -doi : 10.1016 / 0304-3975(88)90028-X . .
• Tatsuo Ohtsuki, Hajimu Mori, Ernest S. Kuh, Toshinobu Kashiwabara, Toshio Fujisawa. Asignación de puertas lógicas unidimensionales y gráficos de intervalos // Transacciones IEEE en circuitos y sistemas. - 1979. - T. 26 , núm. 9 _ - S. 675-684 . -doi : 10.1109/ TCS.1979.1084695 . .
• Sheng-Lung Peng, Chin-Wen Ho, Tsan-sheng Hsu, Ming-Tat Ko, Chuan Yi Tang. proc. 4to Int. Conf. Computación y Combinatoria (COCOON'98). - Springer-Verlag, 1998. - T. 1449. - S. 197-205. — (Apuntes de clase en informática). .
• Andrzej Proskurowski, Jan Arne Telle. Clases de grafos con modelos de intervalo restringido  // Informática  Teórica. - 1999. - vol. 3 . - pág. 167-176 . .
• Neil Robertson, Paul Seymour. gráficos menores. I. Excluyendo un bosque // Journal of Combinatorial Theory, Serie B . - 1983. - T. 35 , núm. 1 . - S. 39-61 . - doi : 10.1016/0095-8956(83)90079-5 . .
• Neil Robertson, Paul Seymour. gráficos menores. XVI. Excluyendo un gráfico no plano // Journal of Combinatorial Theory, Serie B . - 2003. - T. 89 , núm. 1 . - S. 43-76 . -doi : 10.1016 / S0095-8956(03)00042-X . .
• Neil Robertson, Paul D. Seymour. Gráfico Menores. XX. La conjetura de Wagner // Journal of Combinatorial Theory, Serie B . - 2004. - T. 92 , núm. 2 . - S. 325-357 . -doi : 10.1016/ j.jctb.2004.08.001 . .
• Petra Scheffler. Temas de Combinatoria y Teoría de Grafos / R. Bodendiek, R. Henn. - Physica-Verlag, 1990. - S. 613-620. .
• Petra Scheffler. Cuarto Simposio Checoslovaco sobre Combinatoria, Gráficos y Complejidad / Jaroslav Nešetřil, Miroslav Fiedler. — Elsevier, 1992. .
• Konstantin Skodinis. proc. 8º Simposio Europeo sobre Algoritmos (ESA 2000) . - Springer-Verlag, 2000. - T. 1879. - S. 403-414. — (Apuntes de clase en informática). - ISBN 978-3-540-41004-1 . -doi : 10.1007/ 3-540-45253-2_37 . .
• Konstantin Skodinis. 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. - 2003. - T. 47 , núm. 1 . - S. 40-59 . - doi : 10.1016/S0196-6774(02)00225-0 . .
• Karol Suchan, Ioan Todinca. proc. 33º Taller Internacional sobre Conceptos de Teoría de Grafos en Ciencias de la Computación (WG 2007). - Springer-Verlag, 2007. - T. 4769. - S. 258-269. — (Apuntes de clase en informática). -doi : 10.1007 / 978-3-540-74839-7_25 . .
• Mateo Suderman. Dibujos de árboles de ancho de ruta y en capas // Revista internacional de geometría computacional y aplicaciones . - 2004. - T. 14 , núm. 3 . - S. 203-225 . -doi : 10.1142/ S0218195904001433 . Archivado desde el original el 3 de mayo de 2003. .
• Atsushi Takahashi, Shuichi Ueno, Yoji Kajitani. Menores prohibidos acíclicos mínimos para la familia de grafos con ancho de ruta acotado // Matemáticas discretas . - 1994. - T. 127 , núm. 1-3 . - S. 293-304 . - doi : 10.1016/0012-365X(94)90092-2 . .
• FV Fomin. Problemas de seguimiento y búsqueda en grafos // Biblioteca Electrónica de Disertaciones. — 1996.