Publications

• S. Adi, M.D.V. Braga, C.G. Fernandes, C.E. Ferreira, F.H.V. Martinez, M.-F Sagot, M.A. Stefanes, C. Tjandraatmadja and Y. Wakabayashi, Repetition-free longest common subsequence, Discrete Appl. Math., in press - available online DOI:http://dx.doi.org/10.1016/j.dam.2009.04.023 [pdf] [LAGOS 2007 - Extended abstract: Electronic Notes in Discrete Mathematics 30 (2008) 243-248.]

• F. K. Miyazawa and Y. Wakabayashi, Three-dimensional packings with rotations, Computers and Operations Research, vol. 36, Issue 10, 2801--2815, 2009. DOI:http://dx.doi.org/10.1016/j.cor.2008.12.015

• G. Manic and Y. Wakabayashi, Packing triangles in low degree graphs and indifference graphs, Discrete Mathematics, vol. 308 (2008), Issue 8, 1455-1471; DOI:http://dx.doi.org/10.1016/j.disc.2007.07.100: [pdf]

• C.G. Fernandes, C.E. Ferreira, C. Tjandraatmadja, and Y. Wakabayashi, A polyhedral investigation of the LCS problem and a repetition-free variant, In: 8th Latin American Theoretical Informatics Symposium (LATIN), Buzios, 2008, Lecture Notes in Computer Science , v. 4957. E.S. Laber et al. (Eds.): pp. 329-338, 2008. ISBN: 978-3-540-78772-3. DOI:http://dx.doi.org/10.1007/978-3-540-78773. Springerlink [pdf file]

• J.R. Correa, C.G. Fernandes, M. Matamala and Y. Wakabayashi, A 5/3-approximation for finding spanning trees with many leaves in cubic graphs, WAOA 2007 (5th Workshop on Approximation and Online Algorithms), Lecture Notes in Computer Science, v. 4927 (2008), p. 184-192. DOI:http://dx.doi.org/10.1007/978-3-540-77918-6_15 [pdf]

• F. Chataigner, G. Manic, Y.Wakabayashi and R. Yuster, Approximation algorithms and hardness results for the clique packing problem, Discrete Appl. Math. DOI:http://dx.doi.org/10.1016/j.dam.2008.10.017. [pdf] [Extended abstract: Eurocomb 2007- Electronic Notes in Discrete Mathematics Volume 29, Pages 397-401 URL of ENDM http://www.sciencedirect.com/science/journal/1571065.]

• F. Chataigner, L.R.B. Salgado and Y.Wakabayashi, Approximation and inaproximability results on balanced connected partitions of graphs, DMTCS (Discrete Mathematics & Theoretical Computer Science), vol. 9, 2007, 177-192. DMTCS-vol.9, 2007

• J.R. Correa, C.G. Fernandes and Y. Wakabayashi, Approximating a class of combinatorial problems with rational objective function, 2006, submitted.

• G.F. Cintra, F.K. Miyazawa, Y. Wakabayashi and E.C. Xavier, Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation, European Journal of Operational Research, Volume 191, Issue 1 (2008), 59--83; DOI:http://dx.doi.org/10.1016/j.ejor.2007.08.007.

• G.F. Cintra, F.K. Miyazawa, Y. Wakabayashi and E.C. Xavier, A note on the approximability of cutting stock problems, European Journal of Operational Research, Volume 183, Issue 3 (2007), Pages 1328-1332; DOI:http://dx.doi.org/10.1016/j.ejor.2005.09.053

• E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, The maximum agreement forest problem: approximation algorithms and computational experiments, Theoretical Computer Science 374 (2007) 91--110; DOI: http://dx.doi.org/doi:10.1016/j.tcs.2006.12.011

• F.K. Miyazawa and Y. Wakabayashi, Two- and three-dimensional parametric packing, Computers and Operations Research, Vol. 34, Issue 9, 2589-2603, 2007;DOI: http://dx.doi.org/10.1016/j.cor.2005.10.001

