Hispanopedia Wiki
Articulo de referencia

Ancho de trayectoria

En teoría de grafos , una descomposición en caminos de un grafo G es, informalmente, una representación de G como un grafo de caminos "engrosado" [ 1 ] , y el ancho del camino d...

Hispanopedia WikiContenido en espanolLectura gratuita

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

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

Es NP-difícil encontrar el ancho de camino de grafos arbitrarios, o incluso aproximarlo con precisión. [ 5 ] [ 6 ] Sin embargo, el problema es tratable con parámetros fijos : probar si un grafo tiene un ancho de camino k se puede resolver en un tiempo que depende linealmente del tamaño del grafo pero superexponencialmente de k . [ 7 ] Además, para varias clases especiales de grafos, como los árboles , el ancho de camino se puede calcular en tiempo polinomial sin dependencia de k . [ 8 ] [ 9 ] Muchos problemas en algoritmos de grafos se pueden resolver eficientemente en grafos de ancho de camino acotado, utilizando programación dinámica en una descomposición de caminos del grafo. [ 10 ] La descomposición de caminos también se puede utilizar para medir la complejidad espacial de los algoritmos de programación dinámica en grafos de ancho de árbol acotado . [ 11 ]  

Definición

Un ejemplo de grafo G con un ancho de trayectoria de 2 y su descomposición en trayectoria de ancho 2. La parte inferior de la imagen muestra el mismo grafo y su descomposición en trayectoria, con color añadido para mayor énfasis. (Este ejemplo es una adaptación del grafo presentado en Bodlaender (1994a) , énfasis añadido).

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

  1. Para cada arista de G , existe un i tal que ambos extremos de la arista pertenecen al subconjunto X i , y
  2. Para cada tres índices i ≤ j ≤ k ,incógnitai∩incógnitak⊆incógnitaj.{\displaystyle X_{i}\cap X_{k}\subseteq X_{j}.}

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

El ancho de una descomposición de caminos se define de la misma manera que para las descomposiciones de árboles, como max i | X i | − 1 , y el ancho de camino de G es el ancho mínimo de cualquier descomposición de caminos de G . La resta de uno al tamaño de X i en esta definición tiene poca importancia en la mayoría de las aplicaciones del ancho de camino, pero se utiliza para que el ancho de camino de un grafo de caminos sea igual a uno. 

Caracterizaciones alternativas

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

Secuencias de pegado

Una descomposición de caminos puede describirse como una secuencia de grafos G i que se unen identificando pares de vértices de grafos consecutivos en la secuencia, de modo que el resultado de realizar todas estas uniones sea G . Los grafos G i pueden tomarse como los subgrafos inducidos de los conjuntos X i en la primera definición de descomposiciones de caminos, donde dos vértices en subgrafos inducidos sucesivos se unen cuando son inducidos por el mismo vértice en G , y en la otra dirección se pueden recuperar los conjuntos X i como los conjuntos de vértices de los grafos G i . El ancho de la descomposición de caminos es entonces uno menos que el número máximo de vértices en uno de los grafos G i . [ 2 ]

Espesor del intervalo

Un grafo de intervalos con un ancho de camino de dos, uno menos que la cardinalidad de sus cuatro camarillas máximas ABC , ACD , CDE y CDF .

El ancho de camino de cualquier grafo G es igual a uno menos que el número de clique más pequeño de un grafo de intervalo que contiene a G como subgrafo. [ 12 ] Es decir, para cada descomposición de camino 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 camino de G , tal que el ancho de la descomposición es uno menos que el número de clique del grafo de intervalo.

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

En sentido contrario, si G es un subgrafo de un grafo de intervalos con número de cliques p + 1 , entonces G tiene una descomposición en caminos de ancho p cuyos nodos están dados por los cliques máximos del grafo de intervalos. Por ejemplo, el grafo de intervalos mostrado con su representación en la figura tiene una descomposición en caminos con cinco nodos, que corresponden a sus cinco cliques máximos ABC , ACD , CDE , CDF y FG ; el tamaño máximo del clique es tres y el ancho de esta descomposición en caminos es dos.

Esta equivalencia entre el ancho del camino y el grosor del intervalo es muy similar a la equivalencia entre el ancho del árbol y el número mínimo de clique (menos uno) de un grafo cordal del cual el grafo dado es un subgrafo. Los grafos de intervalo son un caso especial de grafos cordales, y estos últimos pueden representarse como grafos de intersección de subárboles de un árbol común, generalizando así la forma en que los grafos de intervalo son grafos de intersección de subcaminos de un camino.

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 a v o a un vértice posterior como 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 camino de G. [ 13 ] Esto se deduce de la equivalencia anterior con los números de clique de grafos de intervalos: si G es un subgrafo de un grafo de intervalos I , representado (como en la figura) de tal manera que todos los puntos finales de intervalo son distintos, entonces el ordenamiento de los puntos finales izquierdos de los intervalos de I tiene un número de separación de vértices uno menos que el número de clique 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 extremo izquierdo del intervalo para un vértice v es su posición en el ordenamiento y el extremo derecho es la posición del vecino de v que aparece último en el ordenamiento.

Número de búsqueda de nodos

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

Límites

Un árbol oruga , un grafo maximal con ancho de camino uno.

