Structural and Algorithmic Aspects of Combinatorial Objects

Proc. FAPESP no. 96/04505-2

Publications (1996-2000)

Books

  1. P. Feofiloff, Algoritmos de Programação Linear, Editora da Universidade de São Paulo, 1999 [ps.gz]
  2. C.E. Ferreira and 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]

Publications in Journals

  1. B. Bollobás, Y. Kohayakawa, and R.H. Schelp, Essentially infinite colourings of graphs, Journal of the London Mathematical Society 61 (2000), no.3, 658-670. [tex.gz | dvi.gz | ps.gz]
  2. R. Borndörfer, C.E. Ferreira, and A. Martin, Decomposing matrices into blocks, SIAM Journal on Optimization, 9 (1)(1999), 236-269. [ps.gz]
  3. 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]
  4. P. Erdös, A. Gyárfás, and Y. Kohayakawa, The size of the largest bipartite subgraphs, Discrete Mathematics, 177 (1-3) (1997), 267-271. [tex.gz | dvi.gz | ps.gz]
  5. C.G. Fernandes, A better approximation ratio for the minimum k-edge-connected, Journal of Algorithms, 28 (1) (1998), 105-124 [ps.gz]
  6. 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.
  7. C.E. Ferreira, F.K. Miyazawa and Y. Wakabayashi, Packing squares into squares, Pesquisa Operacional, 19(2) (1999) [ps.gz]
  8. C.E. Ferreira, C.C. de Souza, and Y. Wakabayashi, Rearrangement of DNA fragments: a branch-and-cut algorithm, Discrete Applied Mathematics, to appear. [ps.gz]
  9. C.M.H. de Figueiredo, S. Klein, Y. Kohayakawa, B. Reed, Finding skew partitions efficiently, Journal of Algorithms, to appear.
  10. L.R.G. Fontes, M. Isopi, Y. Kohayakawa, and P. Picco, The spectral gap of the REM under the Metropolis dynamics, Annals of Applied Probability, 8 (3) (1998), 917-943. [tex.gz | dvi.gz | ps.gz]
  11. J.Z. Gonçalves, A. Mandel, and M. Shirvani, Free products of units in algebras. Part I: quaternion algebras, J. of Algebra, 214 (1999), 301-316. [ps.gz]
  12. 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.
  13. J.Z. Gonçalves and A. Mandel, Free subgroups in the group of units of a twisted group algebra, Communications in Algebra, to appear.
  14. M.A.M.C. Gurgel and Y. Wakabayashi, Adjacency of vertices of the complete pre-order polytope, Discrete Mathematics, 175 (1-3) (1997), 163-172 [ps.gz]
  15. 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 (2000), no.1, 17-33.
  16. P.E. Haxell and Y. Kohayakawa, Partitioning by monochromatic trees, Journal of Combinatorial Theory, Series B, 68 (2), 218-222, 1996. [tex.gz | dvi.gz | ps.gz]
  17. 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]
  18. P.E. Haxell, Y. Kohayakawa, and T. Luczak, Turán's extremal problem in random graphs: forbidding odd cycles, Combinatorica, 16 (1), 107-122, 1996. [tex.gz | dvi.gz | ps.gz]
  19. Y. Kohayakawa and B. Kreuter, Threshold functions for asymmetric Ramsey properties involving cycles, Random Structures and Algorithms, 11 (3) (1997), 245-276. [tex.gz | dvi.gz | ps.gz]
  20. 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]
  21. Y. Kohayakawa, T. Luczak, and V. Rödl, Ramsey-type results for oriented trees, Journal of Graph Theory, 22 (1), 1-8, 1996. [dvi.gz | ps.gz]
  22. Y. Kohayakawa, T. Luczak, and V. Rödl, Arithmetic progressions of length three in subsets of a random set, Acta Arithmetica, LXXV (2), 133-163, 1996. [tex.gz | dvi.gz | ps.gz]
  23. Y. Kohayakawa, T. Luczak and V. Rödl, On K4-free subgraphs of random graphs, Combinatorica, 17 (2) (1997), 173-213. [tex.gz | dvi.gz | ps.gz]
  24. 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]
  25. 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]
  26. F.K. Miyazawa and Y. Wakabayashi, An algorithm for the three-dimensional packing problem with asymptotic performance analysis, Algorithmica, 18 (1997), 122-144 [ps.gz]
  27. 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]
  28. M. Molloy, B. Reed, and W. Steiger, On the mixing rate of the triangulation walk, Randomization methods in algorithm design (Princeton, NJ, 1997), 179-190, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 43, Amer. Math. Soc., Providence, RI, 1999.
  29. B. Reed, The list colouring constants, Journal of Graph Theory 31 (1999), no. 2, 149-153.
  30. B. Reed, A strengthening of Brooks' theorem, Journal of Combinatorial Theory (B) 76 (1999), no. 2, 136-149.
  31. B. Reed, Mangoes and Blueberries, Combinatorica 19 (1999), no. 2, 267-296.
  32. B. Reed and R. Thomas, Clique minors in graphs and their complements, J. Combin. Theory Ser. B 78 (2000), no. 1, 81-85. [ps.gz]
  33. Y. Wakabayashi, The complexity of computing medians of relations, Resenhas, 3 (3) (1998), 323-349 [ps.gz]

