Publicações

PROJETO: Fundamentos da Ciência da Computação: algoritmos combinatórios e estruturas discretas -- Projeto Temático ProNEx - FAPESP/CNPq Proc. No. 2003/09925-5


Publicações dos membros do projeto de Julho/2005 a Junho/2006


Capítulos de Livro

  1. G. Calinescu and C.G. Fernandes, Maximum Planar Subgraph, Chapter R43 in Approximation Algorithms and Metaheuristics, Teofilo F. Gonzalez (Ed.), Francis and Taylor, to appear.

Publicações em periódicos

  1. S.S. Adi and C.E. Ferreira, Gene prediction by multiple syntenic alignment, Journal of Integrative Bioinformatics, v. 13, 2005.
  2. N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira, and V. Rödl, Measures of pseudorandomness for finite sequences: minimal values, Combinatorics, Probability, and Computing, v. 15, n. 1-2, p. 1-29, 2006.
  3. Egon Balas, and C. C. de Souza, The vertex separator problem: a polyhedral investigation. Mathematical Programming - Series A, Volume 103, Issue 3, Jul 2005, Pages 583 - 608
  4. E. C. Bracht, L. A. A. Meira and F.K. Miyazawa. A greedy approximation algorithm for the uniform labeling problem. ACM Journal on Experimental Algorithm. To appear.
  5. M.H. Carvalho and J. Cheryian. An O(VE) algorithm for ear decomposition of matching covered graphs. ACM Transactions on Algorithms, v. 1, n. 2, p. 324-337, 2005
  6. G. Cintra, F.K. Miyazawa, Y. Wakabayashi, and E.C. Xavier, A note on the approximability of cutting stock problems, European Journal of Operational Research, To appear.
  7. P. Coll, C.C. Ribeiro, and C.C. de Souza, Multiprocessor schedule under precedence constraints: polyhedral results, Discrete Applied Mathematics, Volume 154, 770-801, 2006.
  8. S. Curran, O. Lee and X. Yu, Chain decompositions of 4-connected graphs, SIAM J. Discr. Math. 19 (2005), 848--880 (electronic).
  9. S. Curran, O. Lee and X. Yu, Non-separating planar chains in 4-connected graphs, SIAM J. Discr. Math. 19 (2005), 399-419 (electronic).
  10. R. Dahab, D. Hankerson, F. Hu, M. Long, J. López, A. Menezes, Software Multiplication using Gaussian Normal Bases, IEEE Transactions on Computers, to appear.
  11. C.C. de Souza, and Egon Balas, The vertex separator problem: algorithms and computations Mathematical Programming - Series A, Volume 103, Issue 3, Jul 2005, Pages 609 - 631
  12. N. Eaton, Z. Füredi, A. Kostochka, and J. Skokan, Tree representations of graphs, European Journal of Combinatorics, to appear, 17pp.
  13. C.E. Ferreira, F.M. de Oliveira Filho, New reduction techniques for the group Steiner tree problem, SIAM Journal on Optimization, to appear.
  14. C.E. Ferreira and F.M. de Oliveira Filho, Some formulations for the group Steiner tree problem, Discrete Applied Mathematics, to appear, 2006.
  15. A. Fujita, K.B. Massirer, A.M. Durham, C.E. Ferreira, and M.C. Sogayar, GATO gene annotation tool for research laboratories, Brazilian Journal of Medical and Biological Research, Ribeirão Preto, SP, v. 38, n. 11, 2005.
  16. Shinya Fujita, Ken-ichi Kawarabayashi, Claudio Leonardo Lucchesi, Katsuhiro Ota, Michael D. Plummer and Akira Saito. A pair of forbidden subgraphs and perfect matchings, Journal of Combinatorial Theory (B), 96 (2006), 315-324.
  17. S. Gerke, Y. Kohayakawa, V. Rödl, and A. Steger, Small subsets inherit sparse \epsilon-regularity, Journal of Combinatorial Theory Series B, to appear, 2006.
  18. André L. P. Guedes and Lilian Markenzon. Directed Hypergraph Planarity. Pesquisa Operacional, 25(3):383-390, setembro/dezembro 2005.
  19. P.E. Haxell, T. Luczak, Y. Peng, V. Rödl, A. Rucinski, M. Simonovits, and J. Skokan, The Ramsey number for hypergraph cycles I., J. Combin. Theory Ser. A 113(1), 2006, pp. 67-83.
  20. Juliato, M. ; Araujo, G. C. S. ; Lopez, J. ; Dahab, R. A Custom Instruction Approach for Hardware and Software Implementations of Finite Field Arithmetic over F_(2^163) using Gaussian Normal Bases, Journal of VLSI Processing Systems, accepted for publication.
  21. K. Kawarabayashi, O. Lee and X. Yu, Non-separating paths with prescribed ends in 4-connected graphs, Annals of Combinatorics 9 (2005), 47-56.
  22. S. Kingan and M. Lemos, On weak excluded minors for a class of graphs, Annals of Combinatorics 9 (2005), 199-204.
  23. S. Kingan and M. Lemos, On the circuit-cocircuit intersection conjecture, Graphs and Combinatorics, to appear.
  24. M. Lemos, Weight distribuition of the bases of a matroid, Graphs and Combinatorics 22 (2006), 69-82.
  25. M. Lemos, Matroids with few non-common bases, Discrete Mathematics 306 (2006), 680-687.
  26. M. Lemos and J. Oxley, Matroid packing and covering with circuits through an element, Journal of Combinatorial Theory Series B 96 (2006), 135-158.
  27. M. Lemos, On the number of triangles in 3-connected matroids, European Journal of Combinatorics, to appear.
  28. M. Lemos, Elements belonging to triangles in 3-connected matroids, Discrete Mathematics, to appear.
  29. M. Lemos and T. R. B. Melo, Non-separating cocircuits in matroids, Discrete Applied Mathematics, to appear.
  30. E. Macambira, N. Maculan, and C.C. de Souza, A column generation approach for SONET ring assignment Networks, Volume 47, Issue 3, 157-171. May 2006.
  31. E. Macambira, N. Maculan, C. C. de Souza, A note on characterizing canonical cuts using geometry International Transactions in Operational Research, (12), 581--593, 2005.
  32. F.K. Miyazawa and Y. Wakabayashi, Two- and three-dimensional parametric packing. Computers and Operations Research, to appear.
  33. N. Moreano, E. Borin, C. C. de Souza and G. Araujo, Efficient Datapath Merging for Reconfigurable Architectures IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Volume 24, Issue 7, July 2005, pages 969 - 980.
  34. > V. Rödl and J.Skokan, Applications of the regularity lemma for uniform hypergraphs, Random Structures and Algorithms, 28(2), 2006, pp. 180-194.
  35. M. M. Rodrigues, A. V. Moura, and C. C. de Souza, Vehicle and Crew Scheduling for Urban Bus Lines European Journal of Operational Research, Volume 170, Issue 3, 844-862, May 2006.
  36. E.C. Xavier and F.K. Miyazawa. Approximation Schemes for Knapsack Problems with Shelf Divisions. Theoretical Computer Science (Elsevier Science), (352): 71--84, 2006.
  37. T. H. Yunes, A. V. Moura, and C. C. de Souza, Hybrid Column Generation Approaches for Urban Transit Crew Management Problems. Transportation Science, vol. 39, No. 2, 273--288, May 2005.