Cada grafo de n vértices con ancho de camino k tiene como máximo k ( n − k + ( k − 1)/2) aristas, y los grafos de ancho de camino máximo k (grafos a los que no se pueden agregar más aristas sin aumentar el ancho de camino) tienen exactamente esta cantidad de aristas. Un grafo de ancho de camino máximo k debe ser un k- camino o una k -oruga, dos tipos especiales de k- árbol . Un k -árbol es un grafo cordal con exactamente n − k camarillas máximas , cada una con k + 1 vértices; en un k -árbol que no es en sí mismo una ( k + 1) -camarilla, cada camarilla máxima separa el grafo en dos o más componentes, o contiene un único vértice 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 un k -oruga es un k -árbol que puede particionarse en un k -camino y un conjunto de k -hojas, cada una adyacente a una k -clique separadora del k -camino. En particular, los grafos máximos de ancho de camino uno son precisamente los árboles oruga . [ 14 ]

Dado que las descomposiciones de caminos son un caso especial de las descomposiciones de árboles, el ancho de camino de cualquier grafo es mayor o igual que su ancho de árbol . El ancho de camino también es menor o igual que el ancho de corte , el número mínimo de aristas que cruzan cualquier corte entre vértices de menor y mayor numeración en una disposición lineal óptima de los vértices de un grafo; esto se debe a que el número de separación de vértices, el número de vértices de menor numeración con vecinos de mayor numeración, puede ser como máximo igual al número de aristas de corte. [ 15 ] Por razones similares, el ancho de corte es como máximo igual al ancho de camino multiplicado por el grado máximo de los vértices en un grafo dado. [ 16 ]

Cualquier bosque de n vértices tiene un ancho de camino 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 se puede particionar en dos subbosques más pequeños con como máximo 2 n ⁄ 3 vértices cada uno. Una disposición lineal formada al particionar recursivamente cada uno de estos dos subbosques, colocando los vértices separadores 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 grafo, muestra que, si el ancho de árbol de un grafo de n vértices G es t , entonces el ancho de camino de G es O ( t log n ) . [ 18 ] Dado que los grafos exteriores planares , los grafos serie-paralelo y los grafos de Halin tienen todos un ancho de árbol acotado, todos ellos también tienen como máximo un ancho de camino logarítmico.

Además de su relación con el ancho de árbol, el ancho de camino también está relacionado con el ancho de clique y el ancho de corte , a través de los grafos de línea ; el grafo de línea L ( G ) de un grafo G tiene un vértice por cada arista de G y dos vértices en L ( G ) son adyacentes cuando las dos aristas correspondientes de G comparten un extremo. Cualquier familia de grafos tiene un ancho de camino acotado si y solo si sus grafos de línea tienen un ancho de clique lineal acotado, donde el ancho de clique lineal reemplaza la operación de unión disjunta del ancho de clique con la operación de adjuntar un único vértice nuevo. [ 19 ] Si un grafo conexo 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 grafo de línea. [ 20 ]

En cualquier grafo planar , 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 ancho logarítmico de bosques descrita anteriormente) usar el teorema del separador planar para encontrar un conjunto de O ( √ n ) vértices cuya eliminación separa el grafo en dos subgrafos de como máximo 2 n ⁄ 3 vértices cada uno, y concatenar descomposiciones de caminos construidas recursivamente para cada uno de estos dos subgrafos. La misma técnica se aplica a cualquier clase de grafos para los que se cumple un teorema del separador similar. [ 22 ] Dado que, al igual que los grafos planares, los grafos en cualquier familia de grafos cerrados por menores fijos tienen separadores de tamaño O ( √ n ) , [ 23 ] se deduce que el ancho de camino de los grafos en cualquier familia cerrada por menores fijos es nuevamente O ( √ n ) . Para algunas clases de grafos planares, el ancho de camino del grafo y el ancho de camino de su grafo dual deben estar dentro de un factor constante entre sí: se conocen cotas de esta forma para grafos exteriores biconexos planares [ 24 ] y para grafos poliédricos. [ 25 ] Para grafos planares 2-conexos, el ancho de camino del grafo dual es menor que el ancho de camino del grafo de línea. [ 26 ] Queda abierto si el ancho de camino de un grafo planar y su dual están siempre dentro de un factor constante entre sí en los casos restantes.

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

Problema sin resolver en matemáticas
¿Cuál es el mayor ancho de camino posible de un grafo cúbico de n vértices ?
Más problemas sin resolver en matemáticas

En cualquier grafo cúbico , o más generalmente en cualquier grafo con grado máximo de vértice tres, el ancho del camino es como máximo n / 6 + o( n ) , donde n es el número de vértices del grafo. Existen grafos cúbicos con un ancho de camino de 0,082 n , pero se desconoce cómo reducir esta diferencia entre este límite inferior y el límite superior de n / 6. [ 31 ]

Cálculo de descomposiciones de caminos

Es NP-completo determinar si el ancho de camino de un grafo dado es como máximo k , cuando k es una variable dada como parte de la entrada. [ 5 ] Los mejores límites de tiempo conocidos en el peor caso para calcular el ancho de camino de grafos arbitrarios de n vértices son de la forma O (2 n n c ) para alguna constante c . [ 32 ] Sin embargo, se conocen varios algoritmos para calcular descomposiciones de caminos de manera más eficiente cuando el ancho de camino es pequeño, cuando la clase de grafos de entrada es limitada o aproximadamente. 

