Complexity of Discrete Structures

Projeto ProNEx 107/97 - MCT/FINEP


Publications of Group Members (Jan/1998-Nov/2004)

Books and Book Chapters

  1. A.M. Braga, C.M.F. Rubira, and R. Dahab, Tropyc: A Pattern Language for Cryptographic Object-Oriented Software, Pattern Languages of Program Design 4, chapter 16. Addison-Wesley, 1999.
  2. M.H. Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G. Fernandes, C.E. Ferreira, K.S. Guimarães, F.K. Miyazawa, J.C. Pina Jr., J. Soares e Y. Wakabayashi, Uma Introdução Sucinta a Algoritmos de Aproximação, livro texto de um curso intermediário do 23o. Colóquio Brasileiro de Matemática, julho de 2001, IMPA, viii+157pp.
  3. M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, The matching lattice, in Recent Advances in Algorithms and Combinatorics, edited by B. Reed and C.L. Sales, CMS Books in Mathematics, Springer, 2003.
  4. C.C.B. Cavalcante, V.C. Cavalcante, C.C. Ribeiro, and C.C. de Souza, Parallel Cooperative Approaches for the Labor Constrained Scheduling Problem, in Essays and Surveys in Metaheuristics (C.C. Ribeiro and P. Hansen, editors), 2001, Kluwer, 201-225.
  5. H. Everett, C.M.H. de Figueiredo, C.L. Sales, F. Maffray, O. Porto, and B.A. Reed, Even pairs, chapter 4, pp. 67-82, Perfect Graphs, edited by J.L. Ramirez Alfonsin and B.A. Reed, Wiley, 2001. [ps.gz]
  6. P. Feofiloff, Algoritmos de Programação Linear, Editora da Universidade de São Paulo, 1999. [ps.gz]
  7. C.E. Ferreira e Y. Wakabayashi, Planos-de-corte Faciais e a Resolução de Problemas de Otimização Combinatória, I Encontro de Matemática Aplicada e Computacional, ERMAC, 1998. [ps.gz]
  8. C.M.H. de Figueiredo e J. Szwarcfiter, Emparelhamentos em Grafos: Algoritmos e Complexidade, JAI'99 (Jornada de Atualização em Informática), Congresso da SBC, julho 1999.
  9. K.S. Guimarães, Algoritmos de Aproximação para Problemas de Otimização, JAI'98 (Jornada de Atualização em Informática), Congresso da SBC, agosto 1998.
  10. K.S. Guimarães e J.C.B. Melo. Uma Introdução à Análise de Seqüências e Estruturas Biológicas. In: Juan Manuel Adán Coello; Sandra C. P. Ferraz Fabbri. (Org.). Jornadas de Atualização em Informática - JAI 2003, 1-44.
  11. Y. Kohayakawa and V. Rödl, Szemerédi's regularity lemma and quasi-randomness, in Recent Advances in Algorithms and Combinatorics, edited by B. Reed and C.L. Sales, CMS Books in Mathematics, Springer, 2003, 289-351. [pdf.gz | dvi.gz | ps.gz | tex.gz]
  12. C.L. Lucchesi and A.V. Moura, LATIN'98: Theoretical Informatics, Lecture Notes in Computer Science 1380 (1998), Springer-Verlag, Berlin.
  13. J. Meidanis, A Simple Toolkit for DNA Fragment Assembly, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (Farach-Colton, M.; Roberts, F.S.; Vingron, M.; Waterman, M. editors), vol. 47, American Mathematical Society, 1999, 271-288.
  14. J. Meidanis and Z. Dias, An alternative algebraic formalism for genome rearrangements, in D. Sankof and J. Nadeau (eds), Comparative genomics (2000) 213-223, Kluwer.
  15. J. Meidanis, Global Alignment, in D.N. Cooper (ed), Nature Encyclopedia of the human genome (2003).
  16. J. Meidanis, Sequence Assembly, in D.N. Cooper (ed), Nature Encyclopedia of the human genome (2003).
  17. F.K. Miyazawa, Programação Inteira, XI Escola Regional de Informática SBC - Paraná, 2003.
  18. C.G. de A. Moreira e Y. Kohayakawa, Tópicos em Combinatória Contemporânea, livro texto de um curso elementar do 23o. Colóquio Brasileiro de Matemática, julho de 2001, IMPA, x+145pp.
  19. M.-F. Sagot and Y. Wakabayashi, Pattern Inference under many Guises, in Recent Advances in Algorithms and Combinatorics, edited by B. Reed and C.L. Sales, CMS Books in Mathematics, Springer, 2003.
  20. J. C. Setubal. Bioinformatics, in L. Mir (ed), Genomics, Editora Atheneu, 105-118, 2004.
  21. J. C. Setubal and A. C. R. da Silva, Genomic approaches to the study of plant pathogenic bacteria, in Robert M. Goodman (ed), Encyclopedia of Plant and Crop Science, Marcel Dekker, 524-526, 2004.
  22. D. W. Wood, J. C. Setubal, and E. W. Nester. Genome sequence analysis of prokaryotic plant pathogens, in M. Gillings and A. Holmes (eds.), Plant microbiology, 223-241, BIOS Scientific Publishers (Oxford, UK) in cooperation with Marcel Dekker, 2004.

