Ancho del árbol

Número que denota la cercanía de un gráfico a un árbol

En teoría de grafos , el ancho de árbol de un gráfico no dirigido es un número entero que especifica, de manera informal, qué tan lejos está el gráfico de ser un árbol . El ancho de árbol más pequeño es 1; las gráficas con ancho de árbol 1 son exactamente los árboles y los bosques . Las gráficas con un ancho de árbol como máximo de 2 son las gráficas en serie-paralelo . Los gráficos máximos con un ancho de árbol exactamente k se llaman k -árboles , y los gráficos con un ancho de árbol como máximo k se llaman k -árboles parciales . Muchas otras familias de gráficos bien estudiadas también tienen un ancho de árbol acotado.

El ancho del árbol se puede definir formalmente de varias maneras equivalentes: en términos del tamaño del conjunto de vértices más grande en una descomposición en árbol del gráfico, en términos del tamaño de la camarilla más grande en una terminación cordal del gráfico, en términos del máximo orden de un refugio que describe una estrategia para un juego de persecución-evasión en el gráfico, o en términos del orden máximo de una zarza , una colección de subgrafos conectados que se tocan entre sí.

El ancho de árbol se usa comúnmente como parámetro en el análisis de complejidad parametrizado de algoritmos de gráficos . Muchos algoritmos que son NP-hard para gráficos generales se vuelven más fáciles cuando el ancho del árbol está limitado por una constante.

El concepto de ancho de árbol fue introducido originalmente por Umberto Bertelè y Francesco Brioschi (1972) bajo el nombre de dimensión . Posteriormente fue redescubierto por Rudolf Halin  (1976), basándose en propiedades que comparte con un parámetro gráfico diferente, el número de Hadwiger . Posteriormente fue redescubierto nuevamente por Neil Robertson y Paul Seymour  (1984) y desde entonces ha sido estudiado por muchos otros autores. ^[1]

Definición

Un gráfico con ocho vértices y una descomposición en árbol del mismo en un árbol con seis nodos. Cada borde del gráfico conecta dos vértices que se enumeran juntos en algún nodo del árbol, y cada vértice del gráfico se enumera en los nodos de un subárbol contiguo del árbol. Cada nodo del árbol enumera como máximo tres vértices, por lo que el ancho de esta descomposición es dos.

Una descomposición en árbol de un gráfico G = ( V , E ) es un árbol T con nodos X ₁ , …, X _n , donde cada X _i es un subconjunto de V , que satisface las siguientes propiedades ^[2] ( se utiliza el término nodo para referirse a un vértice de T para evitar confusión con vértices de G ):

1. La unión de todos los conjuntos X _i es igual a V . Es decir, cada vértice del gráfico está contenido en al menos un nodo del árbol.
2. Si X _i y X _j contienen un vértice v , entonces todos los nodos X _k de T en el camino (único) entre Xi y _X j _también contienen v . De manera equivalente, los nodos del árbol que contienen el vértice v forman un subárbol conectado de T.
3. Para cada arista ( v , w ) del gráfico, hay un subconjunto Xi _que contiene tanto v como w . Es decir, los vértices son adyacentes en el gráfico sólo cuando los subárboles correspondientes tienen un nodo en común.

El ancho de la descomposición de un árbol es el tamaño de su conjunto más grande X _i menos uno. El ancho de árbol tw( G ) de un gráfico G es el ancho mínimo entre todas las posibles descomposiciones de árbol de G . En esta definición, el tamaño del conjunto más grande se reduce en uno para que el ancho de un árbol sea igual a uno.

De manera equivalente, el ancho del árbol de G es uno menos que el tamaño de la camarilla más grande en el gráfico cordal que contiene G con el número de camarilla más pequeño . Se puede obtener un gráfico cordal con este tamaño de camarilla agregando a G un borde entre cada dos vértices que pertenezcan al menos a uno de los _conjuntos Xi .

Treewidth también se puede caracterizar en términos de paraísos , funciones que describen una estrategia de evasión para un determinado juego de persecución-evasión definido en un gráfico. Un gráfico G tiene un ancho de árbol k si y sólo si tiene un refugio de orden k + 1 pero no de orden superior, donde un refugio de orden k + 1 es una función β que asigna cada conjunto X de como máximo k vértices en G a uno de los componentes conectados de G \ X y que obedece a la propiedad de monotonicidad de que β ( Y ) ⊆ β ( X ) siempre que X ⊆ Y .

