Publicações

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 (desde janeiro 2004)

Livros e Notas de Aulas

  1. N. F. Almeida Jr., G. P. Telles, and F. V. Martinez, Algoritmos e heurísticas para comparações exata e aproximada de seqüências, Jornada de Atualização em Informática, Congresso da Sociedade Brasileira de Computação, São Leopoldo, RS, Brasil, 2005.
  2. P. Feofiloff, Y. Kohayakawa and Y. Wakabayashi, Uma introdução sucinta à teoria dos grafos, Notas de aula - minicurso na II Bienal de Matemática - SBM - Salvador 2004.

Publicações em periódicos

  1. 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, to appear.
  2. E. Balas and C.C. de Souza, The Vertex Separation Problem: A Polyhedral Investigation, Mathematical Programming, to appear.
  3. R. Carmo, J. Donadelli, Y. Kohayakawa and E. Laber, Searching in random partially ordered sets, Theoretical Computer Science, 321 (2004), no. 1, 41-57.
  4. M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, The perfect matching polytope and solid bricks, Journal of Combinatorial Theory (B), 92 (2004), 319-324.
  5. M.H. Carvalho, C.L. Lucchesi and U.S.R. Murty, How to Build a Brick, Discrete Mathematics, to appear.
  6. M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, Graphs with independent perfect matchings, Journal of Graph Theory, 48 (2005), 19-50.
  7. M. H. Carvalho, C. L. Lucchesi and U. S. R. Murty, On the Number of Dissimilar Pfaffian Orientations of Graphs, Theoretical Informatics and Applications 39 (2005), 93-113.
  8. P. Coll, C.C. Ribeiro, and C.C. de Souza, Multiprocessor Schedule under Precedence Constraints: Polyhedral Results, Discrete and Applied Mathematics (2004), to appear.
  9. S. Curran, O. Lee, and X. Yu, Non-separating planar chains in 4-connected graphs. To appear in SIAM J. Discr. Math.
  10. S. Curran, O. Lee and X. Yu, Chain decompositions of 4-connected graphs. To appear in SIAM J. Discr. Math.
  11. C. N. da Silva and R. Dahab, Tutte's 3-flow Conjecture and Matchings in Bipartite Graphs, ARS Combinatoria 76 (2005), to appear.
  12. R. Dahab, D. Hankerson, F. Hu, M. Long, J. López, and A. Menezes, Software Multiplication using Gaussian Normal Bases, IEEE Transactions on Computers. To appear.
  13. C.G.T. de A. Moreira and Y. Kohayakawa, Bounds for optimal coverings, Discrete Applied Mathematics, 141 (2004), no. 1­3, 263-276.
  14. A.P. do Lago, I. Muchnik, and C. Kulikowski, A sparse dynamic programming algorithm for alignment with non-overlapping inversions, Theoretical Informatics and Applications 39 (2005), 175-190.
  15. J. Donadelli, P.E. Haxell, and Y. Kohayakawa, A note on the size-Ramsey number of long subdivisions of graphs, Theoretical Informatics and Applications, 39 (2005), no. 1, 191-206.
  16. N. Eaton, Z. Füredi, A. Kostochka, and J. Skokan, Tree representations of graphs, European Journal of Combinatorics, to appear.
  17. C.G. Fernandes, E. Green, and A. Mandel, From monomials to words to graphs, Journal of Combinatorial Theory A, 105 (2004) 185-206.
  18. M. Ferrara, Y. Kohayakawa, and V.Rödl, Distance graphs on the integers, Combinatorics, Probability, and Computing 14 (2005), no. 1-2, 107-131.
  19. C.E. Ferreira and F.M. de Oliveira Filho, Some formulations for the group Steiner tree problem, Discrete Applied Mathematics, to appear (2005).
  20. 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, to appear (2005).
  21. 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, to appear.
  22. K. Kawarabayashi, O. Lee, and X. Yu, Non-separating paths with prescribed ends in 4-connected graphs, Annals of Combinatorics 9 (2005), 47-56.
  23. S. Kingan and M. Lemos, On weak excluded minors for a class of graphs, Annals of Combinatorics, to appear.
  24. Y. Kohayakawa, F.K. Miyazawa, P. Raghavan and Y. Wakabayashi. Multidimensional Cube Packing. Algorithmica, 40 (3) (2004), 173-187.
  25. Y. Kohayakawa, V. Rödl, and M. Schacht, The Turán theorem for random graphs, Combinatorics, Probability, and Computing, 13:61-91 (2004).
  26. Y. Kohayakawa, V. Rödl, and P. Sissokho, Embedding graphs with bounded degree in sparse pseudorandom graphs, Israel Journal of Mathematics, 139 (2004), 93-137.
  27. M. Lemos, Non-separating cocircuits in binary matroids, Linear Algebra and its Applications, 382 (2004), 171-178.
  28. M. Lemos, Elements belonging to triads in 3-connected matroids. Discrete Mathematics, North Holland, 285 (2004), 167-181.
  29. M. Lemos, On the number of non-isomorphic matroids. Advances in Applied Mathematics, Academic Press, 33 (2004), 733-746.
  30. M. Lemos, Weight distribution of the bases of a matroid, Graphs and Combinatorics, to appear.
  31. M. Lemos and J. Oxley, Matroid packing and covering with circuits through an element, Journal of Combinatorial Theory Series B, to appear.
  32. M. Lemos and J.G. Oxley, On the minor-minimal 2-connected graphs having a fixed minor, Discrete Mathematics, 280 (2004), 77-118.
  33. L. Lins, S. Lins, and S.B. Melo, Phorma; perfectly hashable order restricted multidimensional arrays. Discrete Applied Mathematics, 141 (2004), 209-223.
  34. F.K. Miyazawa and Y. Wakabayashi, Two- and three-dimensional parametric packing. Computers and Operations Research, to appear.
  35. N. Moreano, E. Borin, G. Araújo and C.C. de Souza, Efficient Datapath Merging for Reconfigurable Architectures, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (2004), to appear.
  36. Y. Peng, V. Rödl, and J. Skokan, Counting small cliques in 3-uniform hypergraphs, Combinatorics, Probability, Computing, 14 (3), 2005, 371-413
  37. V. Rödl and J. Skokan, Regularity lemma for uniform hypergraphs, Random Structures and Algorithms, 25 (1), 2004, 1-42.
  38. V. Rödl and J. Skokan, Counting subgraphs in quasi-random 4-uniform hypergraphs, Random Structures and Algorithms, 26(1-2), 2005, 160-203.
  39. V. Rödl, B. Nagle, J. Skokan, M. Schacht, and Y. Kohayakawa, The hypergraph regularity method and its applications, Proceedings of the National Academy of Sciences (USA), 102 (23), 2005, 8109-8113.
  40. V. Rödl, and J. Skokan, Applications of the regularity lemma for uniform hypergraphs, Random Structures and Algorithms, to appear.
  41. M.M. Rodrigues, C.C. de Souza, and A.V. Moura, Vehicle and Crew Scheduling for Urban Bus Lines, European Journal of Operational Research, to appear.
  42. C.C. de Souza and E. Balas, The Vertex Separator Problem: Algorithms and Computations, Mathematical Programming (2004), to appear.
  43. T.H. Yunes, A.V. Moura, and C.C. de Souza, Hybrid column generation approaches for solving real world crew management problems. Transportation Science, vol. 39, No. 2, 273-288, May 2005.

