Complexity of Discrete Structures

Projeto ProNEx 107/97 - MCT/FINEP

Publications of Group Members (Jan/1998-Feb/2003)

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, x+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.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.
  5. 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.
  6. 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]
  7. P. Feofiloff, Algoritmos de Programação Linear, Editora da Universidade de São Paulo, 1999. [ps.gz]
  8. 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]
  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. 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. [pdf.gz | dvi.gz | ps.gz | tex.gz]
  11. C.L. Lucchesi and A.V. Moura, LATIN'98: Theoretical Informatics, Lecture Notes in Computer Science 1380 (1998), Springer-Verlag, Berlin.
  12. 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.
  13. 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.

Publications in Journals

  1. 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]
  2. 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.
  3. 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]
  4. O. Alves, C.E. Ferreira, F.P. Machado, Estimates for the Spreading Velocity of an Epidemic Model, Mathematics and Computers in Simulation, 2003.
  5. 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.
  6. 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]
  7. R. Borndörfer, C. E. Ferreira, and A. Martin, Decomposing matrices into blocks, SIAM Journal on Optimization, 9 (1)(1999), 236-269. [ps.gz]
  8. F. Calheiros, A. Lucena, and C.C. de Souza, Optimal Rectangular Partition, Networks, 41 (1) (2003), 51-67. [ps.gz]
  9. 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]
  10. 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]
  11. 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]
  12. M.B. Campêlo and S. Klein, Maximum vertex-weighted matching in strongly chordal graphs, Discrete Applied Mathematics, 84 (1998), 71-77. [ps.gz]
  13. R. Carmo, J. Donadelli, Y. Kohayakawa and E. Laber, Searching in random partially ordered sets, Theoretical Computer Science, to appear, 20pp.
  14. J.S. Carter and S. Lins, Thin_G theory and local moves for gems, Advances in Mathematics, 143 (1999), 251-283.
  15. 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]
  16. 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.
  17. 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.
  18. 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.
  19. 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.
  20. C.C.B. Cavalcante, Y. Colombani, S. Heipcke, and C.C. de Souza, Scheduling under Labour Resource Constraints, Constraints, 5 (4) (2000), 415-422.
  21. C.C.B. Cavalcante, M.P. Savelsbergh, C.C. de Souza, Y. Wang, and L.A. Wolsey, Scheduling Projects with Labor Constraints, Discrete and Applied Mathematics 112 (1-3) (2001), 27-52.
  22. 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]
  23. M.R. Cerioli and J.L. Szwarcfiter, Edge clique graphs and some classes of chordal graphs, Discrete Mathematics, 242 (2002), 31-39. [pdf]
  24. M.R. Cerioli and J.L. Szwarcfiter, A characterization of edge clique graphs, Ars Combinatoria 60 (2001), 287-292. [ps.gz]
  25. 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]
  26. S. Dantas, C.M.H. de Figueiredo, S. Gravier and Sulamita Klein, Extended skew partition problem, Discrete Mathematics, to appear.
  27. S. Dantas, L. Faria and C.M.H. de Figueiredo, On decision on and optimization (k,l)-graph sandwich problems, Discrete Applied Mathematics, to appear.
  28. S. Dantas, C.M.H. de Figueiredo, S. Gravier, Sulamita Klein, and Bruce Reed, Stable skew partition problem, Discrete Applied Mathematics, to appear.
  29. C.G.T. de A. Moreira and Y. Kohayakawa, Bounds for optimal coverings, Discrete Applied Mathematics, to appear, 14pp. [ps.gz | dvi.gz | tex.gz]
  30. 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.
  31. 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]
  32. 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, to appear. [ps.gz]
  33. 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]
  34. 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]
  35. 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]
  36. 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]
  37. 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]
  38. 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]
  39. 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.
  40. C.M.H. de Figueiredo and K. Vuskovic, A class of beta-perfect graphs, Discrete Mathematics 216 (2000), 169-193. [ps.gz]
  41. C.M.H. de Figueiredo and K. Vuskovic, Recognition of quasi-Meyniel graphs, Discrete Applied Mathematics 113 (2001), 255-260. [ps.gz]
  42. 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]
  43. 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]
  44. 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]
  45. 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]
  46. 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, to appear.
  47. 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.
  48. 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.
  49. 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.
  50. 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]
  51. C.G. Fernandes, A better approximation ratio for the minimum k-edge-connected, Journal of Algorithms, 28 (1) (1998), 105-124. [ps.gz]
  52. 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.
  53. 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]
  54. 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.
  55. C.E. Ferreira, F.K. Miyazawa, and Y. Wakabayashi, Packing squares into squares, Pesquisa Operacional, 19 (1999)(2). [ps.gz]
  56. G. Fonseca, C.M.H. de Figueiredo, and P. C. P. Carvalho, Kinetic hanger, Information Processing Letters, 89 (2004), 151-157.
  57. 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]
  58. 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).
  59. 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]
  60. 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]
  61. 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.
  62. M. Gutierrez and J. Meidanis, On Clique Graph Recognition. Ars Combinatoria 63 (2002), 207-210.
  63. 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.
  64. 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]
  65. 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.
  66. S. Kingan and M. Lemos, Almost graphic matroids, Advances of Applied Mathematics, 28 (3-4)(2002), 438-477.
  67. 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.
  68. 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]
  69. 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]
  70. Y. Kohayakawa, F.K. Miyazawa, P. Raghavan and Y. Wakabayashi. Multidimensional Cube Packing. Algorithmica, to appear. [ps.gz]
  71. 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]
  72. 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]
  73. 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]
  74. Y. Kohayakawa, V. Rödl, and M. Schacht, The Turán theorem for random graphs, Combinatorics, Probability, and Computing, 13:61-91 (2004).
  75. Y. Kohayakawa, V. Rödl, and P. Sissokho, Embedding graphs with bounded degree in sparse pseudorandom graphs, Israel Journal of Mathematics, to appear, 40pp.
  76. 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]
  77. Y. Kohayakawa, V. Rödl, and L. Thoma, An optimal algorithm for checking regularity, SIAM Journal on Computing 32 (5) (2003), 1210-1235.
  78. O. Lee and Y. Wakabayashi, On the circuit cover problem for mixed graphs, Combinatorics, Probability and Computing 11 (2002), 43-59.
  79. O. Lee and Y. Wakabayashi, Note on a min-max conjecture of Woodall, Journal of Graph Theory, 38 (1) (2001), 36-41.
  80. 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]
  81. M. Lemos, On Mills's conjecture on matroids with many common bases, Discrete Mathematics, 240 (2001), 271-276. [dvi.gz | ps.gz]
  82. 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]
  83. M. Lemos, Matroids with many common bases, Discrete Mathematics, 270 (2003), 192-204. [dvi.gz | ps.gz]
  84. M. Lemos, Non-separating cocircuits in binary matroids, Linear Algebra and its Applications, to appear. [dvi.gz]
  85. M. Lemos and J.G. Oxley, On the minor-minimal 3-connected matroids having a fixed minor, Discrete Mathematics, to appear.
  86. M. Lemos and B.M. Junior, Matroids having small circumference, Combinatorics, Probability and Computing, 10 (2001), 349-360. [dvi.gz | ps.gz]
  87. 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]
  88. M. Lemos and J.G. Oxley, On packing minors into connected matroids, Discrete Mathematics, 189 (1998), 283-289.
  89. M. Lemos and J.G. Oxley, On removable circuits in graphs and matroids, Journal of Graph Theory, 30 (1999), 51-66.
  90. 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]
  91. 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]
  92. 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]
  93. 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]
  94. M. Lemos and J. Oxley, On removable cycles throught every edge, Journal of Graph Theory, 42 (2003), 155-164.
  95. M. Lemos and J.G. Oxley, On the minor-minimal 2-connected graphs having a fixed minor, European Journal of Combinatorics 24 (2003), 1097-1123. [ps.gz]
  96. L. Lins, S. Lins, and R. Morabito, 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.
  97. 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.
  98. S. Lins, R. Morábito, and L. Lins, A 9-fold partition heuristic for packing boxes into a container, Investigación Operativa, v.7, n.3, p.69-82, 1999.
  99. S. Lins and M. Mulazzani, Isomorphisms and homeomorphisms of a class of graphs and spaces. Aequationes Math. 64 (1-2) (2002), 110-127.
  100. C.L. Lucchesi, C.P. de Mello, and J.L. Szwarcfiter, On clique-complete graphs, Discrete Mathematics, 183 (1998), 247-254.
  101. 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.
  102. N. Maculan, S.C. Porto, C.C. Ribeiro, and C.C. de Souza, A New Formulation for Scheduling Unrelated Processors under Precedence Constraints. Revue d'Automatique, Informatique et Recherche Operationelle (RAIRO), 33 (1999), 87-90.
  103. 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.
  104. J. Meidanis, O. Porto, and G.P. Telles, On the Consecutive Ones Property, Discrete Applied Mathematics, 88 (1998), 325-354.
  105. 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.
  106. 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.
  107. 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]
  108. 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]
  109. F.K. Miyazawa and Y. Wakabayashi, Cube packing, Theoretical Computer Science, 297 (2003) 1-3, 355--366. [ps.gz]
  110. 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].
  111. 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.
  112. 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.
  113. Y. Wakabayashi, The complexity of computing medians of relations, Resenhas, 3 (3) (1998), 323-349. [ps.gz]
  114. R. Werneck and J. C. Setubal. Finding Minimum Congestion Spanning Trees, ACM Journal on Experimental Algorithmics 5 (2000).
  115. 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]
  116. 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. [ps.gz]
  117. R. Zucchello and R. Dahab, Acyclic clique-interval graphs, Investigación Operativa, 8 (1999), 185-195.