Tratabilidad de parámetros fijos

El ancho de camino es tratable con parámetros fijos : para cualquier constante k , es posible comprobar si el ancho de camino es como máximo k , y si es así, encontrar una descomposición de camino de ancho k , en tiempo lineal. [ 7 ] En general, estos algoritmos operan en dos fases. En la primera fase, se utiliza la suposición de que el grafo tiene un ancho de camino k para encontrar una descomposición de camino o descomposición de árbol que no es óptima, pero cuyo ancho puede acotarse como una 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 los algoritmos conocidos de este tipo son exponenciales en k 2 , imprácticos excepto para los valores más pequeños de k . [ 33 ] Para el caso k = 2, de Fluiter (1997) da un algoritmo explícito de tiempo lineal basado en una descomposición estructural de grafos de ancho de camino 2 .

Clases especiales de grafos

Bodlaender (1994) analiza la complejidad del cálculo del ancho de camino en varias clases especiales de grafos. Determinar si el ancho de camino de un grafo G es como máximo k sigue siendo NP-completo cuando G se restringe a grafos de grado acotado, [ 34 ] grafos planares , [ 34 ] grafos planares de grado acotado, [ 34 ] grafos cordales , [ 35 ] dominós cordales, [ 36 ] los complementos de grafos de comparabilidad , [ 29 ] y grafos bipartitos hereditarios de distancia . [ 37 ] Se deduce inmediatamente que también es NP-completo para las familias de grafos que contienen los grafos bipartitos hereditarios de distancia, incluidos los grafos bipartitos, los grafos bipartitos cordales, los grafos hereditarios de distancia y los grafos circulares . [ 37 ]

Sin embargo, el ancho de camino se puede calcular en tiempo lineal para árboles y bosques. [ 9 ] También se puede calcular en tiempo polinomial para grafos de ancho de árbol acotado, incluidos los grafos serie-paralelo , los grafos exteriores planares y los grafos de Halin , [ 7 ] así como para grafos divididos , [ 38 ] para los complementos de grafos cordales, [ 39 ] para grafos de permutación , [ 28 ] para cografos , [ 27 ] para grafos de arco circular , [ 40 ] para los grafos de comparabilidad de órdenes de intervalo, [ 30 ] y por supuesto para los propios grafos de intervalo , ya que en ese caso el ancho de camino es solo uno menos que el número máximo de intervalos que cubren cualquier punto en una representación de intervalo del grafo.

Algoritmos de aproximación

Es NP-difícil aproximar el ancho de camino de un grafo con una constante aditiva. [ 6 ] La mejor razón de aproximación conocida de un algoritmo de aproximación de tiempo polinomial para el ancho de camino es O ((log n ) 3/2 ) . [ 41 ] Para algoritmos de aproximación anteriores para el ancho de camino, véase Bodlaender et al. (1992) y Guha (2000) . Para aproximaciones en clases restringidas de grafos, véase Kloks y Bodlaender (1992) .

menores de grafos

Un subgrafo G es otro grafo formado a partir de G mediante la contracción, eliminación y supresión de aristas y vértices. Los subgrafos tienen una teoría compleja en la que varios resultados importantes involucran el ancho de camino.

Excluyendo un bosque

Si una familia F de grafos es cerrada bajo la toma de menores (cada menor de un miembro de F también está en F ), entonces por 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 grafos planares son los grafos que no tienen ni el grafo completo K 5 ni el grafo 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 de Robertson y Seymour (1983) , [ 2 ] y relaciona el ancho de camino acotado con la existencia de un bosque en la familia de menores prohibidos. Específicamente, definimos una familia F de grafos para que tenga ancho de camino acotado si existe una constante p tal que cada grafo en F tiene un ancho de camino como máximo p . Entonces, una familia cerrada de menores F tiene un ancho de camino acotado si y solo si el conjunto X de menores prohibidos para F incluye al menos un bosque.

En una dirección, este resultado es fácil de demostrar: si X no incluye al menos un bosque, entonces los grafos libres de X -menores no tienen ancho de camino acotado. Porque, en este caso, los grafos libres de X -menores incluyen todos los bosques, y en particular incluyen los árboles binarios perfectos . Pero un árbol binario perfecto con 2k + 1 niveles tiene un ancho de camino k , por lo que en este caso los grafos libres de X -menores tienen un ancho de camino no acotado. En la otra dirección, si X contiene un bosque de n vértices, entonces los grafos libres de X -menores tienen un ancho de camino como máximo n − 2. [ 43 ]

Obstáculos al ancho de ruta limitado

Los menores prohibidos para grafos de ancho de camino  1.

La propiedad de tener un ancho de camino como máximo p es, en sí misma, cerrada bajo la toma de menores: si G tiene una descomposición en caminos con un ancho como máximo p , entonces la misma descomposición en caminos sigue siendo válida si se elimina cualquier arista de G , y cualquier vértice puede eliminarse de G y de su descomposición en caminos sin aumentar el ancho. La contracción de una arista también puede realizarse sin aumentar el ancho de la descomposición, fusionando los subcaminos que representan los dos extremos de la arista contraída. Por lo tanto, los grafos con un ancho de camino como máximo p pueden caracterizarse por un conjunto X p de menores excluidos. [ 42 ] [ 44 ]