Publicações em Anais de Congressos Internacionais

  1. C.E.R. Alves, A.P. do Lago, and A.F. Vellozo, Alignment with non-overlapping inversions in O(n3logn)-time, Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Electronic Notes in Discrete Mathematics 19:365-371, 2005.
  2. J. Boyer, C.G. Fernandes, A. Noma, and J.C. Pina, Lempel, Even, and Cederbaum Planarith Method, Proceedings of the Third International Workshop Experimental and Efficient Algorithms (WEA 2004), Angra dos Reis, RJ, Brazil, May, 2004. Lecture Notes in Computer Science, vol. 3059, Springer, 2004, 129-144.
  3. F.C. Botelho, Y. Kohayakawa, and N. Ziviani, A practical minimal perfect hashing method, Proceedings of the fourth International Workshop on Experimental and Efficient Algorithms (WEA 2005), Santorini Island, Greece (S.E. Nikoletseas, ed.), Lecture Notes in Computer Science, vol. 3503, Springer, 2005, 488-500.
  4. E.C. Bracht, L.A.A. Meira and F.K. Miyazawa. A Greedy Approximation Algorithm for the Uniform Labeling Problem Analysed by a Primal Dual Technique. WEA'2004: Workshop on Efficient and Experimental Algorithms. Lecture Notes in Computer Science 3059, 145-158, Springer-Verlag, Rio de Janeiro, 2004.
  5. R. Carmo, Y. Kohayakawa, and E. Laber, Querying priced information in databases: the conjunctive case (extended abstract), LATIN 2004: Theoretical Informatics (Buenos Aires, 2004) (Martin Farach­Colton, ed.), Lecture Notes in Computer Science, vol. 2976, Springer, Berlin, 2004, pp. 6-15.
  6. M.H. Carvalho and J. Cheryian. An O(VE) algorithm for ear decomposition of matching covered graphs. Proceedings of the sixteenth annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, Canada, 415-423, 2005.
  7. M. Castilho, A. Guedes, T. Lima, J. Marynowski, M. Razer, L. Künzle and F. Silva, A Petri net based representation for planning problems. In Booklet of International Planning Competition - IPC'04, pages 27-29, Whistler, British Columbia, Canada, June 2004. ICAPS'04.
  8. G.F. Cintra and Y. Wakabayashi, Dynamic Programming and Column Generation based Approaches for Two-dimensional Guillotine Cutting Problems, Proceedings of WEA 2004: Workshop on Efficient and Experimental Algorithms, Angra dos Reis, RJ, Brazil - May 25 to 28, 2004. Lecture Notes in Computer Science, vol. 3059 (2004), pp. 175-190.
  9. C.G. Fernandes, V. Lacroix, and M.-F. Sagot, Reaction motifs in metabolic networks, Proceedings of the Workshop on Algorithms in Bioinformatics (Eivissa, Spain, WABI 2005). To appear in LNCS.
  10. C.E. Ferreira, F.M. de Oliveira Filho, Some formulations for the group Steiner tree problem, Proceedings of the Latin American Conference on Combinatorics, Graphs and Algorithms (LACGA), Santiago, Chile. Eletronic Notes in Discrete Mathematics 18, pp. 127-132, 2004.
  11. L. de C. Ferreira and R. Dahab, Optimistic Blinded-Key Signatures for ElGamal and Related Schemes, IEEE MATA 2004 - 1st International Workshop on Mobility Aware Technologies and Applications. Florianópolis, SC, BRASIL, 2004. In LNCS, Vol. 3284, pp.254-263.
  12. L. de C. Ferreira and R. Dahab, Optimistic Blinded-key Signatures, The 2004 IEEE First Symposium on Multi-Agent Security and Survivability (MAS&S 2004), Philadelphia, 2004. In Proceedings of the 2004 IEEE First Symposium on Multi-Agent Security and Survivability, pp. 65-72.
  13. Y. Kohayakawa, M. Simonovits, and J. Skokan, The 3­colored Ramsey number of odd cycles, Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Electronic Notes in Discrete Mathematics 19:397-402, 2005.
  14. M. Lemos and T. R. B. Melo, Non-separating cocircuits in matroids, Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005), Electronic Notes in Discrete Mathematics 19:149-153, 2005.
  15. S. Livramento, A.V. Moura, F.K. Miyazawa, M.M. Harada and R.A. Miranda, A Genetic Algorithm for Telecommunication Network Design. EvoComNet 2004: European Workshop on Evolutionary Computation in Communications, Networks, and Connected Systems. Lecture Notes in Computer Science, LNCS 3005, pp. 140-149, Springer-Verlag. Coimbra, Portugal, 2004.
  16. 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), to appear.
  17. 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.
  18. F.K. Miyazawa and Y. Wakabayashi. Packing Problems with Orthogonal Rotations. LATIN'2004: Theoretical Informatics. Lecture Notes in Computer Science (LNCS) 2976, 359-368, Springer-Verlag. Buenos Aires, Argentina, 2004.
  19. F.K. Miyazawa and Y. Wakabayashi. Two- and Three-dimensional Parametric Packing Problems. Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005). Electronic Notes in Discrete Mathematics, 19:313-319, 2005.
  20. R.A. Pereira, A.V. Moura and C.C. de Souza, Comparative Experiments with GRASP and Constraint Programming for the Oil Well Drilling Problem, Proceedings of the Fourth International Workshop Experimental and Efficient Algorithms (WEA 2005), Santorini, Greece, May 2005. Lecture Notes in Computer Science, vol. 3503, 328-340.
  21. L.R.B. Salgado and Y. Wakabayashi, Approximation Results on Balanced Connected Partitions of Graphs, Proceedings of the Latin-American Conference on Combinatorics, Graphs and Applications (LACGA), Santiago, Chile. Electronic Notes in Discrete Mathematics 18, 207-212, 2004.
  22. M.V.G. Silva and A.L.P. Guedes, Perfect subgraph/supergraph. Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005). Electronic Notes in Discrete Mathematics 19:355-360, 2005.
  23. C.C. de Souza, A.M.M. Lima, N.B. Moreano and G. Araújo, The Datapath Merging Problem in Reconfigurable Systems: Lower Bounds and Heuristic Evaluation, Proceedings of the Third International Workshop Experimental and Efficient Algorithms (WEA 2004), Angra dos Reis, RJ, Brazil, May, 2004. Lecture Notes in Computer Science, vol. 3059, 545-558.
  24. E.C. Xavier and F.K. Miyazawa, A One-dimensional Bin Packing Problem with Shelf Divisions. Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics (GRACO 2005). Electronic Notes in Discrete Mathematics 19:329-335, 2005.

