Susanna Figueiredo de Rezende
Supervisora: Profa. Dra. Yoshiko Wakabayashi
19 de setembro de 2011
A versão preliminar da monografia pode ser encontrada no seguinte link: www.linux.ime.usp.br/~susanna/mac499/preliminar/monografia.pdf.
A proposta desse trabalho é estudar duas classes de problemas relativos a caminhos mais longos em grafos: uma de natureza algorítmica e outra de natureza estrutural. Os problemas de enfoque algrítmico se referem a busca de caminhos mais longos, enquantos os de enfoque estrutural se referem a intersecção de caminhos mais longos.
Em 2010, como atividade de IC, estudei um artigo de M. Axenovich [1], sobre intersecção de três caminhos mais longos em um grafo exoplanar, o que motivou o estudo da história e dos resultados conhecidos sobre problemas relacionados a intersecção de caminhos mais longos. Baseado nesse estudo, elaborei uma monografia para o V Simpósio Nacional / Jornadas de Iniciação Científica organizado pelo IMPA em 2010.
Durante esse último semestre, aprofundei no estudo dos resultados conhecidos sobre intersecção de caminhos mais longos. Estudei três artigos relacionados com o tema:
Também comecei a estudar os resultados conhecidos sobre o problema de encontrar um caminho comprimento máximo em um grafo. Atualmente estou estudando os seguintes artigos:
Com base no trabalho feito ano passado, comecei a elaborar um nova monografia, abrangendo também o problema de busca de caminho mais longo. Pretendo ainda reproduzir as provas lidas nos artigos mencionados acimas, e se possível incluir outros resultados.
[1] Axenovich, M., When do three longest paths have a common vertex?, Discrete Mathematics, Algorithms and Applications 1 (2009), pp. 115-120
[2] Balister, P., E. Győri, J. Lehel and R. Schelp, Longest paths in circular arc
graphs, Combin. Probab. Comput. 13 (2004), pp. 311-317.
[3] Bondy, J.A. and U.S.R. Murty, Graph theory, volume 244 of Graduate Texts in Mathematics. Springer, New York, 2008.
[4] Bulterman, R.W., F.W. van der Sommen, G. Zwaan, T. Verhoe, A.J.M. van Gasteren,
and W.H.J. Feijen, On computing a longest path in a tree. Inform. Process. Lett.,
81(2):93-96, 2002.
[5] Gallai, T., Problem 4, in: Theory of Graphs (1968), p. 362.
[6] Garey, M.R. and D.S. Johnson, Computers and intractability. W. H. Freeman and Co.,
San Francisco, Calif., 1979. A guide to the theory of NP-completeness, A Series of
Books in the Mathematical Sciences.
[7] Grünbaum, B, Vertices missed by longest paths or circuits. J. Combinatorial Theory
Ser. A, 17:31-38, 1974.
[8] Hatzel, W., Ein planarer hypohamiltonscher Graph mit 57 Knoten. Math. Ann.,
243(3):213-216, 1979.
[9] Ioannidou, K., G. Mertzios, and S. Nikolopoulos, The longest path problem is polynomial on interval graphs.
In Rastislav Královic and Damian Niwinski, editors, Mathematical Foundations of Computer Science 2009,
volume 5734 of Lecture Notes in Computer Science, pages 403-414. Springer Berlin / Heidelberg, 2009.
[10] Ioannidou, K. and S. Nikolopoulos, The longest path problem is polynomial on cocomparability graphs. In
Dimitrios Thilikos, editor, Graph Theoretic Concepts in Computer Science, volume 6410 of Lecture Notes in
Computer Science, pages 27-38. Springer Berlin / Heidelberg, 2010.
[11] Klavžar, S. and M. Petkovšek, Graphs with non empty intersection of longest
paths, Ars Combin. 29 (1990), pp. 13-52.
[12] Pelikán J., L. Lovász and K. Vesztergombi, Discrete Mathematics: elementary and beyond. Undergraduate
Texts in Mathematics. Springer-Verlag, New York, 2003.
[13] Research problems, Discrete Mathematics 167/168 (1997), pp. 605-615, 15th
British Combinatorial Conference.
[14] Schmitz, W., Über längste Wege und Kreise in Graphen. Rend. Sem. Mat. Univ. Padova,
53:97-103, 1975.
[15] Skupień, Z., Smallest sets of longest paths with empty intersection, Combin.
Probab. Comput. 5 (1996), pp. 429-436.
[16] Takamizawa, K., T. Nishizeki, and N. Saito, Linear-time computability of combinatorial problems on seriesparallel
graphs. J. ACM, 29:623-641, July 1982.
[17] Uehara, R. and Y. Uno, Efficient algorithms for the longest path problem. In Rudolf Fleischer and Gerhard
Trippen, editors, Algorithms and Computation, volume 3341 of Lecture Notes in Computer Science, pages
1547-1553. Springer Berlin / Heidelberg, 2005.
[18] Uehara, R. and Y. Uno, On computing longest paths in small graph classes. Internat.
J. Found. Comput. Sci., 18(5):911-930, 2007.
[19] Walther, H., Über die Nichtexistenz eines Knotenpunktes, durch den alle
längsten Wege eines Graphen gehen, J. Combinatorial Theory 6 (1969), pp. 1-6.
[20] Walther, H. and H.-J. Voss, Über Kreise in Graphen, VEB Deutscher Verlag
der Wissenschaften (1974).
[21] Zamfirescu, T., A two-connected planar graph without concurrent longest paths. J.
Combinatorial Theory, 13:116-121, 1972.
[22] Zamfirescu, T., On longest paths and circuits in graphs, Math. Scand. 38 (1976),
pp. 211-239.
[23] Zamfirescu, T., Intersecting longest paths or cycles: a short survey, An. Univ.
Craiova Ser. Mat. Inform. 28 (2001), pp. 1-9.