Una zarza de orden cuatro en un gráfico de cuadrícula de 3 × 3, cuya existencia muestra que el gráfico tiene un ancho de árbol de al menos 3

También se puede hacer una caracterización similar usando zarzas , familias de subgrafos conectados que se tocan entre sí (lo que significa que comparten un vértice o están conectados por un borde). ^[3] El orden de una zarza es el conjunto de aciertos más pequeño para la familia de subgrafos, y el ancho del árbol de un gráfico es uno menos que el orden máximo de una zarza.

Ejemplos

Todo gráfico completo K _n tiene un ancho de árbol n – 1 . Esto se ve más fácilmente usando la definición de ancho de árbol en términos de gráficos cordales: el gráfico completo ya es cordal y agregar más aristas no puede reducir el tamaño de su camarilla más grande.

Un gráfico conectado con al menos dos vértices tiene un ancho de árbol 1 si y sólo si es un árbol. Un árbol tiene un ancho de árbol uno por el mismo razonamiento que para los gráficos completos (es decir, es cordal y tiene un tamaño de camarilla máximo de dos). Por el contrario, si un gráfico tiene un ciclo, entonces cada terminación cordal del gráfico incluye al menos un triángulo que consta de tres vértices consecutivos del ciclo, de lo que se deduce que el ancho de su árbol es al menos dos.

Ancho de árbol delimitado

Familias de gráficos con ancho de árbol acotado

Para cualquier constante fija k , las gráficas de ancho de árbol como máximo k se denominan k -árboles parciales . Otras familias de gráficos con ancho de árbol acotado incluyen los gráficos de cactus , los pseudobosques , los gráficos de series-paralelas , los gráficos de planos exteriores , los gráficos de Halin y las redes apolíneas . ^[4] Los gráficos de flujo de control que surgen en la compilación de programas estructurados también tienen un ancho de árbol limitado, lo que permite que ciertas tareas, como la asignación de registros, se realicen de manera eficiente en ellos. ^[5]

Los gráficos planos no tienen un ancho de árbol limitado, porque el gráfico de cuadrícula n × n es un gráfico plano con un ancho de árbol exactamente n . Por lo tanto, si F es una familia de gráficos menores cerrados con un ancho de árbol acotado, no puede incluir todos los gráficos planos. Por el contrario, si algún gráfico plano no puede ocurrir como menor para los gráficos de la familia F , entonces hay una constante k tal que todos los gráficos en F tienen un ancho de árbol como máximo k . Es decir, las tres condiciones siguientes son equivalentes entre sí: ^[6]

1. F es una familia cerrada menor de gráficos de ancho de árbol acotado;
2. Uno de los finitos menores prohibidos que caracterizan a F es plano;
3. F es una familia de gráficos menores cerrados que no incluye todos los gráficos planos.

Menores prohibidos

Los cuatro menores prohibidos para el ancho del árbol 3: K ₅ (arriba a la izquierda), la gráfica del octaedro (abajo a la izquierda), la gráfica de Wagner (arriba a la derecha) y la gráfica del prisma pentagonal (abajo a la derecha)

Para cada valor finito de k , las gráficas de ancho de árbol como máximo k pueden caracterizarse por un conjunto finito de menores prohibidos . (Es decir, cualquier gráfico de ancho de árbol > k incluye uno de los gráficos del conjunto como menor). Cada uno de estos conjuntos de menores prohibidos incluye al menos un gráfico plano.

• Para k = 1 , el único menor prohibido es un gráfico de ciclo de 3 vértices . ^[4]
• Para k = 2 , el único menor prohibido es el gráfico completo de 4 vértices K ₄ . ^[4]
• Para k = 3 , hay cuatro menores prohibidos: K ₅ , la gráfica del octaedro , la gráfica del prisma pentagonal y la gráfica de Wagner . De estos, los dos gráficos poliédricos son planos. ^[7]

Para valores mayores de k , el número de menores prohibidos crece al menos tan rápido como el exponencial de la raíz cuadrada de  k . ^[8] Sin embargo, los límites superiores conocidos sobre el tamaño y el número de menores prohibidos son mucho más altos que este límite inferior. ^[9]

Algoritmos

Calcular el ancho del árbol

Es NP-completo determinar si un gráfico dado G tiene un ancho de árbol como máximo para una variable k dada . ^[10] Sin embargo, cuando k es una constante fija, se pueden reconocer los gráficos con un ancho de árbol k y se puede construir una descomposición de árbol de ancho k para ellos, en tiempo lineal. ^[11] La dependencia temporal de este algoritmo de k es exponencial.