• J.R. Correa, C.G. Fernandes and Y. Wakabayashi, Approximating rational objectives is as easy as approximating linear ones, SWAT (10th Scandinavian Workshop on Algorithm Theory), Riga, July 2006, Lecture Notes in Computer Science, vol. 4059 (2006), pp. 351--362; DOI: http://dx.doi.org/10.1007/11785293_33

• G. Manic and Y. Wakabayashi, Packing triangles in low degree graphs and indifference graphs, EuroComb 2005 (European Conference on Combinatorics, Graph Theory and Applications). Discrete Mathematics and Theoretical Computer Science (DMTCS), Vol. AE 2005, pp. 251--256 (extended abstract).

• F.K. Miyazawa and Y. Wakabayashi, Two- and three-dimensional parametric packing. Proceedings of GRACO2005, 313--319 (electronic), Electron. Notes Discrete Math., 19, Elsevier, Amsterdam, 2005 (extended abstract). ENDM-vol.19-GRACO 2005

• C.G. Fernandes, O. Lee and Y. Wakabayashi, The minimum cycle cover and the Chinese postman problems on mixed graphs with bounded tree-width, Discrete Appl. Math., to appear. DOI: http://dx.doi.org/10.1016/j.dam.2007.10.032 [pdf]

• L.R.B. Salgado and Y. Wakabayashi, Approximation results on balanced connected partitions of graphs, Proceedings of the Latin-American Conference on Combinatorics, Graphs and Applications, Santiago, Chile, 16--20 August, 2004, Extended abstract. Electronic Notes in Discrete Mathematics 18 (2004) 207-212.

• Y. Kohayakawa, F.K. Miyazawa, P. Raghavan, Y. Wakabayashi, Multidimensional cube packing, Algorithmica, 40(3): 173--187, 2004. [ps.gz | pdf.gz] -- (submitted version -- different from the revised version), DOI: http://dx.doi.org/10.1007/s00453-004-1102-5.

• 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.

• F.K. Miyazawa and Y. Wakabayashi, Packing problems with orthogonal rotations. Proceedings of LATIN 2004: Theoretical Informatics. M. Farach-Colton (Ed.) Lecture Notes in Computer Science, vol. 2976 (2004), pp. 359--368. Buenos Aires, Argentina, April 5--8, 2004.

• F.K. Miyazawa and Y. Wakabayashi, Parametric on-line approximation algorithms for packing squares and boxes, European Journal of Operational Research, 150 (2003) 281-292.

• F.K. Miyazawa and Y. Wakabayashi, Cube packing, Theoretical Computer Science, 297 (2003) 1-3, 355--366.

• O. Lee and Y. Wakabayashi, On the circuit cover problem for mixed graphs, Combinatorics, Probability and Computing (2002) 11, 43--59. [ps.gz] [pdf.gz]

• C.E. Ferreira and C.C. Souza and Y. Wakabayashi, Rearrangement of DNA fragments: a branch-and-cut algorithm, Discrete Applied Mathematics 116 (2002), no. 1-2, 161--177.

• O. Lee and Y. Wakabayashi, Note on a min-max conjecture of Woodall, Journal of Graph Theory, 38 (2001), no. 1, 36-41 [ps.gz]

