Ancho del árbol

Número que indica la proximidad de un gráfico a un árbol

En teoría de grafos , el ancho de árbol de un grafo no dirigido es un número entero que especifica, informalmente, a qué distancia está el grafo de ser un árbol . El ancho de árbol más pequeño es 1; los grafos con ancho de árbol 1 son exactamente los árboles y los bosques . Los grafos con ancho de árbol como máximo 2 son los grafos serie-paralelos . Los grafos máximos con ancho de árbol exactamente k se denominan k -árboles , y los grafos con ancho de árbol como máximo k se denominan k -árboles parciales . ^[1] Muchas otras familias de grafos bien estudiadas también tienen 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 completitud cordal del gráfico, en términos del orden máximo 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 subgráficos conectados que se tocan entre sí.

El ancho del árbol se utiliza comúnmente como parámetro en el análisis de complejidad parametrizada de algoritmos de grafos . Muchos algoritmos que son NP-hard para grafos 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 . Más tarde fue redescubierto por Rudolf Halin  (1976), basándose en propiedades que comparte con un parámetro gráfico diferente, el número de Hadwiger . Más tarde fue redescubierto nuevamente por Neil Robertson y Paul Seymour  (1984) y desde entonces ha sido estudiado por muchos otros autores. ^[2]

Definición

Un gráfico con ocho vértices y una descomposición en árbol del mismo en un árbol con seis nodos. Cada arista 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 grafo 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 ^[3] (el término nodo se utiliza para referirse a un vértice de T para evitar confusiones con los vértices de G ):

1. La unión de todos los conjuntos Xi _es igual a V. Es decir, cada vértice del grafo está contenido en al menos un nodo del árbol.
2. Si X _i y X _j contienen ambos un vértice v , entonces todos los nodos X _k de T en la ruta (única) entre X _i y X _j contienen también v . De manera equivalente, los nodos del árbol que contienen el vértice v forman un subárbol conexo de T .
3. Para cada arista ( v , w ) del grafo, existe un subconjunto Xi que contiene tanto a v como _a w . Es decir, los vértices son adyacentes en el grafo solo cuando los subárboles correspondientes tienen un nodo en común.

El ancho de una descomposición en árbol es el tamaño de su conjunto más grande, Xi _, menos uno. El ancho de árbol tw( G ) de un grafo G es el ancho mínimo entre todas las descomposiciones en árbol posibles de G . En esta definición, el tamaño del conjunto más grande se reduce en uno para que el ancho de árbol 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 grafo cordal que contiene a G con el número de camarilla más pequeño . Un grafo cordal con este tamaño de camarilla se puede obtener agregando a G una arista entre cada dos vértices que pertenezcan a al menos uno de los conjuntos X _i .

El ancho de árbol también puede caracterizarse en términos de refugios , funciones que describen una estrategia de evasión para un cierto juego de persecución-evasión definido en un grafo. Un grafo G tiene un ancho de árbol k si y solo si tiene un refugio de orden k + 1 pero de ningún orden superior, donde un refugio de orden k + 1 es una función β que mapea cada conjunto X de como máximo k vértices en G en uno de los componentes conectados de G \ X y que obedece la propiedad de monotonía 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 realizar una caracterización similar utilizando 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). ^[4] El orden de una zarza es el conjunto de impacto más pequeño para la familia de subgrafos, y el ancho de árbol de un gráfico es uno menos que el orden máximo de una zarza.

Ejemplos

Todo grafo 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 grafos cordales: el grafo completo ya es cordal, y agregar más aristas no puede reducir el tamaño de su grupo más grande.

Un grafo conexo con al menos dos vértices tiene un ancho de árbol de 1 si y solo si es un árbol. Un árbol tiene un ancho de árbol de uno por el mismo razonamiento que para los grafos completos (es decir, es cordal y tiene un tamaño máximo de grupo de dos). Por el contrario, si un grafo tiene un ciclo, entonces cada completitud cordal del grafo incluye al menos un triángulo que consta de tres vértices consecutivos del ciclo, de lo que se sigue que su ancho de árbol es al menos dos.

Ancho de árbol limitado

Familias de gráficos con ancho de árbol acotado

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

Los grafos planares no tienen un ancho de árbol acotado, porque el grafo de cuadrícula n × n es un grafo planar con un ancho de árbol exactamente n . Por lo tanto, si F es una familia de grafos cerrada menor con un ancho de árbol acotado, no puede incluir todos los grafos planares. Por el contrario, si algún grafo planar no puede ocurrir como menor para los grafos de la familia F , entonces existe una constante k tal que todos los grafos en F tienen un ancho de árbol como máximo k . Es decir, las siguientes tres condiciones son equivalentes entre sí: ^[7]