Debido al papel que desempeña el ancho del árbol en una enorme cantidad de campos, se desarrollaron diferentes algoritmos prácticos y teóricos que calculan el ancho del árbol de un gráfico. Dependiendo de la aplicación en cuestión, se puede preferir una mejor relación de aproximación o una mejor dependencia en el tiempo de ejecución del tamaño de la entrada o del ancho del árbol. La siguiente tabla proporciona una descripción general de algunos de los algoritmos de ancho de árbol. Aquí k es el ancho del árbol y n es el número de vértices de un gráfico de entrada G. Cada uno de los algoritmos genera en el tiempo f ( k ) ⋅ g ( n ) una descomposición del ancho dada en la columna Aproximación. Por ejemplo, el algoritmo de Bodlaender (1996) en el tiempo 2 ^{O ( k 3 )} ⋅ n construye una descomposición en árbol del gráfico de entrada G de ancho como máximo k o informa que el ancho del árbol de G es mayor que k . De manera similar, el algoritmo de Bodlaender et al. (2016) en el tiempo 2 ^{O ( k )} ⋅ n construye una descomposición en árbol del gráfico de entrada G de ancho como máximo 5 k + 4 o informa que el ancho del árbol de G es mayor que k . Korhonen (2021) mejoró esto a 2 k + 1 en el mismo tiempo de ejecución.

Problema no resuelto en matemáticas :

¿ Se puede calcular el ancho de árbol de gráficos planos en tiempo polinomial?

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

No se sabe si la determinación del ancho de árbol de gráficos planos es NP-completa o si su ancho de árbol se puede calcular en tiempo polinómico. ^[12]

En la práctica, un algoritmo de Shoikhet & Geiger (1997) puede determinar el ancho de árbol de gráficos con hasta 100 vértices y el ancho de árbol hasta 11, encontrando una terminación cordal de estos gráficos con el ancho de árbol óptimo.

Para gráficos más grandes, se pueden utilizar técnicas basadas en búsqueda, como la búsqueda de rama y límite (BnB) y la búsqueda del mejor primero para calcular el ancho del árbol. Estos algoritmos se encuentran en cualquier momento en el que, cuando se detienen temprano, generarán un límite superior en el ancho del árbol.

Gogate y Dechter propusieron el primer algoritmo BnB para calcular el ancho de un árbol, llamado algoritmo QuickBB ^{[13] . [14]} Dado que la calidad de cualquier algoritmo BnB depende en gran medida de la calidad del límite inferior utilizado, Gogate y Dechter ^[14] también propusieron un algoritmo novedoso para calcular un límite inferior en el ancho del árbol llamado ancho mínimo menor. ^[14] En un nivel alto, el algoritmo de ancho mínimo menor combina el hecho de que el ancho del árbol de un gráfico nunca es mayor que su grado mínimo o su menor para producir un límite inferior del ancho del árbol. El algoritmo de ancho mínimo menor construye repetidamente un gráfico menor contrayendo un borde entre un vértice de grado mínimo y uno de sus vecinos, hasta que solo queda un vértice. Se garantiza que el máximo del grado mínimo sobre estos menores construidos será un límite inferior en el ancho del árbol del gráfico.

Dow y Korf ^[15] mejoraron el algoritmo QuickBB utilizando la búsqueda "mejor primero" . En ciertos gráficos, este algoritmo de búsqueda del mejor primero es un orden de magnitud más rápido que QuickBB.

Resolver otros problemas en gráficas de ancho de árbol pequeño

A principios de la década de 1970, se observó que una gran clase de problemas de optimización combinatoria definidos en gráficos podían resolverse eficientemente mediante programación dinámica no serial siempre que el gráfico tuviera una dimensión acotada , ^[16] un parámetro que se demostró que era equivalente a ancho del árbol por Bodlaender (1998). Posteriormente, varios autores observaron de forma independiente a finales de la década de 1980 ^[17] que muchos problemas algorítmicos que son NP-completos para gráficos arbitrarios pueden resolverse eficientemente mediante programación dinámica para gráficos de ancho de árbol acotado, utilizando las descomposiciones de árbol de estos gráficos.