Publicações em Anais de Congressos Internacionais


  1. E. Araújo and J. Soares, Scoring matrices that induce metrics on sequences, Proceedings of the Latin American Theoretical Informatics Symposium (Valdivia, Chile, LATIN 2006). Lecture Notes in Computer Science, v. 3887. p. 68-79.
  2. J.R. Correa, C.G. Fernandes, and Y. Wakabayashi, Approximating Rational Objectives is as Easy as Approximating Linear Ones. In SWAT - 10th Scandinavian Workshop on Algorithm Theory, Riga, 2006. Lecture Notes in Computer Science, v. 4059. p. 351-362.
  3. Pedro Ribeiro de Andrade Neto and André L. P. Guedes. A Linear Algorithm for Exact Pattern Matching in Planar Subdivisions. In Proceedings of SIBGRAPI 2005, XVIII Simpósio Brasileiro de Computação Gráfica e Processamento de Imagens, pages 120-127, Natal, RN, 2005.
  4. D. Dellamonica Jr. and Y. Kohayakawa, An algorithmic Friedman-Pippenger theorem on tree embeddings and applications to routing (extended abstract), Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006. p. 1038-1044.
  5. C.G. Fernandes, V. Lacroix, and M.-F. Sagot, Reaction motifs in metabolic networks, Proceedings of the Workshop on Algorithms in Bioinformatics (Mallorca, Spain, WABI 2005). Lecture Notes in Computer Science, v. 3692, p. 178-191.
  6. M. Juliato, G.C.S. Araujo, J. Lopez, J and R. Dahab, A Custom Instruction Approach for Hardware and Software Implementations of Finite Field Arithmetic over F_(2^163) using Gaussian Normal Bases, Proceedings. 2005 IEEE International Conference on Field-Programmable Technology, 2005, Cingapura.
  7. O. Lee and A. Williams. Packing dicycle covers in planar graphs with no $K_5-e$ minor. Proceedings of the 7th Latin American Theoretical Informatics Symposium (LATIN'06), Valdivia, Chile. Lecture Notes in Comp. Science 3887 (2006), 677-688.
  8. G. Manic and Y. Wakabayashi, Packing triangles in low-degree graphs and indifference graphs, European Conference on Combinatorics, Graph Theory, and Applications (EUROCOMB 2005), Berlin, Germany, September 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science (DMTCS), vol. AE (2005), pp. 251-256.
  9. M. Marciniszyn, J. Skokan, R. Spöhel, and A. Steger, Threshold Functions for Asymmetric Ramsey Properties Involving Cliques, Proceedings of the 10th International Workshop on Randomization and Computation, RANDOM 2006, to appear, 12pp.
  10. J. López and R. Dahab, New Point Compression Algorithms for Binary Curves. Proceedings of the IEEE Information Theory Workshop (ITW), 2006, Punta Del Este.
  11. F.V. Martinez, J.C. de Pina, and J. Soares, Algorithms for Terminal Steiner Trees, Computing and Combinatorics Conference (COCOON 2005), Kunming, Yunnan, China, 2005. LNCS 3595, 369-379.
  12. L.B. Oliveira, H.C. Wong, M. Bern, R. Dahab and A.A.F. Loureiro. SecLEACH -- A Random Key Distribution Solution for Securing Clustered Sensor Networks. Accepted for the 5th IEEE International Symposium on Network Computing and Applications (IEEE NCA06), 2006.
  13. E.C. Xavier and F.K. Miyazawa. The class constrained bin packing problem with applications to video-on-demand. 12th Annual International Computing and Combinatorics Conference (COCOON'06). To appear. Lecture Notes on Computer Science (LNCS), Springer-Verlag, 2006.

Trabalhos Submetidos

  1. S.S. Adi and C.E. Ferreira, A graph theoretical model for the Gene Prediction Problem, 2004.
  2. D. M. Batista, N. L. S. da Fonseca, F. K. Miyazawa and F. Granelli. Traffic Engineering for Grid Networks.
  3. Renato Carmo, Yoshiharu Kohayakawa and Eduardo Laber. Dois Problemas de Busca. XIX Concurso de Teses e Dissertações da Sociedade Brasileira de Computação. Aceito para publicação nos anais do XXVI Congresso da Sociedade Brasileira de Computação, Campo Grande, julho de 2006
  4. R. Carmo, T. Feder, Y. Kohayakawa, E. Laber, R. Motwani, Liadan O'Callaghan, Rina Panigrahy, and Dilys Thomas, Querying priced information in databases: the conjunctive case, 2004.
  5. V. Cavalcante, A. Lucena, and C.C. de Souza, A relax-and-cut algorithm to the set partitioning problem.
  6. G. F. Cintra, F. K. Miyazawa, Y. Wakabayashi and E. C. Xavier. Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation.
  7. F. Chataigner, L.R.B. Salgado and Y. Wakabayashi, Approximability and inapproximability of problems on balanced connected partitions of graphs, 2006.
  8. R. Cordovil, B. M. Junior and M. Lemos, The 3-connected binary matroids with circumference 6 or 7, 2006.
  9. P. Feofiloff, C.G. Fernandes, C.E. Ferreira, and J.C. de Pina, Approximation algorithms for the Prize-Collecting Steiner Tree Problem, 2005.
  10. C.G Fernandes, O. Lee and Y. Wakabayashi, The Minimum Cycle Cover and the Chinese Postman Problems on Mixed Graphs with Bounded Tree Width.
  11. A. Fujita, J.R. Sato, M.C. Sogayar, C.E. Ferreira, Non parametric regression and canonical correlation analysis in tumor classification, 2004.
  12. B. M. Junior, M. Lemos and T. R. B. Melo, Non-separating circuits and cocircuits in matroids, 2005.
  13. S.J. Kim, K. Nakprasit, M. Pelsmajer, and J. Skokan, Transversal numbers of translates of a convex body, 2006.
  14. Y. Kohayakawa, V. Rödl, M. Schacht, P. Sissokho, and J. Skokan, Turán's Theorem for pseudorandom graphs, 2006.
  15. G. Manic and Y. Wakabayashi, Packing triangles in low-degree graphs and indifference graphs, 2005.
  16. L. A. A. Meira and F. K. Miyazawa. Semidefinite Programming Based Algorithms for the Ratio Cut Problem.
  17. A. V. Moura, R. A. Pereira, C. C. de Souza, GRASP strategies for scheduling activities at oil wells with resource displacement.
  18. E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, The Maximum Agreement Forest Problem: approximation algorithms and computational experiments, 2005.
  19. F.H. Viduani Martinez, J.C. de Pina, and J. Soares, Algorithms for Terminal Steiner Trees, Theoretical Computer Science, 2006.
  20. E. C. Xavier and F. K. Miyazawa. A Note on Dual Approximation Algorithms for Class Constrained Bin Packing Problems.

Outras publicações

  1. Celso Hartmann, Alexandre Direne, Luis Bona, Fabiano Silva, Gabriel dos Santos, André Guedes, Marcos Castilho, and Marcos Sunyé. Linguagem e Ferramenta de Autoria para Promover o Desenvolvimento de Perícias em Xadrez. In Neide Santos and Fernanda Campos, editors, XVI SBIE - Simpósio Brasileiro de Informática na Educação (SBIE-2005), pages 656-665, Juiz de Fora, Brasil, Novembro 2005. SBC-UFJF.
  2. J. Donadelli, Tópicos em Teoria dos Grafos - Uma Introdução à Teoria Espectral de Grafos Notas de aula da disciplina disponível em http://www.inf.ufpr.br/jair/MANUSCRIPTS/ttg.pdf. Curitiba, 2005.
  3. J. Donadelli, Algoritmos e Teoria dos Grafos Notas de aula da disciplina disponível em http://www.inf.ufpr.br/jair/MANUSCRIPTS/ci065.pdf. Curitiba, 2005.