Largura de caminho: diferenças entre revisões

← Ver a alteração anterior Ver a alteração posterior →

Conteúdo apagado Conteúdo adicionado

Em linha

Revisão das 00h08min de 6 de julho de 2015

Em teoria dos grafos, uma decomposição em caminho de um grafo G é, informalmente, uma representação de G como um caminho "alargado",^[1] e a largura de caminho de G é um número que mensura quanto o caminho foi ampliado em largura a partir de G. Mais formalmente, decomposição em caminho é uma sequência de subconjuntos de vértices de G em que os nós extremos de cada aresta apareçam em um dos subconjuntos e que cada vértice apareça em uma subsequência adjacente dos subconjuntos,^[2] e o caminho de largura é um a menos que o tamanho do maior conjunto em dada decomposição. Largura de caminho é também conhecida como largura de intervalo (um a menos que o tamanho do clique máximo em um supergrafo de intervalo de G), número de separação de vértice, ou número de busca de nós.^[3] Largura de caminho é também conhecida como largura de intervalo (um a menos que o tamanho do clique máximo em um supergrafo de intervalo de G), número de separação de vértice, ou número de busca de nós.

↑ Diestel & Kühn (2005).
↑ Robertson & Seymour (1983).
↑ Bodlaender (1998).

Largura de caminho e decomposições de caminho são aproximadamente análogo a largura de árvore e decomposição de árvores. Têm um papel fundamental na teoria de grafos menores: as famílias de grafos que são fechadas sob grafos menores e não incluem todas florestas devem ser caracterizadas como tendo caminhos de largura delimitados,^[1] e os vórtices que aparecem na teoria da estrutura para família de grafos menores fechados tem caminhos de largura delimitados.^[2] Largura de caminho, e grafos de largura de caminho delimitados, possuem também aplicações em design de VLSI, desenho de grafos, and linguística computacional.