Aunque X p necesariamente incluye al menos un bosque, no es cierto que todos los grafos en X p sean bosques: por ejemplo, X 1 consta de dos grafos, un árbol de siete vértices y el triángulo K 3 . Sin embargo, el conjunto de árboles en X p puede caracterizarse con precisión: estos árboles son exactamente los árboles que se pueden formar a partir de tres árboles en X p − 1 conectando un nuevo vértice raíz 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 1 se forma de esta manera a partir del árbol de dos vértices (una sola arista) en X 0 . Basándonos en esta construcción, se puede demostrar que el número de menores prohibidos en X p es al menos ( p !) 2 . [ 44 ] Se ha calculado el conjunto completo X 2 de menores prohibidos para grafos de ancho de camino 2; contiene 110 grafos diferentes. [ 45 ]

Teoría de la estructura

El teorema de estructura de grafos para familias de grafos cerrados menores establece que, para cualquier familia F de este tipo , los grafos en F pueden descomponerse en sumas de cliques de grafos que pueden incrustarse en superficies de género acotado , junto con un número acotado de ápices y vórtices para cada componente de la suma de cliques. Un ápice es un vértice que puede ser adyacente a cualquier otro vértice en su componente, mientras que un vórtice es un grafo de ancho de camino acotado que se adhiere a 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 se incrusta un vórtice debe ser compatible con la descomposición de caminos 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 camino está íntimamente conectado a familias de grafos cerrados menores arbitrarias, 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 particionar circuitos en subsistemas más pequeños, con un número reducido de componentes en el límite entre los subsistemas. [ 34 ]

Ohtsuki et al. (1979) utilizan el grosor de intervalo para modelar el número de pistas necesarias en un diseño unidimensional de un circuito VLSI, formado por un conjunto de módulos que deben interconectarse mediante un sistema de redes. En su modelo, se forma un grafo en el que los vértices representan redes, y en el que dos vértices están conectados por una arista si sus redes se conectan al mismo módulo; es decir, si los módulos y las redes se interpretan como los nodos e hiperaristas de un hipergrafo , entonces el grafo formado a partir de ellos es su grafo de líneas . Una representación de intervalo de un supergrafo de este grafo de líneas, junto con una coloración 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 conectarse a las redes apropiadas. El hecho de que los grafos de intervalos sean grafos 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 clique de la completación de intervalos del grafo de red.

El diseño de matriz de compuertas [ 48 ] es un estilo específico de diseño VLSI CMOS para circuitos lógicos booleanos . En los diseños de matriz de compuertas, las señales se propagan a lo largo de "líneas" (segmentos de línea verticales), mientras que cada compuerta del circuito está formada por una secuencia de características del dispositivo que se encuentran a lo largo de un segmento de línea horizontal . Por lo tanto, el segmento de línea horizontal para cada compuerta debe cruzar los segmentos verticales para 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) , un diseño de este tipo que minimice el número de pistas verticales sobre las que se deben disponer las líneas se puede encontrar calculando el ancho de camino de un grafo que tiene las líneas como sus vértices y pares de líneas que comparten una compuerta como sus aristas. [ 49 ] El mismo enfoque algorítmico también se puede utilizar para modelar problemas de plegado en matrices lógicas programables . [ 50 ]

Dibujo de gráficos