Publications in International Conference Proceedings or in Collected Publications

  1. N. Alon, M.R. Capalbo, Y. Kohayakawa, V. Rödl, A. Rucinski, and E. Szemerédi, Universality and tolerance at the turn of the millennium (extended abstract), Proceedings of the 41st IEEE Annual Symposium on Foundations of Computer Science (FOCS 2000), 2000, to appear. [tex.gz | dvi.gz | ps.gz]
  2. J. Barrera and 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]
  3. B. Bollobás and Y. Kohayakawa, On Richardson's model on the hypercube. In B. Bollobás and A. Thomason, editors, Combinatorics, Geometry and Probability, pages 129-137. Cambridge University Press, Cambridge, 1997. ISBN 0521584728. [tex.gz | dvi.gz | ps.gz]
  4. 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 (1998), 137-152 [ps.gz]
  5. C.G. Fernandes, A Better Approximation Ratio for the Minimum k-edge-connected Spanning Subgraph Problem, Proc. 8th Annual ACM-SIAM Symposium on Discrete Algorithms, EUA, 629-638, 1997 [ps.gz]
  6. C.G. Fernandes and T. Nierhoff, The UPS Problem, Proc. 18th International Symposium in Theoretical Aspects of Computer Science (STACS), 2001. (Copyrights held by Springer-Verlag.) [ps.gz]
  7. C.E. Ferreira and C.C. de Souza and Y. Wakabayashi, Rearrangement of DNA fragments: a branch-and-cut algorithm, Proceedings of the 2nd Workshop on Practical Combinatorial Optimization Problems, Valparaiso, Chile, 1996.
  8. C.E. Ferreira and C.C. de Souza and Y. Wakabayashi, A Polyhedral Approach for DNA Fragments Rearrangement, Proc. of the XVI International Symposium on Math. Programming, Lausanne, 1997.
  9. C.M.H. de Figueiredo, S. Klein, Y. Kohayakawa, 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.
  10. Y. Kohayakawa, Szemerédi's regularity lemma for sparse graphs. In F. Cucker and M. Shub, editors, Foundations of Computational Mathematics, pages 216-230, Berlin, Heidelberg, January 1997. Springer-Verlag. [tex.gz (llncs.sty.gz) | dvi.gz | ps.gz]
  11. 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., to appear. [tex.gz | dvi.gz | ps.gz]
  12. 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., to appear. [tex.gz | dvi.gz | ps.gz]
  13. 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]
  14. F.K. Miyazawa and Y. Wakabayashi, Approximation Algorithms for Packing Problems with Orthogonal Rotations, Proceedings of the XVI International Symposium on Math. Programming, 1997.
  15. 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.
  16. M. Molloy and B. Reed, A Pseudo-random method for list colouring, Proceedings of the WAIT (Buenos Aires, Argentina), August 1997 [ps.gz]
  17. M. Molloy and B. Reed, Colouring graphs whose chromatic number is almost their maximum degree, Proceedings of LATIN'98: theoretical informatics (Campinas, 1998), C. L. Lucchesi and A. V. Moura (Eds.), Lecture Notes in Comput. Sci., 1380 (1998), 216-225 [ps.gz]
  18. M. Molloy and B. Reed, Further algorithmic aspects of the local lemma, STOC (Dallas, TX), 524-529, ACM, New York, 1999.
  19. 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, to appear [ps.gz].