É NP-difícil encontrar o largura de caminho de grafos arbitrários, ou até mesmo fazer uma aproximação cuidadosamente.^[3]^[4] De qualquer maneira, o problema é tratável por parâmetro fixo: testando se um grafo de largura de caminho k pode ser resolvido em um espaço de tempo que depende linearmente do tamanho do grafo mas super-exponencialmente em k.^[5] Além disso, para várias classes especiais de grafos, como árvores, o largura de caminho pode ser computado em tempo polinomial sem dependência em k.^[6]^[7] Muitos problemas em algoritmos de grafos podem ser resolvidos eficientemente em grafos de largura de caminho delimitados, usando programação dinâmica em uma decomposição em caminho do grafo.^[8] Decomposição em caminho pode também ser usada para medir complexidade de espaço de algoritmos de programação dinâmica em grafos de largura de árvore (teoria dos grafos.^[9]

Definição

No primeiro de sua famosa série de artigos sobre grafos menores, Neil Robertson e Paul Seymour (1983) definiram a decomposição em caminho de um grafo G ser uma sequência de subconjuntos de X_i de vértices de G, com duas propriedades:

Para cada aresta de G, há um i que ambos extremos (vértices) da aresta pertencem ao subconjuntoX_i; e
Para cada três índices i ≤ j ≤ k, X_i ∩ X_k ⊆ X_j.

A segunda dessas propriedades é equivalente a requerir que os subconjuntos contendo quaisquer vértices específicos formam uma subsequência adjacente da sequência inteira. Nas definições encontradas nos últimos artigos sobre grafos menores de Robertson e Seymour, uma decomposição em caminho é uma decomposição em árvore (X,T) em que a árvore subjacente T da decomposição é um caminho.

A largura de uma decomposição em caminho é definida da mesma maneira que é para uma decomposição em árvore, como max_i |X_i| − 1, e a largura de caminho de G é a largura mínima de quaisquer decomposições em caminho de G. A subtração de um do tamanho de X_i nessa definição faz pouca diferença na maioria da aplicações de largura de caminho, mas é usada para estabelecer o largura de caminho de um grafo caminho como sendo igual a um.

Caracterizações alternativas

Como Bodlaender (1998) descreve, largura de caminho de várias maneiras equivalentes.

Sequências de colagem

Uma decomposição em caminho pode ser descrita com uma sequência de grafos G_i que são "colados" juntos identificando pares de vértices de grafos consecutivos na sequência. de modo que o resultado da excução de todas essas colagens é G. Os grafos G_i devem ser considerados como os subgrafos induzidos por vértice dos conjuntos X_i na primeira definição das decomposições em caminho, com dois vértices em sucessivos subgrafos induzidos em serem colados conjuntamente quando eles são induzidos pelo mesmo vértice em G, e em outra direção pode-se recuperar os conjuntos X_i como os conjuntos de nós dos grafos G_i. A largura da decomposição em caminho é então um menor que o número máximo de vértices em um dos grafos G_i.^[1]

Largura de intervalo

A largura de caminho de qualquer grafo G é igual a um a menos que a quantidade dos menores cliques de um grafo de intervalos que contém G como subgrafo.^[10] Isto é, para cada decomposição em caminho de G pode-se procurar um super-grafo de intervalos de G, e para cada super-grafo de intervalos pode-se encontrar uma decomposição em caminho de G, tanto que a largura da decomposição seja uma menor que o numero de cliques do grafo de intervalos.

Por um lado, supondo que uma decomposição de caminho de G é dada. Então é possível representar os nó da decomposição como pontos em uma linha (em forma de um caminho) e representar cada vértice v como um intervalo fechado contendo esses pontos como extremos. Logo, os nós da decomposição de caminho compreendendo v correspondem aos pontos representativos no intervalo para v. O grafo de interseção dos intervalos formados dos vértices de G é um grafo de intervalos que engloba G como um subgrafo. Seus cliques máximos são dados pelos conjuntos de intevalos contendo os pontos representativos, e o tamanho do seu clique máximo é um mais a largura de caminho de G.

Por outro lado, se G é um subgrafo de um grafo de intervalos com número de cliques p + 1, então G tem uma decomposição de caminho com largura p, tal que seus nós são dados pelos cliques máximos do grafo de intervalos. Para exemplo, o gráfico de intervalos mostrado com sua representação de intervalos na figura ao lado tem uma decomposição de caminho com cinco nós, correspondendo aos seus cinco cliques máximos ABC, ACD, CDE, CDF, and FG; o tamanho do clique máximo é três e a largura dessa decomposição de caminho é dois.

Esta equivalência entre a largura de caminho e a largura de intervalo é aproximadamente análoga à equivalência entre largura de árvore e número de cliques mínimos (menos um) de um grafo cordal de que dado grafo é um subgrafo. Grafos de intervalos são um caso especial de grafos cordais, e grafos cordais podem ser representado como grafos de interseção de subárvores de uma árvore comum generalizando o modo que os grafos de intervalos são grafos de interseção de subcaminho de um caminho.

Número de separação de vértices

Supondo que os vértices de um grafo G são linearmente ordenados, então o número de separação de vértices de G é o menor número s que, para cada vértice v, no máximo s vértices são anteriores a v na ordenação mas que tem v ou um vértice posterior como vizinho.

O número de separação de vértices de G é o número de separação de vértices mínimo de quaisquer ordenações lineares de G. O número de separação de vértices foi definido por Ellis, Sudborough & Turner (1983), e é igual à largura de caminho de G.^[11] Isso resulta da correspondência anterior com números de cliques em grafos de intervalos: se G é um subgrafo de um grafo de intervalos I, representado (como na figura) de modo que todos os nós extremos dos intervalos são distintos, então a ordenação dos nós extremos da esquerda do intervalo de I têm número de separação de vértices um menor que o número de cliques de I. E, por outro lado, a partir de uma ordenação linear de G, é praticável a derivação de uma representação de intervalos de modo que o extremo esquerdo de um intervalo para um vértice v esteja em sua posição na ordenação em ao extremo direito está a posição do vizinho de v que vem por último na ordenação.

Número de busca de nós

O jogo de busca de nós em um grafo é uma forma de perseguição e fuga, no qual um conjunto de investigadores colaboram para rastrear um fugitivo escondido em um grafo. Os rastreadores estão dispostos em vértices do grafo enquanto o fugitivo podem estar em qualquer aresta do grafo, e a localização do fugitivo e seus movimentos são ocultados dos investigadores. A cada turno, alguns ou todos os rastreadores podem se mover (arbitrariamente, não necessariamente ao longo das arestas) de um vértice a outro, e, então, o fugitivo tem o poder de se movimentar por qualquer caminho no grafo que não passe por um vértice ocupado por um investigador. O fugitivo é pego quando ambos extremos de sua aresta estão tomados por rastreadores. O número de busca de nós de um grafo é o número mínimo de rastreadores necessários para assegurar que haja a garantia de o fugitivo ser pego, independente de seu movimento. Como Kirousis & Papadimitriou (1985) mostram, o número de busca de nós de um grafo é igual a sua largura de intervalo. A estratégia ótima para rastreadores é se movimentar de maneira em que em sucessivos turnos formem os conjuntos de separação de uma ordenação linear com número mínimo de vértices.

Notes

↑ ^a ^b Erro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome rs83
↑ Robertson & Seymour (2003).
↑ Erro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome npc
↑ Bodlaender et al. (1992).
↑ Erro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome bounded-tw-algs
↑ Bodlaender (1994).
↑ Erro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome tree-algs
↑ Arnborg (1985).
↑ Aspvall, Proskurowski & Telle (2000).
↑ Bodlaender (1998), Theorem 29, p. 13.
↑ Kinnersley (1992); Bodlaender (1998), Theorem 51.

References

Alon, Noga; Seymour, Paul; Thomas, Robin (1990), «A separator theorem for graphs with an excluded minor and its applications», Proc. 22nd ACM Symp. on Theory of Computing (STOC 1990), ISBN 0897913612, pp. 293–299, doi:10.1145/100216.100254 .
Amini, Omid; Huc, Florian; Pérennes, Stéphane (2009), «On the path-width of planar graphs», SIAM Journal on Discrete Mathematics, 23 (3): 1311–1316, doi:10.1137/060670146 .
Arnborg, Stefan (1985), «Efficient algorithms for combinatorial problems on graphs with bounded decomposability – A survey», BIT, 25 (1): 2–23, doi:10.1007/BF01934985 .
Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej (1987), «Complexity of finding embeddings in a $k$-tree», SIAM Journal on Algebraic and Discrete Methods, 8 (2): 277–284, doi:10.1137/0608024 .
Aspvall, Bengt; Proskurowski, Andrzej; Telle, Jan Arne (2000), «Memory requirements for table computations in partial k-tree algorithms», Algorithmica, 27 (3): 382–394, doi:10.1007/s004530010025 .
Berge, Claude (1967), «Some classes of perfect graphs», Graph Theory and Theoretical Physics, New York: Academic Press, pp. 155–165 .
Bienstock, Dan; Robertson, Neil; Seymour, Paul; Thomas, Robin (1991), «Quickly excluding a forest», Journal of Combinatorial Theory, Series B, 52 (2): 274–283, doi:10.1016/0095-8956(91)90068-U .
Björklund, Andreas; Husfeldt, Thore (2008), «Exact algorithms for exact satisfiability and number of perfect matchings», Algorithmica, 52 (2): 226–249, doi:10.1007/s00453-007-9149-8 .
Bodlaender, Hans L. (1994), «A tourist guide through treewidth», in: Dassow, Jürgen; Kelemenová, Alisa, Developments in Theoretical Computer Science (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 November 1992), Topics in Computer Mathematics, 6, Gordon and Breach, pp. 1–20 .
Bodlaender, Hans L. (1996), «A linear-time algorithm for finding tree-decompositions of small treewidth», SIAM Journal on Computing, 25 (6): 1305–1317, doi:10.1137/S0097539793251219 .
Bodlaender, Hans L. (1998), «A partial k-arboretum of graphs with bounded treewidth», Theoretical Computer Science, 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4 .
Bodlaender, Hans L.; Fomin, Fedor V. (2002), «Approximation of pathwidth of outerplanar graphs», 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), «Approximating treewidth, pathwidth, and minimum elimination tree height», Graph-Theoretic Concepts in Computer Science, ISBN 978-3-540-55121-8, Lecture Notes in Computer Science, 570, pp. 1–12, doi:10.1007/3-540-55121-2_1 .
Bodlaender, Hans L.; Gustedt, Jens; Telle, Jan Arne (1998), «Linear-time register allocation for a fixed number of registers», Proc. 9th ACM–SIAM Symposium on Discrete Algorithms (SODA '98) (PDF), pp. 574–583 .
Bodlaender, Hans L.; Kloks, Ton (1996), «Efficient and constructive algorithms for the pathwidth and treewidth of graphs», Journal of Algorithms, 21 (2): 358–402, doi:10.1006/jagm.1996.0049 .
Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter (1993), «Treewidth and pathwidth of permutation graphs», Proc. 20th International Colloquium on Automata, Languages and Programming (ICALP 1993), ISBN 978-3-540-56939-8, Lecture Notes in Computer Science, 700, Springer-Verlag, pp. 114–125, doi:10.1007/3-540-56939-1_66 .
Bodlaender, Hans L.; Möhring, Rolf H. (1990), «The pathwidth and treewidth of cographs», Proc. 2nd Scandinavian Workshop on Algorithm Theory, ISBN 978-3-540-52846-3, Lecture Notes in Computer Science, 447, Springer-Verlag, pp. 301–309, doi:10.1007/3-540-52846-6_99 .
Cattell, Kevin; Dinneen, Michael J.; Fellows, Michael R. (1996), «A simple linear-time algorithm for finding path-decompositions of small width», Information Processing Letters, 57 (4): 197–203, doi:10.1016/0020-0190(95)00190-5 .
Coudert, David; Huc, Florian; Mazauric, Dorian (1998), «A distributed algorithm for computing and updating the process number of a forest», Proc. 22nd Int. Symp. Distributed Computing, ISBN 978-3-540-87778-3, Lecture Notes in Computer Science, 5218, Springer-Verlag, pp. 500–501, arXiv:0806.2710, doi:10.1007/978-3-540-87779-0_36 .
Coudert, David; Huc, Florian; Sereni, Jean-Sébastien (2007), «Pathwidth of outerplanar graphs», 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), «Graph minor hierarchies», Discrete Applied Mathematics, 145 (2): 167–182, doi:10.1016/j.dam.2004.01.010 .
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi (2005), «Algorithmic graph minor theory: decomposition, approximation, and coloring», Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005), ISBN 0-7695-2468-0, pp. 637–646, doi:10.1109/SFCS.2005.14 .
Downey, Rod G.; Fellows, Michael R. (1999), Parameterized Complexity, ISBN 0-387-94883-X, Springer-Verlag .
Dujmović, V.; Fellows, M.R.; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; et al. (2008), «On the parameterized complexity of layered graph drawing», Algorithmica, 52 (2): 267–292, doi:10.1007/s00453-007-9151-1 .
Dujmović, Vida; Morin, Pat; Wood, David R. (2003), «Path-width and three-dimensional straight-line grid drawings of graphs» (PDF), Proc. 10th International Symposium on Graph Drawing (GD 2002), Lecture Notes in Computer Science, 2528, Springer-Verlag, pp. 42–53 .
Ellis, J. A.; Sudborough, I. H.; Turner, J. S. (1983), «Graph separation and search number», Proc. 1983 Allerton Conf. on Communication, Control, and Computing . As cited by Monien & Sudborough (1988).
Ellis, J. A.; Sudborough, I. H.; Turner, J. S. (1994), «The vertex separation and search number of a tree», Information and Computation, 113 (1): 50–79, doi:10.1006/inco.1994.1064 .
Feige, Uriel; Hajiaghayi, Mohammadtaghi; Lee, James R. (2005), «Improved approximation algorithms for minimum-weight vertex separators», Proc. 37th ACM Symposium on Theory of Computing (STOC 2005), ISBN 1581139608, pp. 563–572, doi:10.1145/1060590.1060674 .
Fellows, Michael R.; Langston, Michael A. (1989), «On search decision and the efficiency of polynomial-time algorithms», Proc. 21st ACM Symposium on Theory of Computing, ISBN 0897913078, pp. 501–512, doi:10.1145/73007.73055 .
Ferreira, Afonso G.; Song, Siang W. (1992), «Achieving optimality for gate matrix layout and PLA folding: a graph theoretic approach», Proc. 1st Latin American Symposium on Theoretical Informatics (LATIN '92), ISBN 3-540-55284-7, Lecture Notes in Computer Science, 583, Springer-Verlag, pp. 139–153, doi:10.1007/BFb0023825 .
de Fluiter, Babette (1997), Algorithms for Graphs of Small Treewidth (PDF), ISBN 90-393-1528-0, Ph.D. thesis, Utrecht University .
Fomin, Fedor V. (2003), «Pathwidth of planar and line graphs», Graphs and Combinatorics, 19 (1): 91–99, doi:10.1007/s00373-002-0490-z .
Fomin, Fedor V.; Høie, Kjartan (2006), «Pathwidth of cubic graphs and exact algorithms», 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), «Exact algorithms for treewidth and minimum fill-in», SIAM Journal on Computing, 38 (3): 1058–1079, doi:10.1137/050643350 .
Fomin, Fedor V.; Thilikos, Dimitrios M. (2007), «On self duality of pathwidth in polyhedral graph embeddings», Journal of Graph Theory, 55 (1): 42–54, doi:10.1002/jgt.20219 .
Garbe, Renate (1995), «Tree-width and path-width of comparability graphs of interval orders», Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94), ISBN 978-3-540-59071-2, Lecture Notes in Computer Science, 903, Springer-Verlag, pp. 26–37, doi:10.1007/3-540-59071-4_35 .
Golovach, P. A. (1993), «The cutwidth of a graph and the vertex separation number of the line graph», Discrete Mathematics and Applications, 3 (5): 517–522, doi:10.1515/dma.1993.3.5.517 .
Guha, Sudipto (2000), «Nested graph dissection and approximation algorithms», ISBN 0-7695-0850-2, Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS 2000), 0: 126, doi:10.1109/SFCS.2000.892072 .
Gurski, Frank; Wanke, Egon (2007), «Line graphs of bounded clique-width», Discrete Mathematics, 307 (22): 2734–2754, doi:10.1016/j.disc.2007.01.020 .
Gusted, Jens (1993), «On the pathwidth of chordal graphs», Discrete Applied Mathematics, 45 (3): 233–248, doi:10.1016/0166-218X(93)90012-D .
Habib, Michel; Möhring, Rolf H. (1994), «Treewidth of cocomparability graphs and a new order-theoretic parameter», Order, 11 (1): 47–60, doi:10.1007/BF01462229 .
Hliněny, Petr (2003), «Crossing-number critical graphs have bounded path-width», Journal of Combinatorial Theory, Series B, 88 (2): 347–367, doi:10.1016/S0095-8956(03)00037-6 .
Kashiwabara, T.; Fujisawa, T. (1979), «NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph», Proc. International Symposium on Circuits and Systems, pp. 657–660 .
Kinnersley, Nancy G. (1992), «The vertex separation number of a graph equals its path-width», Information Processing Letters, 42 (6): 345–350, doi:10.1016/0020-0190(92)90234-M .
Kinnersley, Nancy G.; Langston, Michael A. (1994), «Obstruction set isolation for the gate matrix layout problem», Discrete Applied Mathematics, 54 (2–3): 169–213, doi:10.1016/0166-218X(94)90021-3 .
Kirousis, Lefteris M.; Papadimitriou, Christos H. (1985), «Interval graphs and searching» (PDF), Discrete Mathematics, 55 (2): 181–184, doi:10.1016/0012-365X(85)90046-9 .
Kloks, Ton; Bodlaender, Hans L. (1992), «Approximating treewidth and pathwidth of some classes of perfect graphs», Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92), ISBN 978-3-540-56279-5, Lecture Notes in Computer Science, 650, Springer-Verlag, pp. 116–125, doi:10.1007/3-540-56279-6_64 .
Kloks, T.; Bodlaender, H.; Müller, H.; Kratsch, D. (1993), «Computing treewidth and minimum fill-in: all you need are the minimal separators», Proc. 1st European Symposium on Algorithms (ESA'93) (Lecture Notes in Computer Science), 726, Springer-Verlag, pp. 260–271, doi:10.1007/3-540-57273-2_61 .
Kloks, Ton; Kratsch, Dieter; Müller, H. (1995), «Dominoes», Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94), ISBN 978-3-540-59071-2, Lecture Notes in Computer Science, 903, Springer-Verlag, pp. 106–120, doi:10.1007/3-540-59071-4_41 .
Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter (2005), «Algorithms based on the treewidth of sparse graphs», Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), ISBN 978-3-540-31000-6, Lecture Notes in Computer Science, 3787, Springer-Verlag, pp. 385–396, doi:10.1007/11604686_34 .
Korach, Ephraim; Solel, Nir (1993), «Tree-width, path-width, and cutwidth», Discrete Applied Mathematics, 43 (1): 97–101, doi:10.1016/0166-218X(93)90171-J .
Kornai, András; Tuza, Zsolt (1992), «Narrowness, path-width, and their application in natural language processing», Discrete Applied Mathematics, 36 (1): 87–92, doi:10.1016/0166-218X(92)90208-R .
Lengauer, Thomas (1981), «Black-white pebbles and graph separation», Acta Informatica, 16 (4): 465–475, doi:10.1007/BF00264496 .
Lopez, Alexander D.; Law, Hung-Fai S. (1980), «A dense gate matrix layout method for MOS VLSI», IEEE Transactions on Electron Devices, ED-27 (8): 1671–1675, doi:10.1109/T-ED.1980.20086, Also in the joint issue, IEEE Journal of Solid-State Circuits 15 (4): 736–740, 1980, doi:10.1109/JSSC.1980.1051462 .
Miller, George A. (1956), «The Magical Number Seven, Plus or Minus Two», Psychological Review, 63 (2): 81–97, PMID 13310704, doi:10.1037/h0043158 .
Möhring, Rolf H. (1990), «Graph problems related to gate matrix layout and PLA folding», in: Tinhofer, G.; Mayr, E.; Noltemeier, H.; Sysło, M., Computational Graph Theory, ISBN 3-211-82177-5, Computing Supplementum, 7, Springer-Verlag, pp. 17–51 .
Monien, B.; Sudborough, I. H. (1988), «Min cut is NP-complete for edge weighted trees», 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), «One-dimensional logic gate assignment and interval graphs», IEEE Transactions on Circuits and Systems, 26 (9): 675–684, doi:10.1109/TCS.1979.1084695 .
Peng, Sheng-Lung; Ho, Chin-Wen; Hsu, Tsan-sheng; Ko, Ming-Tat; Tang, Chuan Yi (1998), «A linear-time algorithm for constructing an optimal node-search strategy of a tree», Proc. 4th Int. Conf. Computing and Combinatorics (COCOON'98), Lecture Notes in Computer Science, 1449, Springer-Verlag, pp. 197–205 .
Proskurowski, Andrzej; Telle, Jan Arne (1999), «Classes of graphs with restricted interval models» (PDF), Discrete Mathematics and Theoretical Computer Science, 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), «Graph minors. XVI. Excluding a non-planar graph», Journal of Combinatorial Theory, Series 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), «A linear algorithm for the pathwidth of trees», in: Bodendiek, R.; Henn, R., Topics in Combinatorics and Graph Theory, Physica-Verlag, pp. 613–620 .
Scheffler, Petra (1992), «Optimal embedding of a tree into an interval graph in linear time», in: Nešetřil, Jaroslav; Fiedler, Miroslav, Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, Elsevier .
Skodinis, Konstantin (2000), «Computing optimal linear layouts of trees in linear time», Proc. 8th European Symposium on Algorithms (ESA 2000), ISBN 978-3-540-41004-1, Lecture Notes in Computer Science, 1879, Springer-Verlag, pp. 403–414, doi:10.1007/3-540-45253-2_37 .
Skodinis, Konstantin (2003), «Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time», 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, 4769, Springer-Verlag, pp. 258–269, doi:10.1007/978-3-540-74839-7_25 .
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 .
Takahashi, Atsushi; Ueno, Shuichi; Kajitani, Yoji (1994), «Minimal acyclic forbidden minors for the family of graphs with bounded path-width», Discrete Mathematics, 127 (1–3): 293–304, doi:10.1016/0012-365X(94)90092-2 .

[1] Diestel & Kühn (2005).

[rs83-2] Robertson & Seymour (1983).

[3] Bodlaender (1998).

[rs83-4] Erro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome rs83

[Robertson_2003-5] Robertson & Seymour (2003).

[npc-6] Erro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome npc

[bghk92-7] Bodlaender et al. (1992).

[bounded-tw-algs-8] Erro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome bounded-tw-algs

[9] Bodlaender (1994).

[tree-algs-10] Erro de citação: Etiqueta <ref> inválida; não foi fornecido texto para as refs de nome tree-algs

[Arnborg_1985-11] Arnborg (1985).

[apt00-12] Aspvall, Proskurowski & Telle (2000).

[13] Bodlaender (1998), Theorem 29, p. 13.

[14] Kinnersley (1992); Bodlaender (1998), Theorem 51.

[1]

[2]

[3]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]