1. F es una familia de gráficos de ancho de árbol acotado y menormente cerrados;
2. Uno de los muchos menores prohibidos que caracterizan a F es planar;
3. F es una familia de grafos menores cerrados que no incluye todos los grafos planares.

Menores prohibidos

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

Para cada valor finito de k , los grafos con un ancho de árbol de k como máximo pueden caracterizarse por un conjunto finito de menores prohibidos . (Es decir, cualquier grafo con un ancho de árbol > k incluye uno de los grafos del conjunto como menor). Cada uno de estos conjuntos de menores prohibidos incluye al menos un grafo planar.

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

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 . ^[9] 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. ^[10]

Algoritmos

Calcular el ancho del árbol

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

Debido a los roles que desempeña el ancho del árbol en una enorme cantidad de campos, se desarrollaron diferentes algoritmos prácticos y teóricos para calcular el ancho del árbol de un grafo. 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 grafo 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 o bien construye una descomposición del árbol del grafo de entrada G de ancho como máximo k o bien 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 o bien construye una descomposición en árbol del gráfico de entrada G con un ancho de como máximo 5 k + 4 o bien 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 sin resolver en matemáticas :

¿Es posible calcular el ancho de árbol de gráficos planares 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 planares es NP-completo o si su ancho de árbol se puede calcular en tiempo polinomial. ^[13]

En la práctica, un algoritmo de Shoikhet & Geiger (1997) puede determinar el ancho de árbol de grafos con hasta 100 vértices y hasta 11, encontrando una completitud cordal de estos grafos 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 ramificación y límite (BnB) y la búsqueda de mejor primero, para calcular el ancho del árbol. Estos algoritmos son útiles en cualquier momento , ya que, si se detienen antes, generarán un límite superior para el ancho del árbol.

El primer algoritmo BnB para calcular el ancho de árbol, llamado algoritmo QuickBB ^[14] fue propuesto por Gogate y Dechter ^[15] . Dado que la calidad de cualquier algoritmo BnB depende en gran medida de la calidad del límite inferior utilizado, Gogate y Dechter ^[15] también propusieron un algoritmo novedoso para calcular un límite inferior del ancho de árbol llamado minor-min-width ^[15] . En un nivel alto, el algoritmo minor-min-width combina los hechos de que el ancho de árbol de un grafo nunca es mayor que su grado mínimo o su menor para producir un límite inferior del ancho de árbol. El algoritmo minor-min-width construye repetidamente un menor de grafo contrayendo una arista 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 sea un límite inferior del ancho de árbol del grafo.

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

Solución de otros problemas en gráficos de árboles de pequeño ancho

A principios de la década de 1970, se observó que una gran clase de problemas de optimización combinatoria definidos en grafos se podían resolver de manera eficiente mediante programación dinámica no serial siempre que el grafo tuviera una dimensión acotada ^[17] , un parámetro que Bodlaender (1998) demostró que era equivalente al ancho del árbol. Más tarde, varios autores observaron de manera independiente a fines de la década de 1980 ^[18] que muchos problemas algorítmicos que son NP-completos para grafos arbitrarios se pueden resolver de manera eficiente mediante programación dinámica para grafos de ancho de árbol acotado, utilizando las descomposiciones en árbol de estos grafos.

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 en á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 se puede extender a todos los nodos descendientes en la descomposición en árbol, combinando información de un tipo similar calculada y almacenada 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 sea manejable con parámetros fijos .

Teorema de Courcelle

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

• Operaciones lógicas, como ${\displaystyle \wedge ,\vee ,\neg ,\Rightarrow }$
• Pruebas de pertenencia, 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 grafos. Para un grafo G = ( V , E ) , este problema plantea la pregunta de si es posible asignar a cada vértice v ∈ V uno de los 3 colores de modo que no haya dos vértices adyacentes con el mismo color asignado. 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, mediante los resultados de Courcelle, el problema de los 3 colores se puede resolver en tiempo lineal para un grafo dada una descomposición en árbol de ancho de árbol constante y acotado.

Parámetros relacionados

Ancho de ruta

El ancho de ruta de un grafo tiene una definición muy similar al ancho de árbol a través de descomposiciones de árboles, pero está restringido a descomposiciones de árboles en las que el árbol subyacente de la descomposición es un grafo de ruta . Alternativamente, el ancho de ruta se puede definir a partir de grafos de intervalo de manera análoga a la definición de ancho de árbol a partir de grafos cordales. Como consecuencia, el ancho de ruta de un grafo es siempre al menos tan grande como su ancho de árbol, pero solo puede ser mayor por un factor logarítmico. ^[5] Otro parámetro, el ancho de banda del grafo , tiene una definición análoga a partir de grafos 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 que está acotado para una familia de grafos cerrados menores si y solo si la familia excluye un camino, y la degeneración , una medida de la escasez de un grafo que es como máximo igual a su ancho de árbol.