Publications in International Conference Proceedings

  1. 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.
  2. 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]
  3. 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]
  4. 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]
  5. 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]
  6. 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.
  7. 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.
  8. 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]
  9. 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]
  10. 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]
  11. 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.
  12. 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.
  13. 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.
  14. 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
  15. 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.
  16. Z. Dias and J. Meidanis. Sorting by Prefix Transpositions. Proceedings of SPIRE'2002 - String Processing and Information Retrieval. September, 11-13, 2002. Lisbon, Portugal.
  17. 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]
  18. 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.
  19. 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]
  20. 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]
  21. 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]
  22. 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]
  23. 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]
  24. 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.
  25. 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.
  26. 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.
  27. 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
  28. 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]
  29. 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]
  30. 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]
  31. 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]
  32. 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.
  33. 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.
  34. 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.
  35. 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.
  36. 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.
  37. F.K. Miyazawa and Y. Wakabayashi. Packing Problems with Orthogonal Rotations. LATIN'2004: Theoretical Informatics. To appear in Lecture Notes in Computer Science (LNCS), Springer-Verlag. Buenos Aires, Argentina, 2004. ps.gz]
  38. 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).
  39. 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].
  40. 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.
  41. 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.
  42. 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.
  43. 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.

Submitted Manuscripts

  1. S.S. Adi and C.E. Ferreira, An Experimental Evaluation of Gene Prediction Tools, 2004.
  2. S.S. Adi and C.E. Ferreira, A Graph Theoretical Model for the Gene Prediction Problem, 2004.
  3. E. Balas and C.C. de Souza, The Vertex Separation Problem: A Polyhedral Investigation, submitted, 2003, 42pp. [pdf.gz]
  4. J. Boyer, C.G. Fernandes, W.-L. Hsu, A. Noma and J.C. Pina, Correcting and Implementing the PC-tree Planarity Algorithm, 2003.
  5. J. Boyer, C.G. Fernandes, A. Noma and J.C. Pina, Lempel, Even, and Cederbaum Planarith Method, 2004.
  6. 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. Submitted to Genetics and Molecular Biology, 2001.
  7. C.N. Campos, C.P. de Mello, Coloração Total do Cn2, 2002.
  8. M.H. Carvalho, C.L. Lucchesi and U.S.R. Murty, Graphs with independent perfect matchings, 2002.
  9. M.H. Carvalho, C.L. Lucchesi and U.S.R. Murty, How to Build a Brick, 2003.
  10. M.H. Carvalho, C.L. Lucchesi and U.S.R. Murty, The Perfect Matching Polytope and Solid Bricks, 2003.
  11. P. Coll, C.C. Ribeiro, and C.C. de Souza, Multiprocessor Schedule under Precedence Constrints: Polyhedral Results, submitted, 2003, 34pp. [ps.gz]
  12. N.F. de Almeida Jr. and J.C. Setubal, Um modelo oculto de Markov para encontrar promotores em seqüências de DNA, 1998.
  13. C.M.H. de Figueiredo, M. Gutierrez, Linear-time max-cut for split-indifference graphs, 2001.
  14. C.M.H. de Figueiredo and F. Maffray, Optimizing bull-free perfect graphs, 1997. [ps.gz]
  15. 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]
  16. T. Feder, P. Hell, S. Klein and R. Motwani, List Partition Problems, 2000.
  17. P. Feofiloff, C.G. Fernandes, C.E. Ferreira, and J.C. de Pina, Approximation Algorithms for the Prize-Collecting Steiner Tree Problem, 2003.
  18. 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.
  19. V.O. Ferreira, J.Z. Gonçalves, A. Mandel, Free symmetric and unitary pairs, 2001, 22pp.
  20. M. Gutierrez and J. Meidanis, The images under the Clique Operator of all graphs and of clique graphs, 1999.
  21. S. Kingan and M. Lemos, On the circuit-cocircuit intersection conjecture, 2003.
  22. Y. Kohayakawa, B. Nagle, and V. Rödl, Efficient testing of hypergraphs (extended abstract), 2001, 10pp. [dvi.gz | ps.gz]
  23. F. Larrión, C.P. de Mello, A. Morgana, V. Neumann-Lara, and M. Pizaña, The clique operator on cographs and serial graphs, 2001. [ps.gz]
  24. M. Lemos, Elemensts belonging to triands in 3-connected matroids, 2003. [dvi]
  25. M. Lemos, Weight distribuition of the bases of a matroid, 2003. [dvi][ps.gz]
  26. M. Lemos, On the number of non-isomorphic matroids, 2003. [dvi]
  27. M. Lemos and J.G. Oxley, Matroid packing and covering with circuits through an element, 2002.
  28. M. Loparic and C.E. Ferreira, A branch-and-cut algorithm for a vehicle routing problem with capacity and time constraints, 1998 [ps.gz]
  29. C.P. de Mello, A. Morgana, The clique operator on extended P4-sparse graphs, 2002.
  30. C.P. de Mello, A. Morgana, and G. Sontacchi, An algorithm for 1-bend embeddings of planar graphs in the two-dimensional grid, 2001.
  31. 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.
  32. E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, The Maximum Agreement Forest Problem: approximation algorithms and computational experiments.
  33. A.C. da Silva, (...52 other authors...), J.C. Setubal, J. Meidanis, N.F. Almeida Jr. The Complete Sequence of Xanthomonas axonopodis pv. citri and Xanthomonas campestris pv. campestris: two similar plant pathogen with different host specificity, 2001.
  34. T.H. Yunes, A.V. Moura and C.C. de Souza, Hybrid column generation approaches for solving real world crew management problems. Relatório Técnico IC-00-18. Instituto de Computação, UNICAMP, 38 páginas, 2000.

Other Publications
Complexity of Discrete Structures main page.
Y. Kohayakawa <yoshi@ime.usp.br>
Last modified: Thu Feb 19 19:55:41 BRT 2004