Publications in Journals

  1. L. Alcon, C.M.H. de Figueiredo, M. Cerioli, M. Gutierrez, and J. Meidanis, Tree Loop Graphs, Discrete Applied Mathematics, to appear.
  2. N.F. Almeida Jr., M.S.S. Felipe, et al. Transcriptome characterization of the dimorphic and pathogenic fungus Paracoccidioides brasiliensis by EST analysis, Yeast, 263-271, Vol.20, No.3, 2003. [Abstract] [Full Text] [PDF]
  3. N.F. Almeida Jr., J.C. Setubal, J. Meidanis, et al., Comparison of the genomes of two Xanthomonas pathogens with differing host specificities. Nature, 417 (2002), 459-463.
  4. N.F. Almeida Jr., J.C. Setubal, M.A. Van Sluys, et al. Comparative analyses of the complete genome sequences of Pierce's Disease and Citrus Variegated Chlorosis strains of Xylella fastidiosa, Journal of Bacteriology, 1018-1026, Vol. 185, No. 3, 2003. [Abstract] [HTML] [PDF]
  5. O. Alves, C.E. Ferreira, F.P. Machado, Estimates for the Spreading Velocity of an Epidemic Model, Mathematics and Computers in Simulation, Vol. 64/6, 609-616, 2003.
  6. E. Balas and C.C. de Souza, The Vertex Separation Problem: A Polyhedral Investigation, Mathematical Programming (2004), to appear.
  7. B. Bollobás, J. Donadelli, Y. Kohayakawa, and R.H. Schelp, Ramsey minimal graphs, Journal of the Brazilian Computer Society 7 (3)(2002), 27-37.
  8. B. Bollobás, Y. Kohayakawa, and R.H. Schelp, Essentially infinite colourings of graphs, The Journal of the London Mathematical Society, Second Series, 61 (3) (2000), 658-670. [tex.gz | dvi.gz | ps.gz]
  9. R. Borndörfer, C. E. Ferreira, and A. Martin, Decomposing matrices into blocks, SIAM Journal on Optimization, 9 (1)(1999), 236-269. [ps.gz]
  10. M.D.V. Braga, Z. Dias, T.L. Lin, J. Meidanis, J.A.A. Quitzau, F.R. da Silva, and G.P. Telles. Bioinformatics of the Sugarcane EST Project. Genetics and Molecular Biology, 2001.
  11. F. Calheiros, A. Lucena, and C.C. de Souza, Optimal Rectangular Partition, Networks, 41 (1) (2003), 51-67. [ps.gz]
  12. G. Calinescu, C.G. Fernandes, U. Finkler, and H. Karloff, A better approximation algorithm for finding planar subgraphs, Journal of Algorithms 27 (2) (1998), 269-302. [ps.gz]
  13. G. Calinescu, C.G. Fernandes, H. Karloff, and A. Zelikovski, A new approximation algorithm for finding heavy planar subgraphs, Algorithmica (2003) 36: 179-205. [ps.gz]
  14. G. Calinescu, C.G. Fernandes and B. Reed, Multicuts in Unweighted Graphs and Digraphs with Bounded Degree and Bounded Tree-Width, Journal of Algorithms 48 (2), 333-359 (2003). [ps.gz]
  15. M.B. Campêlo and S. Klein, Maximum vertex-weighted matching in strongly chordal graphs, Discrete Applied Mathematics, 84 (1998), 71-77. [ps.gz]
  16. C. N. Campos and C. P. de Mello, Coloração Total do $C_{n}^{2}$, TEMA Tendências Matemática Aplicada e Computacional, 4 (02) (2004), 177-186.
  17. R. Carmo, J. Donadelli, Y. Kohayakawa and E. Laber, Searching in random partially ordered sets, Theoretical Computer Science, to appear, 321 (2004), no. 1, 41-57.
  18. J.S. Carter and S. Lins, Thin_G theory and local moves for gems, Advances in Mathematics, 143 (1999), 251-283.
  19. M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, Ear decompositions of matching covered graphs, Combinatorica, 19 (2) (1999), 151-174. [ps.gz]
  20. M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, On a conjecture of Lovász concerning bricks I: The characteristic of a matching covered graph, Journal of Combinatorial Theory (B), 85 (1) (2002), 94-136.
  21. M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, On a conjecture of Lovász concerning bricks II: Bricks of Finite Characteristic, Journal of Combinatorial Theory (B), 85 (1) (2002), 137-180.
  22. M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, Optimal ear decompositions of matching covered graphs and bases for the matching lattice, Journal of Combinatorial Theory (B), 85 (1) (2002), 59-93.
  23. 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.
  24. M.H. Carvalho, C.L. Lucchesi and U.S.R. Murty, How to Build a Brick, Discrete Mathematics (2004), to appear.
  25. M.H. Carvalho, C.L. Lucchesi, and U.S.R. Murty, Graphs with independent perfect matchings, Journal of Graph Theory, 48 (2005), 19-50.
  26. M.H. Carvalho, C.L. Lucchesi and U.S.R. Murty, On the Number of Dissimilar Pfaffian Orientations of Graphs, RAIRO - Theoretical Informatics and Applications (2004), to appear.
  27. C.C.B. Cavalcante, Y. Colombani, S. Heipcke, and C.C. de Souza, Scheduling under Labour Resource Constraints, Constraints, 5 (4) (2000), 415-422.
  28. C.C.B. Cavalcante, M.P. Savelsbergh, C.C. de Souza, Y. Wang, and L.A. Wolsey, Scheduling Projects with Labor Constraints, Discrete Applied Mathematics 112 (1-3) (2001), 27-52.
  29. M.R. Cerioli, H. Everett, C.M.H. de Figueiredo, and S. Klein, The homogeneous set sandwich problem, Information Processing Letters, 67 (1998), 31-35. [ps.gz]
  30. M.R. Cerioli and J.L. Szwarcfiter, Edge clique graphs and some classes of chordal graphs, Discrete Mathematics, 242 (2002), 31-39. [pdf]
  31. M.R. Cerioli and J.L. Szwarcfiter, A characterization of edge clique graphs, Ars Combinatoria 60 (2001), 287-292. [ps.gz]
  32. M.R. Cerioli and J.L. Szwarcfiter, Characterizing Intersection Graphs of Substars of a Star, Ars Combinatoria, to appear.
  33. B.V. Cherkassky, A.V. Goldberg, P. Martin, J.C. Setubal, and J. Stolfi, Augment or Push? A computational study of bipartite matching and unit capacity maximum flow algorithms, ACM Journal on Experimental Algorithmics, 38 pp. (electronic). [ps.gz | jea]
  34. P. Coll, C.C. Ribeiro, and C.C. de Souza, Multiprocessor Schedule under Precedence Constrints: Polyhedral Results, Discrete and Applied Mathematics (2004), to appear. [ps.gz]
  35. R. Cordovil, D. Forge e S. Klein, How is a Chordal Graph like a Supersolvable Binary Matroid, Discrete Mathematics 288 (2004), 167-172.
  36. S. Dantas, C.M.H. de Figueiredo, S. Gravier, and S. Klein, Extended skew partition problem, Discrete Mathematics, to appear.
  37. S. Dantas, L. Faria, and C.M.H. de Figueiredo, On decision on and optimization (k,l)-graph sandwich problems, Discrete Applied Mathematics, 143 (2004), 155-165.
  38. S. Dantas, C.M.H. de Figueiredo, S. Gravier, S. Klein, and B. Reed, Stable skew partition problem, Discrete Applied Mathematics, 143 (2004), 17-22.
  39. S. Dantas, C.M.H. de Figueiredo, S. Gravier, and S. Klein, Finding H-partitions efficiently, RAIRO - Theoretical Informatics and Applications, to appear.
  40. C.G.T. de A. Moreira and Y. Kohayakawa, Bounds for optimal coverings, Discrete Applied Mathematics, 141 (2004), no. 1­3, 263-276. [ps.gz | dvi.gz | tex.gz]
  41. R. DeMarco, A. Kowaltowski, A. Machado, M. Bento Soares, C. Gargioni, T. Kawano, V. Rodrigues, A. Madeira, R. A. Wilson, C. Menck, J. C. Setubal, E. Dias-Netto, L. Leite, S. Verjovski-Almeida, Saci-1, -2, and-3 and Perere, Four novel retrotransposons with high transcriptional activities from the human parasite Schistosoma mansoni, Journal of Virology, 78:6, (2004) 2967-2978.
  42. V.M.F. Dias, C.M.H. de Figueiredo, and J.L. Szwarcfiter, Generating bicliques of a graph in lexicographic order. Theoretical Computer Science, to appear.
  43. L. A. Digiampietri, C. B. Medeiros, J. C. Setubal. A data model for comparative genomics, Revista Tecnologia da Informação, 3(2) (2003), 35-40, 2003.
  44. V. Dias, G. Fonseca, C.M.H. de Figueiredo, and J. Szwarcfiter, The stable marriage problem with restricted pairs, Theoretical Computer Science, 306 (2003), 391-405. [ps.gz]
  45. J. Donadelli, P. E. Haxell, and Y. Kohayakawa, A note on the size­Ramsey number of long subdivisions of graphs, RAIRO - Theoretical Informatics and Applications, to appear.
  46. J. Donadelli and Y. Kohayakawa, A density result for random sparse oriented graphs and its relation to a conjecture of Woodall, Electronic Journal of Combinatorics, 9 (1) (2002), Research paper 45, 10pp. [pdf.gz | ps.gz | dvi.gz | tex.gz]
  47. H. Everett, C. M. H. de Figueiredo, S. Klein, and B. Reed, The perfection and recognition of bull-reducible Berge graphs, RAIRO - Theoretical Informatics and Applications, to appear.
  48. M.H.C.Fampa, S. Klein, F. Protti, D.C.A. Rêgo, Optimal grid representations, Networks, 44 (3) (2004), 187-193.
  49. L. Faria and C. M. H. de Figueiredo. On Eggleton and guy conjectured upper bound for the crossing number of the n-cube, Mathematica Slovaca, 50 (2000), 271-287. [ps.gz]
  50. L. Faria, C.M.H. de Figueiredo, and C.F.X. de Mendonça Neto, Splitting number is NP-complete, Discrete Applied Mathematics 108 (2001), 65-83. [esls]
  51. L. Faria, C.M.H. de Figueiredo, and C. F. X. de Mendonça Neto, On the complexity of the approximation of nonplanarity parameters for cubic graphs, Discrete Applied Mathematics 141 (2004), 119-134.
  52. L. Faria, C. M. H. de Figueiredo, J. Stolfi, C. F. X. de Mendonça Neto, and E. F. Xavier, The splitting number and skewness of Cn x Cm, Ars Combinatoria, 63 (2002), 193-205.
  53. L. Faria, C.M.H. de Figueiredo, J. Stolfi, and C. F. X. de Mendonça Neto, The non planar vertex deletion of Cn x Cm", Ars Combinatoria, to appear.
  54. A.X. Falcão, J.K. Udupa, and F.K. Miyazawa, An Ultra-Fast User-Steered Segmentation Paradigm: Live-Wire-On-The-Fly, IEEE Transactions on Medical Imaging, 19 (1) (2000), 55-62.
  55. T. Feder, P. Hell, S. Klein, and R. Motwani, List Partitions. SIAM J. Discrete Math. 16(3): 449-478 (2003).
  56. D. Ferber, T. Dias, A. Moura, C.C. de Souza, Constructing Nurse Schedules at Large Hospitals, International Transactions in Operations Research, 10 (2003), 245-265. [pdf.gz]
  57. C.G. Fernandes, A better approximation ratio for the minimum k-edge-connected, Journal of Algorithms, 28 (1) (1998), 105-124. [ps.gz]
  58. C.G. Fernandes, E. Green, and A. Mandel, "From monomials to words to graphs", Journal of Combinatorial Theory A, to appear. Available at the arXiv.org e-Print archive.
  59. M. Ferrara, Y. Kohayakawa and V. Rödl, Distance graphs on the integers, Combinatorics, Probability, and Computing, to appear, 23pp.
  60. C.E. Ferreira, C.C. de Souza, and Y. Wakabayashi, Rearrangement of DNA fragments: a branch-and-cut algorithm, Discrete Applied Mathematics, 116 (1-2) (2002), 161-177. [ps.gz]
  61. C.E. Ferreira, A. Martin, C.C. de Souza, R.Weismantel, and L.A. Wolsey, The node capacitated graph partitioning problem: a computational study, Mathematical Programming, Series B, 8 (1998), 229-256.
  62. C.E. Ferreira, F.K. Miyazawa, and Y. Wakabayashi, Packing squares into squares, Pesquisa Operacional, 19 (1999)(2). [ps.gz]
  63. V.O. Ferreira, J.Z. Gonçalves, A. Mandel, Free symmetric and unitary pairs in division rings with involution, International Journal of Algebra And Computation, 22pp, 2003.
  64. C.M.H. de Figueiredo and G.D. Fonseca, Kinetic heap-ordered trees: tight analysis and improved algorithms, Information Processing Letters, 85 (2003), 165-169.
  65. C.M.H. de Figueiredo, G.D. Fonseca, and P.C. Carvalho, Kinetic hanger, Information Processing Letters, 89 (2004), 151-157.
  66. C.M.H. de Figueiredo, J. Gimbel, C.P. de Mello, and J.L. Szwarcfiter, Even and odd pairs in comparability and in P4-comparability graphs, Discrete Applied Mathematics 90 (1999), 293-297. [ps.gz]
  67. C.M.H. de Figueiredo, J. Gimbel, C. P. de Mello, and J. L. Szwarcfiter. A note on transitive orientations with maximum sets of sources and sinks, Discrete Applied Mathematics, 120 (2002), no. 1-3, 91-95. [ps.gz]
  68. C.M.H. de Figueiredo, S. Gravier, and C. L. Sales. On Tucker's proof of the Strong Perfect Graph Conjecture for (K4 - e)-free graphs, Discrete Mathematics 232 (1-3) (2001), 105-108. [ps.gz]
  69. C.M.H. de Figueiredo, S. Klein, Y. Kohayakawa, and B. Reed, Finding skew partitions efficiently, Journal of Algorithms, 37 (2) (2000), 505-521. [Original article]
  70. C.M.H. de Figueiredo, S. Klein, and K. Vuskovic, The graph sandwich problem for 1-join composition is NP-complete, Discrete Applied Mathematics 121 (1-3) (2002), 73-82. [ps.gz]
  71. C.M.H. de Figueiredo, F. Maffray, and C. Hoang, A characterization of P4-Comparability graphs. Discrete Mathematics, to appear.
  72. C.M.H. de Figueiredo and F. Maffray, Optimizing bull-free perfect graphs, SIAM Journal on Discrete Mathematics, 18 (2004), 226-240. [ps.gz]
  73. C.M.H. de Figueiredo, F. Maffray, and O. Porto, On the structure of bull-free perfect graphs, 2: the weakly chordal case, Graphs and Combinatorics, 17 (2001), 435-456. [ps.gz]
  74. C.M.H. de Figueiredo, J. Meidanis, and C.P. de Mello, Local conditions for edge-coloring, Journal of Combinatorial Mathematics and Combinatorial Computing, 32 (2000), 79-91. [ps.gz]
  75. C.M.H. de Figueiredo, J. Meidanis, and C.P. de Mello, Total chromatic number and chromatic index of dually chordal graphs, Information Processing Letters, 70 (1999), 147-152. [ps.gz]
  76. C.M.H. de Figueiredo, J. Meidanis, C.P. de Mello, and C. Ortiz, Decompositions for the edge colouring of reduced indifference graphs, Theoretical Computer Science, 297 (2003), 145-155.
  77. C.M.H. de Figueiredo and V. G. P. Sa, Note on the homogeneous set sandwich problem, Information Processing Letters, 93 (2005), p. 75-81.
  78. C.M.H. de Figueiredo and K. Vuskovic, A class of beta-perfect graphs, Discrete Mathematics 216 (2000), 169-193. [ps.gz]
  79. C.M.H. de Figueiredo and K. Vuskovic, Recognition of quasi-Meyniel graphs, Discrete Applied Mathematics 113 (2001), 255-260. [ps.gz]
  80. G. Fonseca, C.M.H. de Figueiredo, and P. C. P. Carvalho, Kinetic hanger, Information Processing Letters, 89 (2004), 151-157.
  81. L.R.G. Fontes, M. Isopi, Y. Kohayakawa, and P. Picco, The spectral gap of the REM under Metropolis dynamics, Annals of Applied Probability 8 (3) (1998), 917-943. [tex.gz | dvi.gz | ps.gz]
  82. E. Friedgut, Y. Kohayakawa, V. Rödl, A. Rucinski, and P. Tetali, Ramsey games against a one-armed bandit, Combinatorics, Probability, and Computing, 12:515-545 (2003).
  83. J.Z. Gonçalves, A. Mandel, and M. Shirvani, Free products of units in algebras. Part I: Quaternion algebras, Journal of Algebra 214 (1999), 301-316. [ps.gz]
  84. J.Z. Gonçalves, A. Mandel, and M. Shirvani, Free products of units in algebras. Part II: Crossed products, J. of Algebra 233 (2) (2000), 567-593. [ps.gz]
  85. J.Z. Gonçalves and A. Mandel, Free subgroups in the group of units of a twisted group algebra, Communications in Algebra 29 (5)(2001), 2231-2238.
  86. M. Gutierrez and J. Meidanis, Algebraic theory for the clique operator, Journal of the Brazilian Computing Society 7 (3) (2001), 53-64.
  87. M. Gutierrez and J. Meidanis, On Clique Graph Recognition. Ars Combinatoria 63 (2002), 207-210.
  88. M. Gutierrez and J. Meidanis, Recognizing Clique Graphs of Directed Edge Path Graphs. Discrete Applied Mathematics, v.126, n.2-3, p.297-304, 2003.
  89. M. Gutierrez and J. Meidanis, Preimage, image, and iterated image of the clique operator, Matematica Contemporanea 25 (2003), 107-123.
  90. R.F. Hashimoto, J. Barrera, and C.E. Ferreira, A combinatorial optimization technique for the sequential decomposition of erosions and dilations, Journal of Mathematical Imaging and Vision 13 (1) (2000), 17-33.
  91. J. C. M. Janssen, K. Kilakos, S. Klein and S.Gravier, Graph covers using t-colourable vertex sets, Discrete Mathematics, 278, (2004), 61-80.
  92. P.E. Haxell and Y. Kohayakawa, Packing and covering triangles in tripartite graphs, Graphs and Combinatorics 14 (1) (1998), 1-10. [tex.gz | dvi.gz | ps.gz]
  93. P. Hell, S. Klein, L.T. Nogueira, and F. Protti, Partitioning Chordal Graphs into Independent Sets and Cliques, Discrete Applied Mathematics 141 (2004), 185-194. [ps.gz]
  94. P. Hell, S. Klein, L.T.Nogueira, and F. Protti, Packing r-cliques in weighted chordal graphs, Annals of Operational Research, to appear.
  95. H. van der Holst and J.C. de Pina, Length-bounded disjoint paths in planar graphs. Sixth Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1999). Discrete Applied Mathematics 120 (1-3) (2002), 251-261.
  96. S. Kingan and M. Lemos, Almost graphic matroids, Advances of Applied Mathematics, 28 (3-4)(2002), 438-477.
  97. S. Kingan and M. Lemos, On weak excluded minors for a class of graphs. Annals of Combinatorics, to appear.
  98. S. Klein, P. Hell, T. Feder, and R. Motwani, List partitions, SIAM Journal on Discrete Mathematics 16 (3) (2003), 449-478.
  99. S. Klein and J. L. Szwarcfiter, A representation for the Modules of a Graph and Applications, Journal of the Brazilian Computer Society , 9 (2003), 9-16.
  100. Y. Kohayakawa and B. Kreuter, The width of random subsets of Boolean lattices, Journal of Combinatorial Theory A, v.100, n.2, 376-386, 2002.
  101. Y. Kohayakawa, B. Kreuter, and D. Osthus, The length of random subsets of Boolean lattices, Random Structures and Algorithms, 16 (2) (2000), 177-194. [tex.gz | dvi.gz | ps.gz]
  102. Y. Kohayakawa, B. Kreuter, and A. Steger, An extremal problem for random graphs and the number of graphs with large even-girth, Combinatorica, 18 (1) (1998), 101-120. [tex.gz | dvi.gz | ps.gz]
  103. Y. Kohayakawa, F.K. Miyazawa, P. Raghavan and Y. Wakabayashi. Multidimensional Cube Packing. Algorithmica, 40 (3) (2004), 173-187. [ps.gz]
  104. Y. Kohayakawa, B. Nagle, and V. Rödl, Hereditary properties of triple systems, Combinatorics, Probability, and Computing 12 (2) (2003), 155-189. [dvi.gz | ps.gz]
  105. Y. Kohayakawa, H.-J. Prömel, and V. Rödl, Induced Ramsey numbers, Combinatorica, 18 (3) (1998), 373-404. [tex.gz | dvi.gz | ps.gz]
  106. Y. Kohayakawa and V. Rödl, Regular pairs in sparse random graphs I, Random Structures and Algorithms 22 (4) (2003), 359-434. [pdf.gz | ps.gz | dvi.gz | tex.gz]
  107. Y. Kohayakawa, V. Rödl, and M. Schacht, The Turán theorem for random graphs, Combinatorics, Probability, and Computing, 13:61-91 (2004).
  108. 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.
  109. Y. Kohayakawa, V. Rödl, and J. Skokan, Hypergraphs, quasi-randomness, and conditions for regularity, J. of Combinatorial Theory (A), 97 (2) (2002), 307-352. [ps.gz | dvi.gz]
  110. Y. Kohayakawa, V. Rödl, and L. Thoma, An optimal algorithm for checking regularity, SIAM Journal on Computing 32 (5) (2003), 1210-1235.
  111. Y. Kohayakawa, M. Simonovits, and J. Skokan, The 3­colored Ramsey number of odd cycles, Electronic Notes in Discrete Mathematics, Elsevier Science Publishers, 2005, 6pp.
  112. F. Larrión, C.P. Mello, A. Morgana, V. Neumann-Lara, and M. Pizaña, The clique operator on cographs and serial graphs, Discrete Mathematics, 282 (2004), 183-191. [ps.gz]
  113. O. Lee and Y. Wakabayashi, On the circuit cover problem for mixed graphs, Combinatorics, Probability and Computing 11 (2002), 43-59.
  114. O. Lee and Y. Wakabayashi, Note on a min-max conjecture of Woodall, Journal of Graph Theory, 38 (1) (2001), 36-41.
  115. M. Lemos, On the connectivity function of a binary matroid, Journal of Combinatorial Theory, Series (B), 86 (1) (2002), 114-132. [tex.gz | dvi.gz | ps.gz]
  116. M. Lemos, On Mills's conjecture on matroids with many common bases, Discrete Mathematics, 240 (2001), 271-276. [dvi.gz | ps.gz]
  117. M. Lemos, Uniqueness of the decomposition of the rank function of a 2-polymatroid, Discrete Mathematics, 269 (2003), 161-179. [tex.gz | dvi.gz | ps.gz]
  118. M. Lemos, Matroids with many common bases, Discrete Mathematics, 270 (2003), 192-204. [dvi.gz | ps.gz]
  119. M. Lemos, Non-separating cocircuits in binary matroids, Linear Algebra and its Applications, 382 (2004), 171-178. [dvi.gz]
  120. M. Lemos, Elements belonging to triads in 3-connected matroids. Discrete Mathematics, North Holland, 285 (2004), 167-181. [dvi]
  121. M. Lemos, On the number of non-isomorphic matroids. Advances in Applied Mathematics, Academic Press, 33 (2004), 733-746. [dvi]
  122. M. Lemos and B.M. Junior, Matroids having small circumference, Combinatorics, Probability and Computing, 10 (2001), 349-360. [dvi.gz | ps.gz]
  123. M. Lemos and S. Mota, The reconstruction of a matroid from its connectivity function, Discrete Mathematics, 220 (2000), 131-143. [tex.gz | dvi.gz | ps.gz]
  124. M. Lemos and J.G. Oxley, On packing minors into connected matroids, Discrete Mathematics, 189 (1998), 283-289.
  125. M. Lemos and J.G. Oxley, On removable circuits in graphs and matroids, Journal of Graph Theory, 30 (1999), 51-66.
  126. M. Lemos and J.G. Oxley, On size, circumference and circuit removal in 3-connected matroids, Discrete Mathematics, 220 (2000), 145-157. [tex.gz | dvi.gz | ps.gz]
  127. M. Lemos and J.G. Oxley, On the 3-connected matroids that are minimal having a fixed spanning restriction, Discrete Mathematics, 218 (2000), 131-165. [tex.gz | dvi.gz | ps.gz]
  128. M. Lemos and J.G. Oxley, A sharp bound on the size of a connected matroid, Transactions of the American Mathematical Society 353 (2001), 4039-4056. [tex.gz | dvi.gz | ps.gz]
  129. M. Lemos, J.G. Oxley, and T.J. Reid, On the 3-connected matroids that are minimal having a fixed restriction, Graphs and Combinatorics, 16 (2000), 285-318. [tex.gz | dvi.gz | ps.gz]
  130. M. Lemos and J. Oxley, On removable cycles throught every edge, Journal of Graph Theory, 42 (2003), 155-164.
  131. M. Lemos and J.G. Oxley, On the minor-minimal 2-connected graphs having a fixed minor, Discrete Mathematics, 280 (2004), 77-118.
  132. M. Lemos and J.G. Oxley, On the minor-minimal 3-connected matroids having a fixed minor, European Journal of Combinatorics 24 (2003), 1097-1123. [ps.gz]
  133. S. Lins, Thin-G theory an local moves for Gems. Adv. Math., 143 (1999), 252-283.
  134. S. Lins, L. Lins, and R. Morábito, A 9-fold partition heuristic for packing boxes into a container, Investigación Operativa, v.7, n.3, p.69-82, 1999.
  135. L. Lins, S. Lins, and R. Morábito, An n-tet graph approach for non-guillotine packings of n-dimensional boxes into an n-container, European Journal of Operational Research 141 (2) (2002), 421-439.
  136. L. Lins, S. Lins, and R. Morábito, An L-approach for packing (l,w)-rectangles into rectangular and L-shaped pieces. Journal of the Operational Research Society, 54 (2003), 777-789.
  137. L. Lins, S. Lins, and S.B. Melo, Phorma; perfectly hashable order restricted multidimensional arrays. Discrete Applied Mathematics, 141 (2004), 209-223.
  138. S. Lins and C.S. Martins, A planar proof of Ferri's 3-D switching lemma and a combinatorial homogeneity theorem. Atti Sem. Mat. Fis. Univ. Moderna 49 (2001), suppl., 73-89.
  139. S. Lins and M. Mulazzani, Isomorphisms and homeomorphisms of a class of graphs and spaces. Aequationes Math. 64 (1-2) (2002), 110-127.
  140. C.L. Lucchesi, C.P. de Mello, and J.L. Szwarcfiter, On clique-complete graphs, Discrete Mathematics, 183 (1998), 247-254.
  141. E. Macambira and C.C. de Souza, The edge-weighted clique problem: valid inequalities, facets and polyhedral computations, European Journal on Operational Research, 123 (2000), 346-371.
  142. N. Maculan, S.C. Porto, C.C. Ribeiro, and C.C. de Souza, A New Formulation for Scheduling Unrelated Processors under Precedence Constraints. RAIRO - Operations Research, 33 (1999), 87-90.
  143. J. Meidanis, M.D.V. Braga, and S. Verjovski-Almeida, Whole-genome analysis of transporters in the plant pathogen Xylella fastidiosa. Microbiology and Molecular Biology Reviews, 66 (2) (2002), 272-299.
  144. J. Meidanis, O. Porto, and G.P. Telles, On the Consecutive Ones Property, Discrete Applied Mathematics, 88 (1998), 325-354.
  145. J. Meidanis, M.M.T. Walter, and Z. Dias. A Lower Bound on the Reversal and Transposition Diameter, Journal of Computational Biology, 9 (5)(2002), 743-745.
  146. J.C.B. Melo, G.D.C. Cavalcanti, and K.S. Guimarães. Protein Secondary Structure Prediction: Efficient Neural Network and Feature Extraction Approaches, Electronics Letters, 40:21 (2004), 1358-1359.
  147. C.P. de Mello, A. Morgana, and G. Sontacchi, An algorithm for 1-bend embeddings of planar graphs in the two-dimensional grid, Discrete Applied Mathematics, to appear.
  148. C.P. de Mello and A. Morgana, The clique operator on extended P4-sparse graphs, Matematica Contemporanea, v.25, p.33-47, 2003.
  149. C.N. de Menezes and C.C. de Souza, Exact solutions of rectangular partitions via integer programming, International Journal on Computational Geometry and Applications and Applications, 10 (5) (2000), 477-522.
  150. F.K. Miyazawa and Y. Wakabayashi, Approximation algorithms for the orthogonal z-oriented three-dimensional packing problem, SIAM Journal on Computing, 29 (3) (2000), 1008-1029. [ps.gz | pdf.gz]
  151. F.K. Miyazawa and Y. Wakabayashi. Parametric on-line approximation algorithms for packing rectangles and boxes, European Journal of Operational Research, 150:281--292, 2003. [ps.gz]
  152. F.K. Miyazawa and Y. Wakabayashi, Cube packing, Theoretical Computer Science, 297 (2003) 1-3, 355--366. [ps.gz]
  153. C. B. Monteiro-Vitorello, L. E. A. Camargo, N.F. Almeida Jr.,... ,J. C. Setubal, The Genome Sequence of the Gram-Positive Sugarcane Pathogen Leifsonia xyli subsp. xyli, Molecular Plant-Microbe Interactions, 17:8 (2004), 827-836.
  154. 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.
  155. L. M. Moreira, R. F. de Souza, L. Digiampietri, A. C. Rasera da Silva, and J. C. Setubal. Comparative analyses of Xanthomonas and Xylella complete genomes, OMICS: A Journal of Integrative Biology, to appear.
  156. L. M. Moreira, R. F. de Souza, N. F. Almeida Jr., J. C. Setubal, J. C. F. Oliveira, L. R. Furlan, J. A. Ferro, A. C. R. da Silva. Comparative genomics analyses of citrus-associated bacteria, Annual Review of Phytopathology, 42 (2004), 163-184.
  157. A. Morgana, C. P. de Mello, and G. Sontacchi, An algorithm for 1-bend embeddings of plane graphs in the two-dimensional grid, Discrete Applied Mathematics, 141 (2004) 225-241.
  158. A. L. T. O. Nascimento,..., J.C. Setubal, D. A. Haake and E.A.L. Martins, Genome features of Leptospira interrogans serovar Copenhageni, Brazilian Journal of Medical and Biological Research, 37(2) 2004.
  159. A.L.T.O. Nascimento,..., J.C. Setubal, M.A. van Sluys, Comparative genomics of two Leptospira interrogans serovars reveals novel insights into physiology and pathogenesis, Journal of Bacteriology, 186(7):2164-2172, 2004.
  160. J.C. de Pina and J. Soares, Improved bound for the Carathéodory rank of the bases of a matroid, Journal of Combinatorial Theory (B) 88 (2003), no. 2, 323--327. [ps.gz].
  161. 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.
  162. A.J.G. Simpson, (...114 other authors...), J. Meidanis, and J.C. Setubal. The genome sequence of the plant pathogen Xylella fastidiosa, Nature, 406 (2000), 151-157.
  163. M.A. van Sluys, C.B. Monteiro-Vitorello, L.E.A. Camargo, C.F.M. Menck, A.C.R. da Silva, J.A. Ferro, M.C. Oliveira, J.C. Setubal, J.P. Kitajima, and A.J.G. Simpson. Comparative genomic analysis of plant- associated bacteria. Annual Review of Phytopathology, 40 (2002), 169-189.
  164. C.C. de Souza and E. Balas, The Vertex Separator Problem: Algorithms and Computations, Mathematical Programming (2004), to appear.
  165. S. Verjovski-Almeida, E. Dias-Neto, L.C. Leite, J.C. Setubal, J.P. Kitajima, J.P. Piazza, Transcriptome analysis of the acoelomate human parasite Schistosoma mansoni. Nature Genetics, v.35, p.1-10, 2003.
  166. Y. Wakabayashi, The complexity of computing medians of relations, Resenhas, 3 (3) (1998), 323-349. [ps.gz]
  167. R. Werneck and J. C. Setubal. Finding Minimum Congestion Spanning Trees, ACM Journal on Experimental Algorithmics 5 (2000).
  168. D.W. Wood, (...48 other authors...), J.C. Setubal, N.F. Almeida Jr. The genome of the Natural Genetic Engineering Agrobacterium tumefaciens C58, Science, 294 (2001), 2317-2323. [ps.gz]
  169. E.C. Xavier and F.K. Miyazawa, Practical comparison of approximation algorithms for scheduling problems, Pesquisa Operacional 24(2), 2004.
  170. T.H. Yunes, A.V. Moura, and C.C. de Souza, Hybrid column generation approaches for solving real world crew management problems. Transportation Science, to appear, 38pp. [ps.gz]
  171. R. Zucchello and R. Dahab, Acyclic clique-interval graphs, Investigación Operativa, 8 (1999), 185-195.