El ancho de ruta tiene varias aplicaciones en el dibujo de gráficos :

  • Los grafos mínimos que tienen un número de cruces dado tienen un ancho de camino que está acotado por una función de su número de cruces. [ 51 ]
  • El número de líneas paralelas sobre las que se pueden dibujar los vértices de un árbol sin que se crucen con las aristas (bajo diversas 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 capa h con k cruces de un grafo G consiste en colocar los vértices de G sobre h líneas horizontales distintas, con aristas trazadas como caminos poligonales monótonos entre estas líneas, de manera que haya como máximo k cruces. Los grafos con tales dibujos tienen un ancho de camino acotado por una función de h y k . Por lo tanto, cuando h y k son constantes, es posible determinar en tiempo lineal si un grafo tiene un dibujo de capa h con k cruces . [ 53 ]
  • Un grafo con n vértices y un ancho de camino p puede incrustarse 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 intersequen. Por lo tanto, los grafos de ancho de camino limitado tienen incrustaciones de este tipo con volumen lineal. [ 54 ]

Diseño de compiladores

En la compilación de lenguajes de programación de alto nivel , el problema del ancho de ruta surge al reordenar secuencias de código lineal (es decir, código sin bifurcaciones de flujo de control ni bucles) de manera que todos los valores calculados en el código puedan almacenarse en registros de máquina en lugar de tener que volcarse a la memoria principal. En esta aplicación, el código a compilar se representa como un grafo acíclico dirigido (DAG) en el que los nodos representan los valores de entrada del código y los valores calculados por las operaciones dentro del código. Una arista del nodo x al nodo y en este DAG representa que el valor x es una de las entradas de 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 ordenamiento dado 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 puede reordenarse de tal manera que pueda evaluarse 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 grafo no dirigido formado al ignorar las orientaciones del DAG descrito anteriormente debe tener un ancho de camino como máximo w . Es posible comprobar si este es el caso, utilizando los algoritmos conocidos de parámetros fijos para el ancho de camino, y, de ser así, encontrar una descomposición de caminos para el grafo no dirigido, en tiempo lineal, suponiendo que w es una constante. Una vez encontrada una descomposición de caminos, se puede encontrar un ordenamiento topológico de ancho w (si existe) utilizando programación dinámica, también 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 grafos, en los que los vértices representan palabras y las aristas representan relaciones entre palabras; por ejemplo, si un adjetivo modifica a un sustantivo en la oración, el grafo tendría una arista entre esas dos palabras. Debido a la capacidad limitada de la memoria a corto plazo humana, [ 56 ] Kornai y Tuza argumentan que este grafo debe tener un ancho de ruta limitado (más específicamente, argumentan, un ancho de ruta como máximo de seis), ya que de lo contrario los humanos no podrían analizar el habla correctamente.

Algoritmos exponenciales

Muchos problemas en algoritmos de grafos pueden resolverse eficientemente en grafos de ancho de camino bajo, utilizando programación dinámica en una descomposición de caminos del grafo. [ 10 ] Por ejemplo, si se da un orden lineal de los vértices de un grafo 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 tiempo O(2 w n ). [ 31 ] En grafos de ancho de camino acotado, este enfoque conduce a algoritmos tratables de parámetros fijos, parametrizados por el ancho de camino. [ 49 ] Tales resultados no se encuentran frecuentemente en la literatura porque están subsumidos por algoritmos similares parametrizados por el ancho de árbol; sin embargo, el ancho de camino surge incluso en algoritmos de programación dinámica basados ​​en el 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 grafos con ancho de camino ilimitado, lo que da lugar a algoritmos que resuelven problemas de grafos no parametrizados en tiempo exponencial . Por ejemplo, al combinar este enfoque de programación dinámica con el hecho de que los grafos cúbicos tienen un ancho de camino n /6  +  o( n ), se observa que, en un grafo cúbico, el conjunto independiente máximo se puede construir en tiempo O(2n / 6  +  o( n ) ), más rápido que los métodos conocidos anteriormente. [ 31 ] Un enfoque similar conduce a algoritmos mejorados de tiempo exponencial para los problemas de corte máximo y conjunto dominante mínimo en grafos cúbicos, [ 31 ] y para varios otros problemas de optimización NP-difíciles. [ 57 ]

Véase también

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

Notas

  1. ↑ Diestel y Kühn (2005) .
  2. 1 2 3 4 Robertson y Seymour (1983) .
  3. ↑ Kinnersley (1989) ; Bodlaender (1998) .
  4. 1 2 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. 1 2 3 Bodlaender (1996) ; Bodlaender y Kloks (1996)
  8. ↑ Bodlaender (1994) .
  9. 12 Mohring (1990) ; Scheffler (1990) ; Ellis, Sudborough y Turner (1994) ; Peng et al. (1998) ; Skodinis (2000) ; Skodinis (2003) ; Coudert, Huc y Mazauric (2012) .
  10. 1 2 Arnborg (1985) .
  11. 1 2 Aspvall, Proskurowski y Telle (2000) .
  12. ↑ Bodlaender (1998) , Teorema 29, pág. 13.
  13. ^ Kinnersley (1989) ; Kinnersley (1992) ; Bodlaender (1998) , Teorema 51.
  14. ↑ Proskurowski y Telle (1999) .
  15. ↑ Korach y Solel (1993) , Lema 3 p.99; Bodlaender (1998) , Teorema 47, p. 24.
  16. ↑ Korach y Solel (1993) , Lema 1, pág. 99; Bodlaender (1998) , Teorema 49, pág. 24.
  17. ↑ Korach y Solel (1993) , Teorema 5, pág. 99; Bodlaender (1998) , Teorema 66, pág. 30. Scheffler (1992) da una cota superior más ajustada de log 3 (2 n + 1) en el ancho de camino de un bosque de n vértices.
  18. ↑ Korach y Solel (1993) , Teorema 6, pág. 100; Bodlaender (1998) , Corolario 24, pág. 10.
  19. ↑ Gurski y Wanke (2007) .
  20. ↑ Golovach (1993) .
  21. ↑ Bodlaender (1998) , Corolario 23, pág. 10.
  22. ↑ Bodlaender (1998) , Teorema 20, pág. 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. ↑ Fomin (2003) .
  27. ^ Bodlaender y Mohring (1990) .
  28. ^ Bodlaender , Kloks y Kratsch (1993) .
  29. 1 2 Habib y Möhring (1994) .
  30. 1 2 Garbe (1995) .
  31. ^ Fomin y Høie ( 2006 ) .
  32. ↑ Fomin et al. (2008) .
  33. ↑ Downey & Fellows (1999) , pág. 12.
  34. ^ Monien y Sudborough ( 1988 ) .
  35. ↑ Gustedt (1993) .
  36. ↑ Kloks, Kratsch y Müller (1995) . Un dominó cordal es un grafo cordal en el que cada vértice pertenece a como máximo dos camarillas máximas.
  37. 1 2 Kloks et al. (1993) .
  38. ↑ Kloks y Bodlaender (1992) ; Gustedt (1993) .
  39. ↑ Garbe (1995) atribuye este resultado a la tesis doctoral de Ton Kloks de 1993; el algoritmo de tiempo polinomial de Garbe para grafos de comparabilidad de órdenes de intervalo generaliza este resultado, ya que cualquier grafo cordal debe ser un grafo de comparabilidad de este tipo.
  40. ↑ Suchan y Todinca (2007) .
  41. ↑ Feige, Hajiaghayi y Lee (2005) .
  42. 1 2 Robertson y Seymour (2004) .
  43. ↑ Bienstock et al. (1991) ; Diestel (1995) ; Cattell, Dinneen y Fellows (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. ↑ Berge (1967) .
  48. ↑ López y Derecho (1980) .
  49. 1 2 Fellows y Langston (1989) .
  50. ↑ Mohring (1990) ; Ferreira y Canción (1992) .
  51. ↑ Hliněny (2003) .
  52. ↑ Suderman (2004) .
  53. ↑ Dujmović et al. (2008) .
  54. ↑ Dujmović, Morin y Wood (2003) .
  55. 1 2 Bodlaender, Gustedt y Telle (1998) .
  56. ↑ Miller (1956) .
  57. ^ Kneis y col. (2005) ; Björklund y Husfeldt (2008) .

Referencias

  • Alon, Noga ; Seymour, Paul ; Thomas, Robin (1990), "Un teorema separador para grafos con un menor excluido y sus aplicaciones", Actas del 22.º Simposio ACM sobre Teoría de la Computación (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 grafos con descomponibilidad acotada: una revisión", 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 k -árbol", SIAM Journal on Algebraic and Discrete Methods , 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 k -árbol parcial", 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. 155–165 .
  • Bienstock, Dan; Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1991), "Exclusión rápida de 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 emparejamientos perfectos", 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 de treewidth", en Dassow, Jürgen; Kelemenová, Alisa (eds.), Desarrollos en Ciencias de la Computación Teórica (Actas de la 7ª Reunión Internacional de Jóvenes Científicos de la Computación, Smolenice, 16-20 de noviembre de 1992) , Temas en Matemáticas Computacionales, vol.  6, Gordon and Breach, pp. 1-20 .
  • Bodlaender, Hans L. (1994a), "Una guía turística a través del ancho de los árboles", Acta Cybernetica , 11 : 1–2
  • Bodlaender, Hans L. (1996), "Un algoritmo de tiempo lineal para encontrar descomposiciones de árboles de pequeño ancho de árbol", SIAM Journal on Computing , 25 (6): 1305– 1317, doi : 10.1137/S0097539793251219 , hdl : 1874/16670.
  • Bodlaender, Hans L. (1998), "Un k -arboreto parcial de grafos con ancho de árbol acotado", Theoretical Computer Science , 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 camino de grafos exteriores planares", 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 del camino y la altura mínima del árbol de eliminación", Conceptos de teoría de grafos en informática , Notas de clase en informática , vol.  570, pp. 1–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", Actas del 9.º Simposio ACM-SIAM sobre Algoritmos Discretos (SODA '98) (PDF) , págs. 574-583 , archivado del original (PDF) el 4 de febrero de 2005. .
  • Bodlaender, Hans L. ; Kloks, Ton (1996), "Algoritmos eficientes y constructivos para el ancho de camino y el ancho de árbol de grafos", Journal of Algorithms , 21 (2): 358– 402, doi : 10.1006/jagm.1996.0049 , hdl : 1874/16538.
  • Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter (1993), "Ancho de árbol y ancho de camino de grafos de permutación", Actas del 20.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP 1993) , Lecture Notes in Computer Science, vol.  700, Springer-Verlag, pp. 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), "The pathwidth and treewidth of cographs", Proc. 2nd Scandinavian Workshop on Algorithm Theory , Lecture Notes in Computer Science, vol.  447, Springer-Verlag, pp. 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, Florian; 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: a short proof of the path-width theorem", Combinatorics, Probability and Computing , 4 (1): 27– 30, doi : 10.1017/S0963548300001450.
  • Diestel, Reinhard; Kühn, Daniela (2005), "Jerarquías menores de grafos", Matemáticas Aplicadas Discretas , 145 (2): 167– 182, doi : 10.1016/j.dam.2004.01.010.
  • Demaine, Erik D .; Hajiaghayi, MohammadTaghi ; Kawarabayashi, Ken-ichi (2005), "Teoría algorítmica de menores de grafos: descomposición, aproximación y coloración", Actas del 46.º Simposio 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 .; Fellows, MR ; 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 grafos en capas", Algorithmica , 52 (2): 267–292 , doi : 10.1007/s00453-007-9151-1 , S2CID 2298634 .
  • Dujmović, Vida ; Morin, Pat ; Wood, David R. (2003), "Ancho de trayectoria y dibujos tridimensionales de cuadrículas de líneas rectas de grafos" (PDF) , Actas del 10.º Simposio Internacional sobre Dibujo de Grafos (GD 2002) , Lecture Notes in Computer Science, vol.  2528, Springer-Verlag, pp. 42–53 . .
  • Ellis, JA; Sudborough, IH; Turner, JS (1983), "Separación de grafos y número de búsqueda", Actas de la Conferencia Allerton de 1983 sobre Comunicación, Control y Computación.. Según lo citado por Monien y Sudborough (1988) .
  • Ellis, JA; Sudborough, IH; Turner, JS (1994), "La separación de vértices y el número de búsqueda de un árbol", Information and Computation , 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", Actas del 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 .
  • Fellows, Michael R.; Langston , Michael A. (1989), "Sobre la decisión de búsqueda y la eficiencia de los algoritmos de tiempo polinomial", Actas del 21.º Simposio ACM sobre Teoría de la Computación , págs. 501–512 , doi : 10.1145/73007.73055 , ISBN  0897913078, S2CID 1854173 .
  • Ferreira, Afonso G.; Song, Siang W. (1992), "Lograr la optimalidad para el diseño de matrices de compuertas y el plegado de PLA: un enfoque basado en la teoría de grafos", Actas del 1er Simposio Latinoamericano de Informática Teórica (LATIN '92) , Lecture Notes in Computer Science, vol.  583, Springer-Verlag, pp. 139–153 , doi : 10.1007/BFb0023825 , hdl : 10068/43314 , ISBN  3-540-55284-7.
  • de Fluiter, Babette (1997), Algoritmos para grafos de ancho de árbol pequeño (PDF) , tesis doctoral, Universidad de Utrecht , ISBN 90-393-1528-0Archivado desde el original (PDF) el 24/07/2011 , consultado el 06/05/2010..
  • Fomin, Fedor V. (2003), "Ancho de camino de grafos planares y lineales", Graphs and Combinatorics , 19 (1): 91–99 , doi : 10.1007/s00373-002-0490-z , S2CID 43123449 .
  • Fomin, Fedor V.; Høie, Kjartan (2006), "Ancho de camino de grafos cúbicos y algoritmos exactos", Information Processing Letters , 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 camino en incrustaciones de grafos poliédricos", Journal of Graph Theory , 55 (1): 42– 54, doi : 10.1002/jgt.20219.
  • Garbe, Renate (1995), "Ancho de árbol y ancho de camino de grafos de comparabilidad de órdenes de intervalo", Actas del 20.º Taller Internacional sobre Conceptos de Teoría de Grafos en Ciencias de la Computación (WG'94) , Lecture Notes in Computer Science, vol.  903, Springer-Verlag, pp. 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 grafo y el número de separación de vértices del grafo de líneas", Matemáticas Discretas y Aplicaciones , 3 (5): 517– 522, doi : 10.1515/dma.1993.3.5.517 , S2CID 120745961 .
  • Guha, Sudipto (2000), "Algoritmos de disección y aproximación de grafos anidados", Actas del 41.º Simposio IEEE sobre Fundamentos de la Informática (FOCS 2000) , pág.  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 clique acotado", Matemáticas Discretas , 307 (22): 2734– 2754, doi : 10.1016/j.disc.2007.01.020.
  • Gustedt, Jens (1993), "Sobre el ancho de camino de los grafos 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 grafos de coconparabilidad y un nuevo parámetro de teoría del orden", Order , 11 (1): 47– 60, doi : 10.1007/BF01462229 , S2CID 2648030 .
  • Hliněny, Petr (2003), "Los grafos críticos de número de cruce tienen ancho de camino acotado", Journal of Combinatorial Theory, Series 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 grafo de intervalo con número mínimo de cliques que contenga un grafo dado como subgrafo", Actas del Simposio Internacional sobre Circuitos y Sistemas , págs. 657–660 .
  • Kinnersley, Nancy G. (1989), Aislamiento de conjuntos de obstrucción para problemas de permutación de diseños (tesis doctoral), Universidad Estatal de Washington, ProQuest 303738168 ; véase el Teorema 6.A, pág. 44.
  • Kinnersley, Nancy G. (1992), "El número de separación de vértices de un grafo es igual a su ancho de camino", Information Processing Letters , 42 (6): 345–350 , doi : 10.1016/0020-0190(92)90234-M.
  • Kinnersley, Nancy G.; Langston, Michael A. (1994), "Aislamiento de conjuntos de obstrucción para el problema de la disposición de la matriz de compuertas", Discrete Applied Mathematics , 54 ( 2–3 ): 169–213 , doi : 10.1016/0166-218X(94)90021-3.
  • Kirousis, Lefteris M.; Papadimitriou, Christos H. (1985), "Grafos de intervalos y búsqueda", Matemáticas Discretas , 55 (2): 181– 184, doi : 10.1016/0012-365X(85)90046-9.
  • Kloks, Ton; Bodlaender, Hans L. (1992), "Aproximación del ancho de árbol y del ancho de camino de algunas clases de grafos perfectos", Actas del 3er Simposio Internacional sobre Algoritmos y Computación (ISAAC'92) , Lecture Notes in Computer Science, vol.  650, Springer-Verlag, pp. 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 de árbol y el relleno mínimo: todo lo que necesitas son los separadores mínimos", Actas del 1er Simposio Europeo sobre Algoritmos (ESA'93) (Lecture Notes in Computer Science) , vol.  726, Springer-Verlag, pp. 260–271 , doi : 10.1007/3-540-57273-2_61 , ISBN  978-3-540-57273-2.
  • Kloks, Ton; Kratsch, Dieter; Müller, H. (1995), "Dominó", Actas del 20.º Taller Internacional sobre Conceptos de Teoría de Grafos en Ciencias de la Computación (WG'94) , Lecture Notes in Computer Science, vol.  903, Springer-Verlag, pp. 106–120 , doi : 10.1007/3-540-59071-4_41 , ISBN  978-3-540-59071-2.
  • Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter (2005), "Algoritmos basados ​​en el ancho de árbol de grafos dispersos", Actas del 31.er Taller Internacional sobre Conceptos de Teoría de Grafos en Ciencias de la Computación (WG 2005) , Lecture Notes in Computer Science, vol.  3787, Springer-Verlag, pp. 385–396 , doi : 10.1007/11604686_34 , ISBN  978-3-540-31000-6.
  • Korach, Ephraim; Solel, Nir (1993), "Ancho de árbol, ancho de camino 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, anchura de trayectoria 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 grafos", Acta Informatica , 16 (4): 465–475 , doi : 10.1007/BF00264496 , S2CID 19415148 .
  • López, Alexander D.; Law, Hung-Fai S. (1980), "Un método de diseño de matriz de compuertas densas para VLSI MOS", 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 el número conjunto, 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 grafos relacionados con la disposición de matrices de compuertas y el plegado de PLA", en Tinhofer, G.; Mayr, E.; Noltemeier, H.; et  al. (eds.), Teoría computacional de grafos , Computing Supplementum, vol.  7, Springer-Verlag, pp. 17–51 , ISBN  3-211-82177-5.
  • Monien, B.; Sudborough, IH (1988), "El corte mínimo es NP-completo para árboles ponderados por aristas", Theoretical Computer Science , 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), "Asignación de compuertas lógicas unidimensionales y grafos de intervalos", IEEE Transactions on Circuits and Systems , 26 (9): 675– 684, Bibcode : 1979ITCS...26..675O , 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, 4.ª Conferencia Internacional Anual, COCOON '98, Taipéi, Taiwán, RoC, 12-14 de agosto de 1998, Actas , Lecture Notes in Computer Science, vol.  1449, Springer, pp. 279-288 , doi : 10.1007/3-540-68535-9_32 , ISBN  978-3-540-64824-6
  • Proskurowski, Andrzej; Telle, Jan Arne (1999), " Clases de grafos con modelos de intervalo restringidos" , Matemáticas Discretas e Informática Teórica , 3 : 167–176.
  • Robertson, Neil ; Seymour, Paul (1983), "Graph minors. I. Excluding a forest", Journal of Combinatorial Theory, Series B , 35 (1): 39–61 , doi : 10.1016/0095-8956(83)90079-5.
  • Robertson, Neil ; Seymour, Paul (2003), "Menores de grafos. XVI. Exclusión de un grafo no planar", 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. Wagner's conjecture", Journal of Combinatorial Theory, Series 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 árboles", en Bodendiek, R.; Henn, R. (eds.), Temas de combinatoria y teoría de grafos , Physica-Verlag, pp. 613–620 .
  • Scheffler, Petra (1992), "Incrustación óptima de un árbol en un grafo de intervalos en tiempo lineal", en Nešetřil, Jaroslav ; Fiedler, Miroslav (eds.), Cuarto Simposio Checoslovaco sobre Combinatoria, Grafos y Complejidad , Elsevier.
  • Skodinis, Konstantin (2000), "Cálculo de diseños lineales óptimos de árboles en tiempo lineal", Actas del 8.º Simposio Europeo sobre Algoritmos (ESA 2000) , Lecture Notes in Computer Science, vol.  1879, Springer-Verlag, pp. 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 árbol 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), "Pathwidth of circular-arc graphs", Proc. 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007) , Lecture Notes in Computer Science, vol.  4769, Springer-Verlag, pp. 258–269 , doi : 10.1007/978-3-540-74839-7_25 , ISBN  978-3-540-74838-0.
  • Suderman, Matthew (2004), "Pathwidth and layered drawings of trees" (PDF) , International Journal of Computational Geometry and Applications , 14 (3): 203–225 , doi : 10.1142/S0218195904001433 , archivado del original (PDF) el 3 de mayo de 2003..
  • Takahashi, Atsushi; Ueno, Shuichi; Kajitani, Yoji (1994), "Menores prohibidos acíclicos mínimos para la familia de grafos con ancho de camino acotado", Matemáticas Discretas , 127 ( 1–3 ): 293–304 , doi : 10.1016/0012-365X(94)90092-2.
Lecturas relacionadas
6 articulos
Teoría de grafosTeoría de grafosEn matemáticas , la teoría de grafos es el estudio de los grafos , que son estructuras matemáticas utilizadas para modelar relaciones por pares ent...Gráfica (matemática discreta)Gráfica (matemática discreta)En matemáticas discretas , particularmente en teoría de grafos , un grafo es una estructura que consiste en un conjunto de objetos donde algunos pa...Gráfico de rutaGráfico de rutaEn el campo matemático de la teoría de grafos , un grafo de trayectoria (o grafo lineal ) es un grafo cuyos vértices se pueden enumerar en el orden...SubconjuntoDiagrama de Euler que muestra que A es un subconjunto de B (denotado ) y, a la inversa, B es un superconjunto de A (denotado ). A ⊆ B {\displaystyl...Vertex (graph theory)Vertex (graph theory)In discrete mathematics, and more specifically in graph theory, a vertex (plural vertices) or node is the fundamental unit of which graphs are form...SubsecuenciaSubsecuenciaEn matemáticas , una subsecuencia de una secuencia dada es una secuencia que se puede derivar de la secuencia dada eliminando algunos elementos o n...