Como ejemplo, el problema de colorear un gráfico de ancho de árbol k se puede resolver utilizando un algoritmo de programación dinámica en una descomposición en árbol del gráfico. Para cada conjunto X _i de la descomposición del árbol, y cada partición de los vértices de X _i en clases de color, el algoritmo determina si esa coloración es válida y puede extenderse a todos los nodos descendientes en la descomposición del árbol, combinando información de naturaleza similar. tipo calculado y almacenado en esos nodos. El algoritmo resultante encuentra una coloración óptima de un gráfico de n vértices en el tiempo O ( k ^{k + O (1)} n ) , un límite de tiempo que hace que este problema de parámetros fijos sea manejable .

teorema de courcelle

Para una clase grande de problemas, existe un algoritmo de tiempo lineal para resolver un problema de la clase si se proporciona una descomposición de árbol con un ancho de árbol acotado constante. Específicamente, el teorema de Courcelle ^[18] establece que si un problema de grafos se puede expresar en la lógica de grafos usando lógica monádica de segundo orden , entonces se puede resolver en tiempo lineal en gráficos con ancho de árbol acotado. La lógica monádica de segundo orden es un lenguaje para describir propiedades de gráficos que utiliza las siguientes construcciones:

• Operaciones lógicas, como ${\displaystyle \wedge ,\vee ,\neg ,\Rightarrow }$
• Pruebas de membresía, como e ∈ E , v ∈ V
• Cuantificaciones sobre vértices, aristas, conjuntos de vértices y/o conjuntos de aristas, como ∀ v ∈ V , ∃ e ∈ E , ∃ I ⊆ V , ∀ F ⊆ E
• Pruebas de adyacencia ( u es un punto final de e ) y algunas extensiones que permiten cosas como la optimización.

Consideremos, por ejemplo, el problema de los 3 colores para gráficos. Para un gráfico G = ( V , E ) , este problema pregunta si es posible asignar a cada vértice v ∈ V uno de los 3 colores de modo que no se asigne el mismo color a dos vértices adyacentes. Este problema se puede expresar en lógica monádica de segundo orden de la siguiente manera:

${\displaystyle \exists W_{1}\subseteq V:\exists W_{2}\subseteq V:\exists W_{3}\subseteq V:\forall v\in V:(v\in W_{1}\vee v\in W_{2}\vee v\in W_{3})\wedge }$

${\displaystyle \forall v\in V:\forall w\in V:(v,w)\in E\Rightarrow (\neg (v\in W_{1}\wedge w\in W_{1})\wedge \neg (v\in W_{2}\wedge w\in W_{2})\wedge \neg (v\in W_{3}\wedge w\in W_{3}))}$,

donde W ₁ , W ₂ , W ₃ representan los subconjuntos de vértices que tienen cada uno de los 3 colores. Por lo tanto, según los resultados de Courcelle, el problema de los 3 colores se puede resolver en tiempo lineal para un gráfico dada una descomposición en árbol de ancho de árbol constante acotado.

Parámetros relacionados

Ancho de ruta

El ancho de ruta de un gráfico tiene una definición muy similar al ancho de árbol mediante descomposiciones de árboles, pero está restringido a descomposiciones de árboles en las que el árbol subyacente de la descomposición es un gráfico de ruta . Alternativamente, el ancho de ruta se puede definir a partir de gráficos de intervalo de manera análoga a la definición del ancho de árbol a partir de gráficos de cuerdas. Como consecuencia, el ancho de ruta de un gráfico es siempre al menos tan grande como el ancho de su árbol, pero sólo puede ser mayor en un factor logarítmico. ^[4] Otro parámetro, el ancho de banda del gráfico , tiene una definición análoga a partir de los gráficos de intervalo adecuados y es al menos tan grande como el ancho de ruta. Otros parámetros relacionados incluyen la profundidad del árbol , un número acotado para una familia de gráficos menores cerrados si y sólo si la familia excluye una ruta, y la degeneración , una medida de la escasez de un gráfico que es como máximo igual a su ancho del árbol.

Tamaño menor de cuadrícula

Debido a que el ancho del árbol de un gráfico de cuadrícula n × n es n , el ancho del árbol de un gráfico G siempre es mayor o igual al tamaño de la cuadrícula cuadrada menor más grande de G. En la otra dirección, el teorema de la cuadrícula menor de Robertson y Seymour muestra que existe una función ilimitada f tal que la cuadrícula menor cuadrada más grande tiene un tamaño al menos f ( r ) donde r es el ancho del árbol. ^[19] Los mejores límites conocidos para f son que f debe ser al menos Ω( r ^d ) para alguna constante fija d > 0 , y como máximo ^[20]

${\displaystyle O\left({\sqrt {r/\log r}}\right).}$