Tamaño menor de la cuadrícula

Como 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 que el tamaño del menor cuadrado de cuadrícula más grande de G . En la otra dirección, el teorema del menor de cuadrícula de Robertson y Seymour muestra que existe una función ilimitada f tal que el menor cuadrado de cuadrícula más grande tiene un tamaño de al menos f ( r ) donde r es el ancho del árbol. ^[20] Los mejores límites conocidos en f son que f debe ser al menos Ω( r ^d ) para alguna constante fija d > 0 , y como máximo ^[21]

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

Para la notación Ω en el límite inferior, consulte la notación O grande . Se conocen límites más estrictos para familias de gráficos restringidas, lo que conduce 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 . ^[22] El teorema de 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. ^[23]

Diámetro y ancho local del árbol

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

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

Número de Hadwiger yS-funciones

Halin (1976) define una clase de parámetros de grafos que él llama S -funciones, que incluyen el ancho del árbol. Se requiere que estas funciones, desde grafos hasta números enteros, sean cero en grafos sin aristas , que sean menores monótonas (una función f se denomina "menor monótona" si, siempre que H es un menor de G , se tiene f ( H ​​) ≤ f ( G ) ), que aumenten en uno cuando se agrega un nuevo vértice que es adyacente a todos los vértices anteriores , y que tomen el valor más grande 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 elemento por elemento. El elemento superior en 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 grafo dado.

Notas

