En teoría de grafos , el ancho de árbol de un grafo no dirigido es un número entero que especifica, informalmente, qué tan lejos está el gráfico de ser un árbol . El ancho de árbol más pequeño es 1; los gráficos con un ancho de árbol 1 son exactamente los árboles y los bosques . Los gráficos con un ancho de árbol como máximo 2 son los gráficos en serie-paralelos . Los gráficos máximas con treewidth exactamente k se llaman k-árboles , y los gráficos con treewidth a lo sumo k se llaman parciales k -Los árboles . Muchas otras familias de gráficos bien estudiadas también tienen un ancho de árbol limitado.
El ancho del árbol puede definirse formalmente de varias formas equivalentes: el tamaño del conjunto de vértices más grande en una descomposición de árbol del gráfico, el tamaño de la camarilla más grande en una terminación cordal del gráfico, el orden máximo de un refugio que describe una estrategia para un juego de persecución-evasión en el gráfico, o el orden máximo de una zarza , una colección de subgrafos conectados que se tocan entre sí.
Treewidth 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
Una descomposición de árbol de un gráfico G = ( V , E ) es un árbol, T , con nodos X 1 , ..., X n , donde cada X i es un subconjunto de V , que satisface las siguientes propiedades [2] (el El término nodo se usa para referirse a un vértice de T para evitar confusión con los vértices de G ):
- 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 de árbol.
- 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 también contienen v . De manera equivalente, los nodos del árbol contienen vértice v forman un subárbol conectado de T .
- Para cada borde ( v , w ) en la gráfica, hay un subconjunto X i que contiene tanto v como w . Es decir, los vértices son adyacentes en el gráfico solo 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 treewidth tw ( G ) de un gráfico G es la anchura mínima entre todos los posibles descomposición en árbol de G . En esta definición, el tamaño del conjunto más grande se reduce en uno para hacer 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 de cuerdas que contiene a G con el número de camarilla más pequeño . Se puede obtener un grafo cordal con este tamaño de camarilla agregando a G una arista entre cada dos vértices que pertenezcan al menos a uno de los conjuntos X i .
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 definida en un gráfico. Un gráfico G tiene un ancho de árbol k si y solo 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 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 a la monotonicidad propiedad que β ( y ) ⊆ β ( X ) cuando X ⊆ y .
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 subgráficos, y el ancho de árbol de una gráfica es uno menos que el orden máximo de una zarza.
Ejemplos de
Cada 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 camarilla más grande.
Un gráfico conectado con al menos dos vértices tiene un ancho de árbol 1 si y solo 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 máximo de camarilla dos). Por el contrario, si una gráfica tiene un ciclo, entonces cada terminación cordal de la gráfica incluye al menos un triángulo que consta de tres vértices consecutivos del ciclo, del cual se deduce que su ancho de árbol es al menos dos.
Ancho de árbol limitado
Grafica familias con ancho de árbol acotado
Para cualquier constante fijo k , los gráficos de las treewidth en la mayoría de k son llamados los parciales k -Los árboles . Otras familias de gráficos con un ancho de árbol limitado incluyen los gráficos de cactus , pseudoforestales , gráficos de series paralelas , gráficos de planos exteriores , gráficos de Halin y 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 acotado, 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 alguna gráfica plana no puede ocurrir como menor para las gráficas de la familia F , entonces hay una constante k tal que todas las gráficas en F tienen un ancho de árbol como máximo k . Es decir, las siguientes tres condiciones son equivalentes entre sí: [6]
- F es una familia menor cerrada de gráficos de ancho de árbol acotado;
- Uno de los pocos menores prohibidos que caracterizan a F es plano;
- F es una familia de gráficos menores cerrados que no incluye todos los gráficos planos.
Menores prohibidos
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 menor prohibido único es un gráfico de ciclo de 3 vértices . [7]
- Para k = 2, el único menor prohibido es el gráfico completo de 4 vértices K 4 . [7]
- Para k = 3, hay cuatro menores prohibidos: K 5 , 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 la 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 G dado tiene un ancho de árbol como máximo para una variable k dada . [11] Sin embargo, cuando k es cualquier constante fija, las gráficas con ancho de árbol k pueden ser reconocidas y una descomposición de árbol de ancho k construida para ellas, en tiempo lineal. [12] La dependencia del tiempo de este algoritmo en k es exponencial.
Debido al papel que juega 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 disponible, 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í es el ancho del árbol y es el número de vértices de un gráfico de entrada . Cada uno de los algoritmos da salida a tiempouna descomposición de la anchura dada en la columna Aproximación. Por ejemplo, el algoritmo de Bodlaender (1996) en el tiempo o bien construye una descomposición de árbol del gráfico de entrada de ancho como máximo o informa que el ancho del árbol de Es mas que . Del mismo modo, el algoritmo de Bodlaender et al. (2016) en el tiempo o bien construye una descomposición de árbol del gráfico de entrada de ancho como máximo o informa que el ancho del árbol de Es mas que . Korhonen (2021) mejoró esto para en el mismo tiempo de ejecución.
Aproximación | f (k) | g (n) | referencia |
---|---|---|---|
exacto | Arnborg, Corneil y Proskurowski (1987) | ||
Robertson y Seymour (1995) | |||
exacto | Bodlaender (1996) | ||
Feige, Hajiaghayi y Lee (2008) | |||
exacto | Fomin, Todinca y Villanger (2015) | ||
Bodlaender y col. (2016) | |||
Fomin y col. (2018) | |||
Korhonen (2021) |
¿Se puede calcular el ancho de árbol de las gráficas planas en tiempo polinomial?
No se sabe si la determinación del ancho de árbol de las gráficas planas 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 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.
Resolver otros problemas en gráficas de pequeño ancho de árbol
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 de manera eficiente mediante programación dinámica no serial siempre que el gráfico tuviera una dimensión acotada , [14] un parámetro que se demostró que es equivalente a treewidth por Bodlaender (1998) . Posteriormente, varios autores observaron independientemente a finales de la década de 1980 [15] que muchos problemas algorítmicos 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 puede resolverse utilizando un algoritmo de programación dinámica en una descomposición de á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 ese color es válido y puede extenderse a todos los nodos descendientes en la descomposición del árbol, combinando información de una estructura 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 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 de árbol con un ancho de árbol acotado constante. Específicamente, el teorema de Courcelle [16] [17] establece que si un problema de gráfico puede expresarse en la lógica de gráficos usando lógica monádica de segundo orden , entonces puede resolverse 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 gráficas que utiliza las siguientes construcciones: operaciones lógicas (), pruebas de membresía (p. ej., ), cuantificaciones sobre vértices, aristas, conjuntos de vértices, conjuntos de aristas (p. ej., , , , ), pruebas de adyacencia ( u es un punto final de e ) y algunas extensiones que permiten cosas como la optimización.
Considere, por ejemplo, el problema de tres colores para gráficos. Para un gráfico, este problema pregunta si es posible asignar cada vértice 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:
- ,
dónde 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 3 colores se puede resolver en tiempo lineal para un gráfico dada una descomposición de á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 a través de descomposiciones de árboles, pero está restringido a las descomposiciones de árboles en las que el árbol subyacente de la descomposición es un gráfico de ruta . Alternativamente, el ancho de ruta puede definirse a partir de gráficos de intervalo de forma análoga a la definición de ancho de árbol a partir de gráficos cordales. Como consecuencia, el ancho de ruta de un gráfico siempre es al menos tan grande como el ancho de su árbol, pero solo 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 de los gráficos de intervalo adecuados , y es al menos tan grande como el ancho de la ruta. Otros parámetros relacionados incluyen la profundidad del árbol , un número que está acotado para una familia de gráficos cerrados menores si y solo 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 de árbol.
Tamaño menor de cuadrícula
Debido a que el treewidth de un n × n gráfico de la red es n , el treewidth de un gráfico G es siempre mayor que o igual al tamaño de la más grande de cuadrícula menor de G . En la otra dirección, el teorema de la cuadrícula menor de Robertson y Seymour muestra que existe una función f tal que el ancho del árbol es como máximo f ( r ) donde r es el tamaño de la cuadrícula menor cuadrada más grande. [18] 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 O ( √ r / log r ). [19] Se conocen límites más estrechos para familias de gráficos restringidos, 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 . [20] 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. [21]
Diámetro y ancho de árbol local
Se dice que una familia F de gráficos cerrados con subgráficos tiene un ancho de árbol local acotado , o la propiedad diámetro-ancho de árbol , si el ancho de árbol de los gráficos de la familia está acotado por una función de su diámetro . Si también se supone que la clase está cerrada para menores de edad , entonces F tiene un ancho de árbol local limitado si y solo si uno de los menores prohibidos para F es un gráfico de vértice . [22] Las pruebas originales de este resultado mostraron que el ancho de árbol en una familia de gráficos sin ápice menor crece como mucho doblemente exponencialmente en función del diámetro; [23] más tarde esto se redujo a exponencial simple [20] y finalmente a un límite lineal. [24] El ancho de árbol local limitado está estrechamente relacionado con la teoría algorítmica de la bidimensionalidad , [25] y cada propiedad de gráfico definible en la 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 . [26]
También es posible que una clase de gráficos que no está cerrada para 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 acotado tienen un tamaño acotado. Otro ejemplo lo dan los gráficos 1-planar , gráficos que se pueden dibujar en el plano con un cruce por borde y, más generalmente, los gráficos que se pueden dibujar en una superficie de género acotado con un número limitado de cruces por borde. 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. [27]
Número de Hadwiger y funciones S
Halin (1976) define una clase de parámetros de gráficos que él llama funciones S , que incluyen el ancho del árbol. Estas funciones, desde gráficas hasta números enteros, deben ser cero en gráficas sin aristas , ser 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 adyacente a todos los vértices anteriores, y para tomar el valor más grande de los dos subgráficos a cada lado de un separador de camarillas . El conjunto de todas estas funciones forma una red completa bajo las operaciones de minimización y maximización de elementos. El elemento superior en esta celosía 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
- ^ Diestel (2005) págs . 354–355
- ^ Diestel (2005) sección 12.3
- ^ Seymour y Thomas (1993) .
- ↑ a b Bodlaender (1998) .
- ^ Thorup (1998) .
- ^ Robertson y Seymour (1986) .
- ↑ a b Bodlaender (1988) .
- ^ Arnborg, Proskurowski y Corneil (1990) ; Satyanarayana y Tung (1990) .
- ^ Ramachandramurthi (1997) .
- ^ Lagergren (1993) .
- ^ Arnborg, Corneil y Proskurowski (1987) .
- ^ Bodlaender (1996) .
- ^ Kao (2008) .
- ^ Bertelè y Brioschi (1972) .
- ^ Arnborg y Proskurowski (1989) ; Bern, Lawler y Wong (1987) ; Bodlaender (1988) .
- ^ 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: Treewidth, menores prohibidos y cuestiones de complejidad". Informatique Théorique (26): 257–286.
- ^ Robertson, Seymour. Graficar menores. V. Excluyendo un gráfico plano . [1]
- ^ Chekuri y Chuzhoy (2016) . Para la notación Ω en el límite inferior, vea la notación O grande .
- ↑ a b Demaine y Hajiaghayi (2008) .
- ^ Diestel (2004) .
- ^ Eppstein (2000) .
- ^ Eppstein (2000) ; Demaine y Hajiaghayi (2004a) .
- ^ Demaine y Hajiaghayi (2004b) .
- ^ Demaine y col. (2004) ; Demaine y Hajiaghayi (2008) .
- ^ Frick y Grohe (2001) .
- ^ Grigoriev y Bodlaender (2007) .
Referencias
- Arnborg, S .; Corneil, D .; Proskurowski, A. (1987), "Complejidad de encontrar incrustaciones en un árbol k ", SIAM Journal on Matrix Analysis and Applications , 8 (2): 277-284, doi : 10.1137 / 0608024.
- 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 k parciales", Matemáticas aplicadas discretas , 23 (1): 11-24, doi : 10.1016 / 0166-218X (89) 90031- 0.
- Berna, MW; Lawler, EL ; Wong, AL (1987), "Cálculo en tiempo lineal de subgráficos ó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 en serie , 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 , Lecture Notes in Computer Science, 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 pequeño ancho de árbol", 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óricas , 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), "A c ^ kn 5-Approximation Algorithm for Treewidth", SIAM Journal on Computing , 45 (2): 317–378, arXiv : 1304.6321 , doi : 10.1137 / 130947374.
- 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.
- 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.
- Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2004a), "Diameter and treewidth in minor-closed graph familias, revisited", Algorithmica , 40 (3): 211–215, doi : 10.1007 / s00453-004-1106-1 , MR 2080518 , S2CID 390856.
- Demaine, Erik D .; Hajiaghayi, MohammadTaghi (2004b), "Equivalence of local treewidth and linear local treewidth and its algorítmic applications", 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), "Lineality of grid minors in treewidth with applications through bidimensionality" (PDF) , Combinatorica , 28 (1): 19–36, doi : 10.1007 / s00493-008-2140-4 , S2CID 16520181.
- Diestel, Reinhard (2004), "Una breve demostración 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), Graph Theory (3.a 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, 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.
- Frick, Markus; Grohe, Martin (2001), "La decisión propiedades de primer orden de las estructuras locales de árboles descomponible", Revista de la ACM , 48 (6): 1184-1206, arXiv : cs / 0004007 , doi : 10.1145 / 504,794.504798 , MR 2.143.836 , 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 bajo ancho de árbol", ACM Trans. Algoritmos , 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 incrustables con pocos cruces por borde", 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), "Treewidth of graphs", Enciclopedia de algoritmos , Springer, p. 969, ISBN 9780387307701,
Otro problema abierto largo de pie es si hay un algoritmo de tiempo polinómico para calcular la treewidth de grafos planos.
- Korhonen, Tuukka (2021), algoritmo de aproximación de 2 tiempos exponencial simple para ancho de árbol , arXiv : 2104.07463
- Lagergren, Jens (1993), "Un límite superior en el tamaño de una obstrucción", Teoría de la estructura de grafos (Seattle, WA, 1991) , Contemporary Mathematics, 147 , Providence, RI: American Mathematical Society, págs. 601–621, doi : 10.1090 / conm / 147/01202 , ISBN 9780821851609, MR 1224734.
- 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.
- 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), "Graph minors 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, Paul ; 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 tres á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 un teorema mínimo-máximo para el ancho del á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", Proc. AAAI '97 (PDF) , 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", Information and Computation , 142 (2): 159-181, doi : 10.1006 / inco.1997.2697.
- Fomin, Fedor V .; Todinca, Ioan; Villanger, Yngve (2015), "Large Induced Subgraphs via Triangulations and CMSO", SIAM Journal on Computing , 44 (1): 54–87, arXiv : 1309.1559 , doi : 10.1137 / 140964801 , S2CID 15880453.