Para conocer la notación Ω en el límite inferior, consulte Notación O grande . Se conocen límites más estrictos para familias de gráficos restringidas, lo que lleva a algoritmos eficientes para muchos problemas de optimización de gráficos en esas familias a través de la teoría de la bidimensionalidad . ^[21] El teorema de la cuadrícula de Halin proporciona un análogo de la relación entre el ancho del árbol y el tamaño menor de la cuadrícula para gráficos infinitos. ^[22]

Diámetro y ancho del árbol local.

Se dice que una familia F de gráficos cerrados tomando subgrafos tiene un ancho de árbol local acotado , o la propiedad diámetro-ancho del árbol , si el ancho de árbol de los gráficos de la familia está acotado superiormente por una función de su diámetro . Si también se supone que la clase está cerrada al aceptar menores , entonces F tiene un ancho de árbol local acotado si y sólo si uno de los menores prohibidos para F es un gráfico de vértices . ^[23] Las pruebas originales de este resultado mostraron que el ancho del árbol en una familia de gráficos sin ápice menor crece como máximo dos veces exponencialmente en función del diámetro; ^[24] más tarde esto se redujo a un exponencial simple ^[21] y finalmente a un límite lineal. ^[25] El ancho de árbol local acotado está estrechamente relacionado con la teoría algorítmica de la bidimensionalidad , ^[26] y cada propiedad de gráfico definible en lógica de primer orden se puede decidir para una familia de gráficos sin ápice menor en una cantidad de tiempo que es solo ligeramente superlineal. . ^[27]

También es posible que una clase de gráficos que no esté cerrada bajo menores tenga un ancho de árbol local limitado. En particular, esto es trivialmente cierto para una clase de gráficos de grados acotados, ya que los subgrafos de diámetro acotados tienen un tamaño acotado. Otro ejemplo lo dan los gráficos uniplanares , gráficos que se pueden dibujar en el plano con un cruce por arista y, más generalmente, los gráficos que se pueden dibujar sobre una superficie de género acotado con un número acotado de cruces por arista. Al igual que con las familias de gráficos menores cerrados de ancho de árbol local acotado, esta propiedad ha señalado el camino hacia algoritmos de aproximación eficientes para estos gráficos. ^[28]

Número de Hadwiger y funciones S

Halin (1976) define una clase de parámetros de gráficos que llama funciones S , que incluyen el ancho del árbol. Se requiere que estas funciones de gráficos a números enteros sean cero en gráficos sin aristas , que sean monótonas menores (una función f se denomina "monótona menor" si, siempre que H es menor de G , se tiene f ( H ) ≤ f ( G ) ), para aumentar en uno cuando se agrega un nuevo vértice que sea adyacente a todos los vértices anteriores y para tomar el valor mayor de los dos subgrafos a cada lado de un separador de camarilla . El conjunto de todas estas funciones forma una red completa bajo las operaciones de minimización y maximización por elementos. El elemento superior de esta red es el ancho del árbol y el elemento inferior es el número de Hadwiger , el tamaño del menor completo más grande en el gráfico dado.

Notas

1. Diestel (2005) págs. 354–355
2. Diestel (2005) sección 12.3
3. Seymour y Thomas (1993).
4. Bodlaender (1998).
5. Thorup (1998).
6. Robertson y Seymour (1986).
7. Arnborg, Proskurowski y Corneil (1990); Satyanarayana y Tung (1990).
8. Ramachandramurthi (1997).
9. Lagergren (1993).
10. Arnborg, Corneil y Proskurowski (1987).
11. Bodlaender (1996).
12. Kao (2008).
13. "Vibhav Gogate". personal.utdallas.edu . Consultado el 27 de noviembre de 2022 .
14. Gogate, Vibhav; Dechter, Rina (11 de julio de 2012). "Un algoritmo completo en cualquier momento para el ancho del árbol". arXiv : 1207.4109 [cs.DS].
15. "Mejor primera búsqueda de ancho de árbol". www.aaai.org . Consultado el 27 de noviembre de 2022 .
16. Bertelè y Brioschi (1972).
17. Arnborg y Proskurowski (1989); Berna, Lawler y Wong (1987); Bodlaender (1988).
18. Courcelle (1990); Courcelle (1992)
19. Robertson, Seymour. Graficar menores. V. Excluyendo un gráfico plano . [1]
20. Chekuri y Chuzhoy (2016)
21. Demaine y Hajiaghayi (2008).
22. Diéstel (2004).
23. Eppstein (2000).
24. Eppstein (2000); Demaine y Hajiaghayi (2004a).
25. Demaine y Hajiaghayi (2004b).
26. Demaine y col. (2004); Demaine y Hajiaghayi (2008).
27. Frick y Grohe (2001).
28. Grigoriev y Bodlaender (2007).