1. Bodlaender (1988).
2. Diestel (2005) págs. 354-355
3. Diestel (2005) sección 12.3
4. Seymour y Thomas (1993).
5. Bodlaender (1998).
6. Thorup (1998).
7. Robertson y Seymour (1986).
8. Arnborg, Proskurowski y Corneil (1990); Satyanarayana y Tung (1990).
9. Ramachandramurthi (1997).
10. Lagergren (1993).
11. Arnborg, Corneil y Proskurowski (1987).
12. Bodlaender (1996).
13. Ko (2008).
14. "Vibhav Gogate". personal.utdallas.edu . Consultado el 27 de noviembre de 2022 .
15. Gogate, Vibhav; Dechter, Rina (11 de julio de 2012). "Un algoritmo completo en cualquier momento para el ancho de árbol". arXiv : 1207.4109 [cs.DS].
16. "Búsqueda de mejor opción para el ancho de árbol". www.aaai.org . Consultado el 27 de noviembre de 2022 .
17. Bertelè y Brioschi (1972).
18. Arnborg y Proskurowski (1989); Berna, Lawler y Wong (1987); Bodlaender (1988).
19. Courcelle (1990); Courcelle (1992)
20. Robertson, Seymour. Gráficos menores. V. Excluyendo un gráfico plano . [1]
21. Chekuri y Chuzhoy (2016)
22. Demaine y Hajiaghayi (2008).
23. Diestel (2004).
24. Eppstein (2000).
25. Eppstein (2000); Demaine y Hajiaghayi (2004a).
26. Demaine y Hajiaghayi (2004b).
27. Demaine y col. (2004); Demaine y Hajiaghayi (2008).
28. Frick y Grohe (2001).
29. 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 la búsqueda de incrustaciones en un árbol ", SIAM Journal on Matrix Analysis and Applications , 8 (2): 277–284, doi :10.1137/0608024 ${\displaystyle k}$.
• Arnborg, Stefan; Proskurowski, Andrzej; Corneil, Derek G. (1990), "Caracterización de menores prohibidos de árboles 3 parciales", Discrete Mathematics , 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-hard restringidos a árboles parciales ", Discrete Applied Mathematics , 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: Algorithms and Computation – 15th International Conference and Workshops, WALCOM 2021, Yangon, Myanmar, 28 de febrero - 2 de marzo de 2021, Actas , Lecture Notes in Computer Science, vol. 12635, Springer, págs. 166–181, arXiv : 2010.03105 , doi :10.1007/978-3-030-68211-8_14, ISBN 978-3-030-68210-1, MR  4239527, S2CID  222177100.
• Belbasi, Mahdi; Fürer, Martin (2021b), "Encontrar todos los separadores de tamaño más a la izquierda ", en Du, Ding-Zhu; Du, Donglei; Wu, Chenchen; Xu, Dachuan (eds.), Optimización combinatoria y aplicaciones - 15.ª conferencia internacional, COCOA 2021, Tianjin, China, 17-19 de diciembre de 2021, Actas , Lecture Notes in Computer Science, vol. 13135, Springer, págs. 273–287, arXiv : 2111.02614 , doi :10.1007/978-3-030-92681-6_23, ISBN ${\displaystyle \leq k}$ 978-3-030-92680-9, Número de identificación del sujeto  242758210
• Bern, MW; Lawler, EL ; Wong, AL (1987), "Cálculo en tiempo lineal de subgrafos óptimos de grafos 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 grafos con ancho de árbol limitado", Proc. 15th International Colloquium on Automata, Languages ​​and Programming , Notas de clase en informática, 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 de árbol 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 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.; 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 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 grafos I: Conjuntos reconocibles de grafos 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 grafos III: Ancho de árbol, menores prohibidos y problemas de complejidad.", Informatique Théorique (26): 257–286.
• Demaine, Erik D .; Fomin, Fedor V.; Hajiaghayi, MohammadTaghi; Thilikos, Dimitrios M. (2004), "Parámetros bidimensionales y ancho de árbol local", SIAM Journal on Discrete Mathematics , 18 (3): 501–511, CiteSeerX  10.1.1.107.6195 , doi :10.1137/S0895480103433410, MR  2134412, S2CID  7803025.
• Demaine, Erik D. ; Hajiaghayi, MohammadTaghi (2004a), "Diámetro y ancho de árbol en familias de grafos menores cerrados, revisitado", 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 los menores de cuadrícula en el ancho del árbol con aplicaciones a través de la 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 grafos cerrados menores", Algorithmica , 27 (3–4): 275–291, arXiv : math/9907126 , doi :10.1007/s004530010020, MR  1759751, S2CID  3172160.
• Feige, Uriel; Hajiaghayi, MohammadTaghi; 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), "Decidir 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 parametrizados en tiempo polinomial completo 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, Alexander; Bodlaender, Hans L. (2007), "Algoritmos para gráficos integrables con pocos cruces por arista", Algorithmica , 49 (1): 1–11, CiteSeerX  10.1.1.65.5071 , doi :10.1007/s00453-007-0010-x, MR  2344391, S2CID  8174422.
• Halin, Rudolf (1976), " Funciones S para gráficos", Journal of Geometry , 8 (1–2): 171–186, doi :10.1007/BF01917434, S2CID  120256194.
• Kao, Ming-Yang, ed. (2008), "Ancho de árbol de grafos", Enciclopedia de algoritmos, Springer, pág. 969, ISBN 9780387307701Otro problema abierto desde hace mucho tiempo es si existe un algoritmo de tiempo polinomial para calcular el ancho de árbol de los gráficos planares.
• Korhonen, Tuukka (2021), "Un algoritmo de aproximación de tiempo exponencial simple 2 para el ancho de árbol", Actas del 62.º Simposio anual del IEEE sobre fundamentos de la informática , IEEE, págs. 184-192, arXiv : 2104.07463 , doi : 10.1109/FOCS52979.2021.00026, ISBN 978-1-6654-2055-6, Número de identificación del sujeto  233240958.
• Lagergren, Jens (1993), "Un límite superior para el tamaño de una obstrucción", Graph structure theory (Seattle, WA, 1991) , Contemporary Mathematics, vol. 147, Providence, RI: American Mathematical Society, págs. 601–621, doi :10.1090/conm/147/01202, ISBN 9780821851609, Sr.  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 del árbol", SIAM Journal on Discrete Mathematics , 10 (1): 146–157, doi :10.1137/S0895480195280010, MR  1430552.
• Reed, Bruce A. (1992), "Cómo encontrar separadores aproximados y calcular rápidamente el ancho de un árbol", en Kosaraju, S. Rao; Fellows, Mike; Wigderson, Avi; Ellis, John A. (eds.), Actas del 24.º Simposio anual de la ACM sobre teoría de la computación, 4-6 de mayo de 1992, Victoria, Columbia Británica, Canadá , ACM, págs. 221–228, doi : 10.1145/129712.129734 , ISBN 0-89791-511-9, S2CID16259988 ​.
• 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), "Grafos menores V: Excluyendo un grafo planar", 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: El problema de los caminos disjuntos", Journal of Combinatorial Theory , Serie B, 63 (1): 65–110, doi : 10.1006/jctb.1995.1006.
• Robertson, Neil ; Seymour, Paul ; Thomas, Robin (1994), "Exclusión rápida de un gráfico planar", 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 árboles 3 parciales", Networks , 20 (3): 299–322, doi :10.1002/net.3230200304, MR  1050503.
• Seymour, Paul D. ; Thomas, Robin (1993), "Búsqueda de grafos y un teorema de 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 Novena Conferencia sobre Aplicaciones Innovadoras de la Inteligencia Artificial, AAAI 97, IAAI 97, 27-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].