Publications in International Conference Proceedings

  1. S.S. Adi and C.E. Ferreira, DNA Fragments Assembly Programs: a Comparative Study, Proceedings of the GRACO (2001), Fortaleza, Brazil.
  2. L. Alcon, C.M.H. de Figueiredo, M. Cerioli, M. Gutierrez e J. Meidanis, Tree Loop Graphs, Proceedings of the LACGA (2004), Santiago, Chile.
  3. N.F. Almeida Jr., C.E.R. Alves, E.N. Cáceres and S.W. Song, Comparison of Genomes using High-Performance Parallel Computing Proceedings of 15th Symposium on Computer Architecture and High Performance Computing SBAC-PAD 2003 - Brazilian Computer Society (SBC), São Paulo, SP, Brazil, November 10-12, 2003 IEEE Computer Society, pp. 142-148, 2003.
  4. N. Alon, M.R. Capalbo, Y. Kohayakawa, V. Rödl, A. Rucinski, and E. Szemerédi, Near-optimum universal graphs for graphs with bounded degrees (extended abstract), Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques (M. Goemans, K. Jansen, J.D.P. Rolim, and L. Trevisan, eds), Lecture Notes in Computer Science 2129, Springer-Verlag, 2001, pp. 170-180 [ps.gz | pdf.gz]
  5. N. Alon, M.R. Capalbo, Y. Kohayakawa, V. Rödl, A. Rucinski, and E. Szemerédi, Universality and tolerance (extended abstract), Proceedings of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2000), 14-21, 2000. [tex.gz | dvi.gz | ps.gz]
  6. M.M. Barbosa, C.P. de Mello, and J. Meidanis, Local conditions for edge-colouring of cographs, 29th Southeastern International Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Estados Unidos. Congressus Numerantium, 133 (1998) 45-55. [ps.gz]
  7. J. Barrera, C.E. Ferreira, and R.F. Hashimoto, Finding optimal sequential decompositions of erosions and dilations, Mathematical morphology and its applications to image and signal processing, Kluwer Academic, 1998. [dvi.gz | ps.gz]
  8. 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, 129-144.
  9. 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.
  10. A.M. Braga, C.M.F. Rubira, and R. Dahab, A Pattern Language for Cryptographic Software, Proceedings of the 5th. Pattern Languages of Programs (PLoP '98)(1998), 26 pp.
  11. A.M. Braga, C.M.F. Rubira, and R. Dahab, A Reflective Variation for the Secure-Channel Communication Pattern}, 6th. Pattern Language of Programs (PLoP'99), accepted.
  12. G. Calinescu, C.G. Fernandes, and B. Reed, Multicuts in unweighted graphs with bounded degree and bounded tree-width, Proceedings of IPCO'98 (Integer Programming and Combinatorial Optimization), R. E. Bixby, E. A. Boyd and R. Z. Ríos-Mercado (Eds.), Lecture Notes in Comput. Sci., 1412, Springer, Berlin (1998), 137-152. [ps.gz]
  13. C. N. Campos and C. P. de Mello, A result on the total colouring of powers of cycles, Proceedings of the Latin American Conference on Combinatorics Graphs and Applications, Santiago, Chile, 2004.
  14. R. Carmo, J. Donadelli, Y. Kohayakawa, and E. Laber, Searching in random partially ordered sets (extended abstract), LATIN 2002: Theoretical Informatics (Cancun, 2002), Lecture Notes in Computer Science, Springer, Berlin, 2002, 278-292. [pdf.gz | ps.gz | .dvi.gz]
  15. 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.
  16. M.R. Cerioli, Clique graphs and edge-clique graphs, Proceedings of the 2nd Cologne Twente Workshop on Graphs and Combinatorial Optimization, Enschede, The Netherlands, 2003, p.35-38. ENDM Vol. 13. [ps.gz]
  17. M. R. Cerioli, L. Faria, T. de O. Ferreira and F. Protti, On minimum clique partition and maximum independent set in unit disk graphs and penny graphs: complexity and approximation, Proceedings of the Latin American Conference on Combinatorics, Graphs and Algorithms (2004), Santiago, Chile.
  18. 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.
  19. Z. Dias and J. Meidanis. Sorting by Prefix Transpositions. Proceedings of SPIRE'2002 - String Processing and Information Retrieval. September, 11-13, 2002. Lisbon, Portugal.
  20. H. Everett, S. Klein, and B. Reed, An optimal algorithm for finding clique-cross partitions, 29th Southeastern International Conference on Combinatorics, Graph Theory and Computing, Boca Raton, Estados Unidos. Congressus Numerantium 135 (1998) 171-177. [ps.gz]
  21. A.X. Falcão, J.K. Udupa, and F.K. Miyazawa, An Ultra-Fast User-Steered Segmentation Paradigm: Live-Wire-On-The-Fly, Proceedings of SPIE on Medical Imaging, February 1999, San Diego, CA.
  22. L. Faria, C.M.H. de Figueiredo, and C.F.X. de Mendonça Neto, The splitting number of the 4-cube, Proceedings of LATIN'98: theoretical informatics (Campinas, 1998), C. L. Lucchesi and A. V. Moura (Eds.), Lecture Notes in Comput. Sci.,1380, Springer, Berlin (1998), 141-150. [ps.gz]
  23. L. Faria, C.M.H. de Figueiredo, and C.F.X. de Mendonça Neto, Splitting number is NP-complete, Proceedings of WG'98, Lecture Notes in Computer Science 1517 (1998) 285-297. [ps.gz]
  24. L. Faria, C.M.H. de Figueiredo, and C.F.X. de Mendonça Neto, Optimal node-degree bounds for the complexity of nonplanarity parameters, Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'99, 887-888. [ps.gz]
  25. T. Feder, P. Hell, S. Klein, L. Nogueira and F. Protti, List partitions of Chordal Graphs, Proceedings of the Latin 2004, Lecture Notes in Computer Science 2976 (2004), 100-108.
  26. T. Feder, P. Hell, S. Klein, and R. Motwani, Complexity of Graph Partition Problems, Proceedings of Thirty-First Annual ACM Symposium on Theory of Computing, STOC'99, 464-472. [ps.gz]
  27. C.G. Fernandes and T. Nierhoff, The UPS Problem, Proc. 18th International Symposium in Theoretical Aspects of Computer Science (STACS'2001). Lecture Notes in Computer Science 2129, Springer-Verlag, 2001, pp. 238-246. [ps.gz]
  28. L.C. Ferreira and R. Dahab, A Scheme for Analyzing Electronic Payment Systems, Proceedings of the 14th. Annual Computer Security Applications Conference, ACSAC'98, (1998), 137-146, IEEE Computer Society.
  29. L.C. Ferreira, R. Dahab, M.V.S. Poggi de Aragao, J.A.P. Magalhaes, Two Approaches for Pay-per-Use Software Construction In: WECWIS'2000-Second International Workshop on Advanced issues of E-Commerce and Web-Based Information Systems, 2000, Milpitas - California. Proceedings fo WECWIS 2000. IEEE Computer Society, 2000, 184-191.
  30. 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 (2004), Santiago, Chile.
  31. C.M.H. de Figueiredo, L. Faria, and S.D. Souza, On the Complexity of (k,l)-Graph Sandwich Problems In: WG 2002, Praga. Lecture Notes in Computer Science. Springer, 2002.
  32. C.M.H. de Figueiredo, S. Klein, Y. Kohayakawa, and B. Reed, Finding skew partitions efficiently, Proceedings of LATIN'2000: theoretical informatics (Punta del Este, Uruguay. April, 2000), Lecture Notes in Comput. Sci., 1776, Springer, Berlin (2000), 163-172.
  33. C.M.H. de Figueiredo, C.P. Mello, and C. Ortiz, Edge colouring reduced indifference graphs, Proceedings of LATIN'2000: theoretical informatics (Punta del Este, Uruguay. April, 2000), Lecture Notes in Comput. Sci., 1776, Springer, Berlin (2000), 145-153.
  34. M. Gutierrez and J. Meidanis, On the clique operator, Latin'98 Theoretical Informatics,Proceedings of LATIN'98: theoretical informatics (Campinas, 1998), C.L. Lucchesi and A.V. Moura (Eds.), Lecture Notes in Comput. Sci., 1380 (1998), 261-272.
  35. S. Klein , N.C. Santos, J. L. Szwarcfiter, A representation for the modular pairs of a cograph by modular decomposition, Proceedings of the Latin American conference on Combinatorics, Graphs and Algorithms (2004), Santiago, Chile.
  36. Y. Kohayakawa, C. Mauduit, C.G. de A. Moreira, and V. Rödl, Measures of pseudorandomness for finite sequences: minimum and typical values (extended abstract), Proceedings of WORDS 2003, 4th International Conference on Combinatorics of Words, 159-169, 2003, TUCS General Publication, Turku Centre for Computer Science.
  37. Y. Kohayakawa, B. Nagle, and V. Rödl, Efficient testing of hypergraphs (extended abstract), Proceedings of ICALP 2002, 29th International Colloquium on Automata, Languages, and Programming (Málaga, Spain, July 2002), Lecture Notes in Computer Science 2380, 1017-1028. [dvi.gz | ps.gz]
  38. Y. Kohayakawa, V. Rödl, and L. Thoma, An optimal algorithm for checking regularity (extended abstract), The 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002), San Francisco, CA, 6 to 8 January 2002, 277-286. [ps.gz | dvi.gz]
  39. Y. Kohayakawa and V. Rödl, Algorithmic aspects of regularity (invited paper), Proceedings of LATIN'2000: theoretical informatics (Punta del Este, Uruguay. April, 2000), Lecture Notes in Comput. Sci., 1776, Springer, Berlin (2000), 1-17. [tex.gz | dvi.gz | ps.gz]
  40. Y. Kohayakawa, V. Rödl, and J. Skokan, Equivalent conditions of regularity, Proceedings of LATIN'2000: theoretical informatics (Punta del Este, Uruguay. April, 2000), Lecture Notes in Comput. Sci., 1776, Springer, Berlin (2000), 48-57. [tex.gz | dvi.gz | ps.gz]
  41. O. Lee and Y. Wakabayashi, Circuit covers in series-parallel mixed graphs, Proceedings of LATIN'98: theoretical informatics (Campinas, 1998), C.L. Lucchesi and A.V. Moura (Eds.), Lecture Notes in Comput. Sci., 1380 (1998), 226-238 [ps.gz]
  42. 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.
  43. J.C. López and R. Dahab, Improved Algorithms for Elliptic Curve Arithmetic in GF(2n), Proceedings of the 5th. Annual Workshop on Selected Areas in Cryptography, SAC'98, Lecture Notes in Comput. Sci. (1998), 13 pp. To appear.
  44. J.C. López and R. Dahab, Fast Multiplication on Elliptic Curves over GF($2^m$) without pre-computation, Proceedings of the I Workshop on Cryptographic Hardware and Embedded Systems (CHES), Worcester Polytechnic Institute, Worcester, NY, 1999, to appear as a LNCS.
  45. J.C. López and R.Dahab, An Improvement of the Guajardo-Paar Method for Multiplication on Non-supersingular Elliptic Curves, Proceedings of the 18th. International Conference of the Chilean Computer Science Society, SCCC'98, IEEE Press (1998), 20 pp.
  46. J. Meidanis and Z. Dias. Genome Rearrangements Distance by Fusion, Fission, and Transposition is Easy. Proceedings of SPIRE'2001 - String Processing and Information Retrieval. November, 13-15, 2001. Laguna de San Rafael, Chile.
  47. F.K. Miyazawa and Y. Wakabayashi, Cube packing, Proceedings of LATIN'2000: theoretical informatics (Punta del Este, Uruguay. April, 2000), Lecture Notes in Comput. Sci., vol. 1776 (2000), 58-67.
  48. 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. ps.gz]
  49. A. Morgana, C. P. de Mello, G. Sontacchi, An algorithm for 1-bend embeddings of plane graphs in the two-dimensional grid, Proceedings of the Brazilian Symposium on Graphs, Algorithms and Combinatorics, Fortaleza, Brasil, 2003.
  50. E.W. Myers, P.B. Oliva, and K.S. Guimarães, Reporting exact and approximate regular expression matches, 9th. Combinatorial Pattern Matching (CPM), Piscataway, NJ, July 1998. Lecture Notes in Comput. Sci., 1448 (1998).
  51. J.C. de Pina and J. Soares, A new bound for the Carathéodory rank of the bases of a matroid, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'2000, 942-943. [ps.gz].
  52. E.M. Rodrigues, M-F. Sagot, and Y. Wakabayashi, Some approximation results for the maximum agreement forest problem, APPROX'2001, Lecture Notes in Computer Science 2129 (2001), 159-169.
  53. J.C. Setubal and N.F. Almeida Jr., Detection of related genes in procaryotes using syntenic regions. DIMACS Workshop on Whole Genome Comparison, 2001, Piscataway, NJ, v. 1. p. 17-19.
  54. J. Soares and M.A. Stefanes, Coarse Grained Parallel Algorithm for Maximum Independent Set in Convex Bipartite Graphs. Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications (2001), 527-533.
  55. 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.
  56. C.C. de Souza, A.V. Moura and T.H. Yunes, Solving Very Large Crew Scheduling Problems to Optimality, Proceedings of the 14th ACM Symposium on Applied Computing (SAC 2000), Villa Olmo, Como, Italy. March 19-21, 2000, 446 - 451
  57. C.C. de Souza, T.H. Yunes, and A.V. Moura, A Hybrid Approach for Solving Large Scale Crew Scheduling Problems, Proceedings of the Second International Workshop on Practical Aspects of Declarative Languages (PADL'00). Boston, MA, USA. January 17-20, 2000, Lecture Notes in Computer Science 1753, pp. 293-307.
  58. M.A. Stefanes and J. Soares, BSP/CGM algorithm for maximum matching in convex bipartite graph. IEEE Proceedings of the 15th Symposium on Computer Architecture and High Performance Computing (SBAC-PAD'03), 167-176, São Paulo, 2003.
  59. M. Walter, Z. Dias, and J. Meidanis, Reversal and Transposition distance of linear chromosomes, String Processing and Information Retrieval (SPIRE'98), Santa Cruz de la Sierra, Bolivia (1998), 96-102.
  60. R. Werneck, J.C. Setubal, and A.F. da Conceição. Finding Minimum Congestion Spanning Trees, Proceedings of the Third Workshop on Algorithm Engineering, King's College, London, volume 1668 of Lecture Notes in Computer Science, 60-71, Springer-Verlag, 1999.
  61. E.C. Xavier and F.K. Miyazawa, Approximation Algorithms for Schedulling Jobs in Machines, Proceedings of the XXIX Conferencia Latino Americana de Informatica (2003) 1-21, La Paz, Bolivia.

Submitted Manuscripts

  1. S.S. Adi and C.E. Ferreira, A Graph Theoretical Model for the Gene Prediction Problem, 2004.
  2. S.M. de Almeida, C.P. de Mello e A. Gomide, A classe dos grafos PI, 2004.
  3. N. Alon, Y. Kohayakawa, C. Mauduit, C.G. Moreira, and V. Rödl, Measures of pseudorandomness for finite sequences: minimal values, 2004, 30pp.
  4. C.N. Campos, C.P. de Mello, A result on the total colouring of powers of cycles, 2004.
  5. 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.
  6. G. Cintra, F.K. Miyazawa, Y. Wakabayashi, and E.C. Xavier, Approximation Algorithms for Cutting Stock Problems, 2004.
  7. C.M.H. de Figueiredo, M. Gutierrez, Linear-time max-cut for split-indifference graphs, 2001.
  8. C. De Simone, C.P. de Mello, Edge-colouring of join graphs, 2004.
  9. P. Feofiloff, C.G. Fernandes, C.E. Ferreira, and J.C. de Pina, Approximation Algorithms for the Prize-Collecting Steiner Tree Problem, 2004.
  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, 2003.
  11. C.E. Ferreira, F.M. de Oliveira Filho, Reduction techniques for the group Steiner tree problem, 2004.
  12. A. Fujita, J.R. Sato, M.C. Sogayar, C.E. Ferreira, Non parametric regression and canonical correlation analysis in tumor classification, 2004.
  13. S. Gerke, Y. Kohayakawa, V. Rödl, and A. Steger, Small subsets inherit sparse #­regularity, 2004.
  14. M. Gutierrez and J. Meidanis, The images under the Clique Operator of all graphs and of clique graphs, 1999.
  15. S. Kingan and M. Lemos, On the circuit-cocircuit intersection conjecture, 2003.
  16. M. Lemos, Weight distribution of the bases of a matroid, 2003. [dvi][ps.gz]
  17. M. Lemos and J.G. Oxley, Matroid packing and covering with circuits through an element, 2002.
  18. M. Liverani, A. Morgana, C. P. de Mello, The K-behaviour of p-trees and p-forests, 2004.
  19. E.M. Macambira, C.C. de Souza and N. Maculan, Integer programming models for the SONET ring assignment problem, submitted, 2004.
  20. C. P. de Mello, A. Morgana, and M. Liverani, The clique operator on graphs with few P4's, 2003.
  21. F.K. Miyazawa and Y. Wakabayashi, Two- and Three-dimensional Packings with Rotations, 2004.
  22. M.A. Morais Jr, W.L.S. Silva, A.R.O. Cavalcanti and K.S. Guimarães, Computational Analysis of a Putative Regulatory DNA Binding Site in the Yeast DNA Repair Gene Promoters, 2002.
  23. E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, The Maximum Agreement Forest Problem: approximation algorithms and computational experiments, 2003.
  24. 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, submitted to a conference, 2004, 14pp. [ps.gz]
  25. E.C. Xavier and F.K. Miyazawa, Approximation Schemes for Knapsack Problems with Shelf Divisions, 2004.

Other Publications


Complexity of Discrete Structures main page.
Y. Kohayakawa <yoshi@ime.usp.br>
Last modified: Wed Jan 26 12:17:47 BRST 2005