Referencias

• Amir, Eyal (2010), "Algoritmos de aproximación para el ancho de árbol", Algorithmica , 56 (4): 448–479, doi :10.1007/s00453-008-9180-4, MR  2581059, S2CID  5874913.
• Arnborg, S.; Corneil, D .; Proskurowski, A. (1987), "Complejidad de encontrar incrustaciones en un árbol ", Revista SIAM sobre análisis y aplicaciones de matrices , 8 (2): 277–284, doi :10.1137/0608024 ${\displaystyle k}$.
• Arnborg, Stefan; Proskurowski, Andrzej; Corneil, Derek G. (1990), "Caracterización de menores prohibidos de 3 árboles parciales", Matemáticas discretas , 80 (1): 1–19, doi : 10.1016/0012-365X(90)90292-P , MR  1045920.
• Arnborg, S.; Proskurowski, A. (1989), "Algoritmos de tiempo lineal para problemas NP-difíciles restringidos a árboles parciales ", Matemáticas Aplicadas Discretas , 23 (1): 11–24, doi : 10.1016/0166-218X(89)90031-0 ${\displaystyle k}$.
• Belbasi, Mahdi; Fürer, Martin (2021a), "Una mejora de la aproximación del ancho de árbol de Reed", en Uehara, Ryuhei; Hong, Seok-Hee ; Nandy, Subhas C. (eds.), WALCOM: Algoritmos y Computación – 15.ª Conferencia y Talleres Internacionales, WALCOM 2021, Yangon, Myanmar, 28 de febrero - 2 de marzo de 2021, Actas , Apuntes de conferencias en Ciencias de la Computación, vol. 12635, Springer, págs. 166–181, arXiv : 2010.03105 , doi : 10.1007/978-3-030-68211-8_14, MR  4239527, S2CID  222177100.
• Belbasi, Mahdi; Fürer, Martin (2021b), "Encontrar todos los separadores de tamaño situados más a la izquierda ", en Du, Ding-Zhu; Du, Donglei; Wu, Chenchén; Xu, Dachuan (eds.), Optimización y aplicaciones combinatorias - 15.ª Conferencia Internacional, COCOA 2021, Tianjin, China, 17-19 de diciembre de 2021, Actas , Apuntes de conferencias en Ciencias de la Computación, vol. 13135, Springer, págs. 273–287, arXiv : 2111.02614 , doi : 10.1007/978-3-030-92681-6_23, S2CID  242758210 ${\displaystyle \leq k}$
• Berna, MW; Lawler, EL ; Wong, AL (1987), "Cálculo en tiempo lineal de subgrafos óptimos de gráficos descomponibles", Journal of Algorithms , 8 (2): 216–235, doi :10.1016/0196-6774(87)90039-3.
• Bertelè, Umberto; Brioschi, Francesco (1972), Programación dinámica no serial, Academic Press, págs. 37–38, ISBN 978-0-12-093450-8.
• Bodlaender, Hans L. (1988), "Programación dinámica en gráficos con ancho de árbol acotado", Proc. XV Coloquio Internacional sobre Autómatas, Lenguajes y Programación , Apuntes de conferencias en Ciencias de la Computación, vol. 317, Springer-Verlag, págs. 105-118, CiteSeerX  10.1.1.18.8503 , doi :10.1007/3-540-19488-6_110, ISBN 978-3-540-19488-0.
• Bodlaender, Hans L. (1996), "Un algoritmo de tiempo lineal para encontrar descomposiciones de árboles de ancho pequeño", SIAM Journal on Computing , 25 (6): 1305–1317, CiteSeerX  10.1.1.19.7484 , doi :10.1137/S0097539793251219.
• Bodlaender, Hans L. (1998), "Un k -arboreto parcial de gráficos con ancho de árbol acotado", Ciencias de la Computación Teórica , 209 (1–2): 1–45, doi : 10.1016/S0304-3975(97)00228-4.
• Bodlaender, Hans L.; Drange, Pal G.; Dregi, Markus S.; Fomin, Fedor V.; Lokshtanov, Daniel; Pilipczuk, Michal (2016), "Un algoritmo de 5 aproximaciones para el ancho de árbol", SIAM Journal on Computing , 45 (2): 317–378, arXiv : 1304.6321 , doi : 10.1137/130947374 ${\displaystyle c^{k}n}$.
• Chekuri, Chandra; Chuzhoy, Julia (2016), "Límites polinomiales para el teorema de la cuadrícula menor", Journal of the ACM , 63 (5): A40:1–65, arXiv : 1305.6577 , doi :10.1145/2820609, MR  3593966, S2CID  209860422.
• Courcelle, B. (1990), "La lógica monádica de segundo orden de los gráficos I: conjuntos reconocibles de gráficos finitos", Información y Computación , 85 : 12–75, CiteSeerX  10.1.1.158.5595 , doi :10.1016/0890-5401 (90)90043-h.
• Courcelle, B. (1992), "La lógica monádica de segundo orden de los gráficos III: ancho de árbol, menores prohibidos y cuestiones de complejidad", Informatique Théorique (26): 257–286.
• Demaine, Erik D .; Fomin, Fedor V.; Hajiaghayi, Mohammad Taghi; Thilikos, Dimitrios M. (2004), "Parámetros bidimensionales y ancho de árbol local", Revista SIAM de Matemáticas Discretas , 18 (3): 501–511, CiteSeerX  10.1.1.107.6195 , doi :10.1137/S0895480103433410, MR  2134412, S2CID  803025.
• Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2004a), "Diámetro y ancho de árbol en familias de gráficos cerrados menores, revisado", Algorithmica , 40 (3): 211–215, doi :10.1007/s00453-004-1106-1, MR  2080518, S2CID  390856.
• Demaine, Erik D.; Hajiaghayi, MohammadTaghi (2004b), "Equivalencia de ancho de árbol local y ancho de árbol local lineal y sus aplicaciones algorítmicas", Actas del decimoquinto simposio anual ACM-SIAM sobre algoritmos discretos , Nueva York: ACM, págs. 840–849, MR  2290974.
• Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2008), "Linealidad de cuadrículas menores en ancho de árbol con aplicaciones mediante bidimensionalidad" (PDF) , Combinatorica , 28 (1): 19–36, doi :10.1007/s00493-008-2140-4, S2CID  16520181.
• Diestel, Reinhard (2004), "Una breve prueba del teorema de la cuadrícula de Halin", Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg , 74 : 237–242, doi :10.1007/BF02941538, MR  2112834, S2CID  124603912.
• Diestel, Reinhard (2005), Teoría de grafos (3.ª ed.), Springer , ISBN 978-3-540-26182-7.
• Eppstein, D. (2000), "Diámetro y ancho de árbol en familias de gráficos cerrados menores", Algorithmica , 27 (3–4): 275–291, arXiv : math/9907126 , doi :10.1007/s004530010020, MR  1759751, S2CID  3172160.
• Feige, Uriel; Hajiaghayi, Mohammad Taghi; Lee, James R. (2008), "Algoritmos de aproximación mejorados para separadores de vértices de peso mínimo", SIAM Journal on Computing , 38 (2): 629–657, CiteSeerX  10.1.1.597.5634 , doi :10.1137/05064299X.
• Fomin, Fedor V .; Todinca, Ioan; Villanger, Yngve (2015), "Grandes subgrafos inducidos mediante triangulaciones y CMSO", SIAM Journal on Computing , 44 (1): 54–87, arXiv : 1309.1559 , doi : 10.1137/140964801, S2CID  15880453.
• Frick, Markus; Grohe, Martin (2001), "Decisión de propiedades de primer orden de estructuras localmente descomponibles en árboles", Journal of the ACM , 48 (6): 1184–1206, arXiv : cs/0004007 , doi :10.1145/504794.504798, MR  2143836, S2CID  999472.
• Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Pilipczuk, Michal; Wrochna, Marcin (2018), "Cálculos totalmente parametrizados en tiempo polinomial para gráficos y matrices de ancho de árbol bajo", ACM Transactions on Algorithms , 14 (3): 34:1–34:45, arXiv : 1511.01379 , doi :10.1145/3186898 , S2CID  2144798.
• Grigoriev, Alejandro; Bodlaender, Hans L. (2007), "Algoritmos para gráficos integrables con pocos cruces por borde", Algorithmica , 49 (1): 1–11, CiteSeerX  10.1.1.65.5071 , doi :10.1007/s00453-007-0010-x , SEÑOR  2344391, S2CID  8174422.
• Halin, Rudolf (1976), " Funciones S para gráficas", Journal of Geometry , 8 (1–2): 171–186, doi :10.1007/BF01917434, S2CID  120256194.
• Kao, Ming-Yang, ed. (2008), "Ancho de árbol de gráficos", Enciclopedia de algoritmos, Springer, pág. 969, ISBN 9780387307701Otro problema abierto desde hace mucho tiempo es si existe un algoritmo de tiempo polinómico para calcular el ancho de árbol de gráficos planos.
• Korhonen, Tuukka (2021), "Un algoritmo de aproximación 2 de tiempo exponencial único para el ancho de árbol", Actas del 62.º Simposio anual del IEEE sobre los fundamentos de la informática , IEEE, págs. 184-192, arXiv : 2104.07463 , doi : 10.1109/ FOCS52979.2021.00026, S2CID  233240958.
• Lagergren, Jens (1993), "Un límite superior del tamaño de una obstrucción", Teoría de la estructura de grafos (Seattle, WA, 1991) , Matemáticas contemporáneas, vol. 147, Providence, RI: Sociedad Matemática Estadounidense, págs. 601–621, doi :10.1090/conm/147/01202, ISBN 9780821851609, señor  1224734.
• Lagergren, Jens (1996), "Algoritmos paralelos eficientes para gráficos de ancho de árbol acotado", Journal of Algorithms , 20 (1): 20–44, doi :10.1006/jagm.1996.0002, MR  1368716.
• Ramachandramurthi, Siddharthan (1997), "La estructura y el número de obstrucciones al ancho de los árboles", Revista SIAM de Matemáticas Discretas , 10 (1): 146–157, doi :10.1137/S0895480195280010, MR  1430552.
• Reed, Bruce A. (1992), "Encontrar separadores aproximados y calcular rápidamente el ancho del árbol", en Kosaraju, S. Rao; Compañeros, Mike; Wigderson, Avi; Ellis, John A. (eds.), Actas del 24º Simposio anual de ACM sobre teoría de la computación, 4 al 6 de mayo de 1992, Victoria, Columbia Británica, Canadá , ACM, págs. 221–228, doi : 10.1145/129712.129734 , S2CID  16259988.
• Robertson, Neil ; Seymour, Paul D. (1984), "Graph minors III: Planar tree-width", Journal of Combinatorial Theory , Serie B, 36 (1): 49–64, doi : 10.1016/0095-8956(84)90013-3.
• Robertson, Neil ; Seymour, Paul D. (1986), "Gráficos menores V: excluyendo un gráfico plano", Journal of Combinatorial Theory , Serie B, 41 (1): 92–114, doi : 10.1016/0095-8956(86)90030-4.
• Robertson, Neil ; Seymour, Paul D. (1995), "Graph Minors XIII: The Disjoint Paths Problem", Journal of Combinatorial Theory , Serie B, 63 (1): 65–110, doi : 10.1006/jctb.1995.1006.
• Robertson, Neil ; Seymour, Pablo ; Thomas, Robin (1994), "Excluyendo rápidamente un gráfico plano", Journal of Combinatorial Theory , Serie B, 62 (2): 323–348, doi : 10.1006/jctb.1994.1073 , MR  1305057.
• Satyanarayana, A.; Tung, L. (1990), "Una caracterización de 3 árboles parciales", Networks , 20 (3): 299–322, doi :10.1002/net.3230200304, MR  1050503.
• Seymour, Paul D .; Thomas, Robin (1993), "Búsqueda de gráficos y teorema mínimo-máximo para el ancho de árbol", Journal of Combinatorial Theory , Serie B, 58 (1): 22–33, doi : 10.1006/jctb.1993.1027.
• Shoikhet, Kirill; Geiger, Dan (1997), "Un algoritmo práctico para encontrar triangulaciones óptimas", en Kuipers, Benjamin; Webber, Bonnie L. (eds.), Actas de la Decimocuarta Conferencia Nacional sobre Inteligencia Artificial y la Novena Conferencia sobre Aplicaciones Innovadoras de Inteligencia Artificial, AAAI 97, IAAI 97, 27 al 31 de julio de 1997, Providence, Rhode Island, EE. UU. , AAAI Press / The MIT Press, págs. 185-190.
• Thorup, Mikkel (1998), "Todos los programas estructurados tienen un ancho de árbol pequeño y una buena asignación de registros", Información y Computación , 142 (2): 159–181, doi : 10.1006/inco.1997.2697.
• Korhonen, Tuukka; Lokshtanov, Daniel (2022), "Un algoritmo parametrizado mejorado para el ancho de árbol", arXiv : 2211.07154 [cs.DS].