Trabalhos Editoriais

  1. C. Choffrut, and Y. Wakabayashi (editors) Preface [Imre Simon, the tropical computer scientist]. Theor. Inform. Appl. 39 (2005), no. 1, i-vii.
  2. P. Feofiloff, C.M.H.de Figueiredo and Y. Wakabayashi (editors) Preface[ Proceedings of the Second Brazilian Symposium on Graphs, Algorithms and Combinatorics]. Electronic Notes in Discrete Mathematics, (Elsevier Science Publishers) 19, 1-7, 2005.

Trabalhos Submetidos

  1. S.S. Adi and C.E. Ferreira, A graph theoretical model for the Gene Prediction Problem, 2004.
  2. E.C. Bracht, L.A.A. Meira and F.K. Miyazawa. A Primal-dual algorithm for the uniform metric labeling problem, 2005.
  3. 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.
  4. M.H. Carvalho and J. Cheryian, An O(VE) algorithm for ear decomposition of matching covered graphs, 2005.
  5. G. Cintra, F.K. Miyazawa, Y. Wakabayashi, and E.C. Xavier, A note on the approximability of cutting stock problems, 2004.
  6. D. Dellamonica Jr. and Y. Kohayakawa, An algorithmic Friedman-Pippenger theorem on tree embeddings and applications to routing (extended Abstract), 2005.
  7. P. Feofiloff, C.G. Fernandes, C.E. Ferreira, and J.C. de Pina, Approximation algorithms for the Prize-Collecting Steiner Tree Problem, 2005.
  8. C.G. Fernandes, O. Lee, and Y. Wakabayashi, The Minimum Cycle Cover and the Chinese Postman Problems on mixed graphs with bounded tree width, 2003.
  9. C.E. Ferreira, F.M. de Oliveira Filho, Reduction techniques for the group Steiner tree problem, 2004.
  10. A. Fujita, J.R. Sato, M.C. Sogayar, C.E. Ferreira, Non parametric regression and canonical correlation analysis in tumor classification, 2004.
  11. S. Gerke, Y. Kohayakawa, V. Rödl, and A. Steger, Small subsets inherit sparse \epsilon-regularity, 2004.
  12. S. Kingan and M. Lemos, On the circuit-cocircuit intersection conjecture, 2003.
  13. M. Lemos, Matroids with few non-common bases, 2005.
  14. M. Lemos, On the number of triangles in 3-connected matroids, 2005.
  15. M. Lemos, Elements belonging to triangles in 3-connected matroids, 2005.
  16. M. Lemos and T. R. B. Melo, Connected hyperplanes in binary matroids, 2005.
  17. M. Lemos and T. R. B. Melo, Non-separating cocircuits in matroids, 2005.
  18. M. Lemos, T. Reid, B. Williams, and H. Wu, Pairs of largest circuits in 3-connected matroids, 2005.
  19. E.M. Macambira, C.C. de Souza and N. Maculan, Integer programming models for the SONET ring assignment problem, 2004.
  20. E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, The Maximum Agreement Forest Problem: approximation algorithms and computational experiments, 2003.
  21. L.R.B. Salgado and Y. Wakabayashi, Approximation Results on Balanced Connected Partitions of Graphs, 2005.
  22. C.C. de Souza, N. Moreano, A.M.M. Lima, and G. Araujo, The Datapath Merging Problem in Reconfigurable Systems: lower bounds and heuristic evaluation, 2004, 14pp.
  23. E.C. Xavier and F.K. Miyazawa, Approximation schemes for Knapsack Problems with shelf divisions, 2004.
  24. E.C. Xavier and F.K. Miyazawa. A One-Dimensional Bin Packing Problem with Shelf Divisions, 2005.
Last modified: Mon Jul 18 15:02:27 BRT 2005