Submitted Manuscripts

  1. G. Calinescu, C.G. Fernandes, H. Karloff, and A. Zelikovski, A new approximation algorithm for finding heavy planar subgraphs, 1998 [ps.gz]
  2. G. Calinescu and C.G. Fernandes, Multicuts in Unweighted Digraphs with Bounded Degree and Bounded Tree-Width, submitted, 2000. [ps.gz]
  3. C.G. Fernandes and R. Thomas, Edge-Coloring Series-Parallel Multigraphs, 2000. [ps.gz]
  4. M.A.M.C. Gurgel and Y.Wakabayashi, The complete pre-order polytope: facets and separation problem, 1997 [ps.gz]
  5. H. van der Holst and J.C. de Pina, Length-bounded disjoint paths in planar graphs, 1999. [ps.gz]
  6. Y. Kohayakawa and B. Kreuter, The width of random subsets of Boolean lattices, 1998. [tex.gz | dvi.gz | ps.gz]
  7. O. Lee and Y. Wakabayashi, Circuit covers and minimum circuits in series-parallel in mixed graphs, 2000. [ps.gz]
  8. O. Lee and Y. Wakabayashi, A note on a min-max conjecture of Woodall, 1999.
  9. M. Loparic and C. E. Ferreira, A branch-and-cut algorithm for a vehicle routing problem with capacity and time constraints, 1998 [ps.gz]
  10. M. Molloy and B. Reed, A Pseudo-random method for list colouring, 1998.
  11. J.C. de Pina and J. Soares, Improved bound for the Carathéodory rank of the bases of a matroid, 1999. [ps.gz].

Publications in National Conference Proceedings

  1. G.F. Cintra and Y. Wakabayashi, Um algoritmo híbrido para o problema de corte unidimensional, XXX SOBRAPO, Anais da III Oficina de Problemas de Corte e Empacotamento, 79-96, Curitiba, 1998 [ps.gz]
  2. C.E. Ferreira and M. Loparic, Uma Aplicação do Método Branch-and-Cut a um Problema de Roteamento de Veículos, Anais do Concurso de Dissertações e Teses da SBC, 509-516, 1997.
  3. F.K. Miyazawa and Y. Wakabayashi, Three-dimensional Packing Problem: Approximation Algorithms and Performance Analysis, Anais da I Oficina Nacional em Problemas de Corte e Empacotamento, 11-16, 1996. (Tech. Report RT-MAC-9610, IME-USP)
  4. F.K. Miyazawa and Y. Wakabayashi, Approximation Algorithms for Packing Small Itens, XX CNMAC - Anais da II Oficina Nacional de Problemas de Cortes e Empacotamento, 7-14, 1997.
  5. F.K. Miyazawa and Y. Wakabayashi, Parametric on-line packing, XXX SOBRAPO, Anais da III Oficina de Problemas de Corte e Empacotamento, 109-121, Curitiba, 1998 [ps.gz]
Structural and Algorithmic Aspects of Combinatorial Objects' Home Page
Cristina G. Fernandes <cris@ime.usp.br>
Last modified: Mon Nov 27 18:31:13 BRDT 2000