• M.-F. Sagot and Y. Wakabayashi, Pattern Inference under many Guises, chapter of Recent Advances in Algorithms and Combinatorics, 245-287, Springer-Verlag, New York, 2003. (ISBN: 0387954341 - 368 pages - http://www.springer.de/search97cgi/s97_cgi) Mini-course of CIMPA School on Algorithms and Combinatorics, 12-16 and 21-24 of March, 2001, Fortaleza, Ceará, Brazil.

• E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, Some approximation results for the maximum agreement forest problem. Proceedings of APPROX-RANDOM 2001 (Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques), M. Goemans et al (Eds.), Lecture Notes in Computer Science, vol. 2129, Springer (2001), 159-169. DOI 10.1007/3-540-44666-4 full paper ATTENTION: The algorithm shown is for the maximum agreement forest (maf) problem (see how this problem is defined in this paper). WE DO NOT CLAIM the algorithm is for the problem of calculating rSPR or TBR distance between two trees. The relation between the maf problem and these other problems have been mentioned by other authors. Some authors state that our algorithm has been proposed for TBR or rSPR and it has some flaws in the sense that it is not a 3-approx for these problems. All we say in the paper is that we present a 3-approx for the maf problem (as defined in the paper). A full paper containing the results of this paper and other new results, implementations, comparisons, etc is mentioned above is the following: E.M. Rodrigues, M.-F. Sagot and Y. Wakabayashi, The maximum agreement forest problem: approximation algorithms and computational experiments, Theoretical Computer Science 374 (2007) 91--110; DOI: http://dx.doi.org/doi:10.1016/j.tcs.2006.12.011 Please contact one of the authors if you would like to have a copy of these papers or if you have any question concerning these results.

• M.R. Cerioli, P. Feofiloff, C.G. Fernandes, F.K. Miyazawa (eds.) Uma Introdução Sucinta a Algoritmos de Aproximação, livro do Colóquio Brasileiro de Matemática, 2001.

• F.K. Miyazawa and Y. Wakabayashi, Cube Packing. Proceedings of LATIN'2000: Theoretical Informatics (Punta del Este, Uruguay. April, 2000), Lecture Notes in Computer Science, vol. 1776 (2000), 58-67.

• F.K. Miyazawa and Y. Wakabayashi, Approximation Algorithms for the Orthogonal z-oriented 3-D Packing Problem, SIAM Journal on Computing, 29(3) (2000) 1008-1029 [ps.gz | pdf.gz]

• C.E. Ferreira and F.K. Miyazawa and Y. Wakabayashi, Packing Squares into Squares, Pesquisa Operacional, 19 (1999), No.2, 223-237. [ps.gz]

• O. Lee and Y. Wakabayashi, Circuit Covers in Series-Parallel Mixed Graphs, Proceedings of LATIN'98: Theoretical Informatics. Lecture Notes in Computer Science, vol. 1380 (1998), 226-238 [ LNCSv.1380] [ps.gz]

• Y. Wakabayashi, The Complexity of Computing Medians of Relations. Resenhas, 3 (3) (1998), 323-349 [ps] [pdf]

• C.E. Ferreira and Y. Wakabayashi, Planos-de-corte Faciais e a Resolução de Problemas de Otimização Combinatória -- texto para o I Encontro de Matemática Aplicada e Computacional, ERMAC, 1998.

• M.A.C.M. Gurgel and Y. Wakabayashi, Adjacency of Vertices of the Complete Pre-order Polytope, Discrete Mathematics 175 (1997), no. 1-3, 163-172 [ps.gz]

• F.K. Miyazawa and Y. Wakabayashi, An Algorithm for the Three-dimensional Packing Problem with Asymptotic Performance Analysis, Algorithmica 18 (1997), no. 1, 122-144 [preliminary version ps.gz]

• C.E. Ferreira and Y. Wakabayashi, Combinatória Poliédrica e Planos-de-Corte Faciais , livro para a X Escola de Computação, UNICAMP, julho de 1996. Livro todo [ps.gz | pdf]

• M. Grötschel and Y. Wakabayashi, Facets of the Clique Partitioning Polytope, Mathematical Programming A, 47 (1990) 367-387. DOI Number: 10.1007/BF01580870 [pdf]

• M. Grötschel and Y. Wakabayashi, Composition of Facets of the Clique Partitioning Polytope, in: Topics in Combinatorics and Graph Theory , R. Bodendieck, R. Henn (eds.), Physica-Verlag, Heidelberg (1990), 271-284.

• Y. Wakabayashi, Adjacency of Vertices on the Clique Partitioning Polytope, SCIENTIA, Series A : Mathematical Sciences Vol. 3 (1989), 111-119 - Univ. Técnica Federico Santa Maria, Valparaíso, Chile.

• M. Grötschel and Y. Wakabayashi, A Cutting Plane Algorithm for a Clustering Problem, Mathematical Programming B, 45 (1989) 52-96. DOI Number: 10.1007/BF01589097 [pdf]

• M.A.C.M. Gurgel and Y. Wakabayashi, On k-leaf-connected Graphs, Journal of Combinatorial Theory, Series B, 41 (1986) 1-16.

• M.A.C.M. Gurgel and Y. Wakabayashi, Embedding of Trees, in: Mathematical Programming, R.W. Cottle et al (eds.), North-Holland, Amsterdam, 1984, pp. 177-184.

• M. Grötschel and Y. Wakabayashi, Constructions of Hypotraceable Digraphs, in: Mathematical Programming, R.W. Cottle et al (eds.), North-Holland, Amsterdam, 1984, pp. 147-175.

• M. Grötschel and Y. Wakabayashi, On the Structure of the Monotone Asymmetric Travelling Salesman Polytope I: Hypohamiltonian Facets, Discrete Mathematics 34 (1981) 43-59.

• M. Grötschel and Y. Wakabayashi, On the Structure of the Monotone Asymmetric Travelling Salesman Polytope II: Hypotraceable Facets, Mathematical Programming Study 14(1981) 77-97.

• M. Grötschel and Y. Wakabayashi, Hypohamiltonian Digraphs, Methods of Operations Research 36 (1980) 99-119.

• M. Grötschel, C. Thomassen and Y. Wakabayashi, Hypotraceable Digraphs, Journal of Graph Theory 4 (1980) 377-381.

Other Publications

• Feofiloff, P; De Figueiredo, C.M.H.; Wakabayashi, Y. Preface, Special issue: 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics GRACO 2005, editors of Discrete Applied Mathematics, Vol. 156, Issue 7 (2008), page 985.

• Choffrut, Christian and Wakabayashi, Yoshiko, Preface [Imre Simon, the tropical computer scientist]. Editors of the special volume: Theor. Inform. Appl. 39 (2005), no. 1, i--vii.

• Proceedings of GRACO2005. Papers from the 2nd Brazilian Symposium on Graphs, Algorithms, and Combinatorics held in Angra dos Reis, April 27--29, 2005. Edited by Paulo Feofiloff, Celina M. H. de Figueiredo and Yoshiko Wakabayashi. Electronic Notes in Discrete Mathematics, 19. Elsevier Science B.V., Amsterdam, 2005. front matter+416 pp. (electronic).

• Y. Kohayakawa, F.K. Miyazawa, P. Raghavan and Y. Wakabayashi. Multidimensional Cube Packing, Szwarcfiter, Jayme (ed.), Proceedings of the Brazilian symposium on graphs, algorithms and combinatorics, Fortaleza, Ceará, Brazil, March 17-19, 2001. Extended abstracts. Amsterdam: Elsevier, Electron. Notes in Discrete Mathematics 7, no pag., electronic only (2001).

• G.F. Cintra and Y. Wakabayashi, Um Algoritmo Híbrido para o Problema de Corte Unidimensional, Anais do XXX Simpósio Brasileiro de Pesquisa Operacional, 1998, 19pp.[ps.gz | pdf.gz]

• F.K. Miyazawa and Y. Wakabayashi, Parametric on-line packing, XXX SOBRAPO-Simpósio Brasileiro de Pesquisa Operacional, Curitiba, 1998. Anais da III Oficina de Problemas de Corte e Empacotamento, 109-121 [ps.gz]

• F.K. Miyazawa and Y. Wakabayashi. Approximation algorithms for packing small items. In XX Congresso Nacional de Matemática Aplicada e Computacional , 1997.

• Y. Wakabayashi, Contribuições a Teoria dos Grafos e Otimização Combinatória. Monografia apresentada no concurso de livre-docência - USP, 1995.

• O. Lee and Y. Wakakabayashi, Caminhos Mínimos em Grafos Mistos, Anais do XVIII Congresso de Matemática Aplicada e Computacional, 1995, 329-333.

• Y. Wakabayashi, Aggregation of Binary Relations: Algorithmic and Polyhedral Investigations, Thesis, Universität Augsburg, Germany, 1986.

• M.A.C.M. Gurgel and Y. Wakabayashi, A Result on Hamilton-connected Graphs, Tech. Report 83309-OR, Institut für Operations Research, Universität Bonn, 1983.

• Y. Wakabayashi, Sobre Grafos Hamiltonianos, dissertação de mestrado, Instituto de Matemática e Estatística da Universidade de São Paulo. 1977.