Foundations of computer science: combinatory algorithms and discrete structures

• Grant number: 03/09925-5
• Support Opportunities: PRONEX Research - Thematic Grants
• Start date: July 01, 2004
• End date: March 31, 2008
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Agreement: CNPq - Pronex
• Principal Investigator: Yoshiharu Kohayakawa
• Grantee: Yoshiharu Kohayakawa
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
• City of the host institution: São Paulo
• Principal investigators: Carlos Eduardo Ferreira ; Cláudio Leonardo Lucchesi ; Sostenes Luiz Soares Lins ; Yoshiko Wakabayashi
• Associated research grant(s): 05/59048-6 - Bruce Alan Reed | McGill University - Canadá, AV.EXT
• Associated scholarship(s): 07/06864-6 - Analysis of heuristic algorithms for rich vehicle routing problems, BP.MS

Abstract

The research proposed in this project is focused on the development of efficient combinatory algorithms and the investigation of discrete structures of interest, with the global aim of supporting in a fundamental manner the Science of computing. The focus of this project is classic in nature. Of the many fronts of computer Science which seek to give support to computationally intense research projects in contemporary Science, this project is classified on the mathematical front, addressing algorithmic problems in a rigorous manner. The algorithms developed are analyzed from the point of view of correction, performance and complexity, through a theoretical analysis and, when appropriate, complemented by implementations. The principal sub-themes to be tackled are as follows: 1) diverse methods for the development of algorithms for problems of combinatory optimization; 2) combinatory problems in computational biology; 3) structural aspects of graphs and correlated objects; 4) assyntotic properties and combinatory structures.(AU)

Scientific publications

(37)

(The scientific publications listed on this page originate from the Web of Science or SciELO databases. Their authors have cited FAPESP grant or fellowship project numbers awarded to Principal Investigators or Fellowship Recipients, whether or not they are among the authors. This information is collected automatically and retrieved directly from those bibliometric databases.)

LEMOS, MANOEL; REID, TALMAGE JAMES; WU, HAIDONG. On the circuit-spectrum of binary matroids. EUROPEAN JOURNAL OF COMBINATORICS, v. 32, n. 6, SI, p. 861-869, AUG 2011. (03/09925-5)

GADI, MANOEL FERNANDO ALONSO; WANG, XIDI; DO LAGO, ALAIR PEREIRA; WANI, MA; CHEN, X; CASASENT, D; KURGAN, L; HU, T; HAFEEZ, K. Comparison with Parametric Optimization in Credit Card Fraud Detection. SEVENTH INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND APPLICATIONS, PROCEEDINGS, v. N/A, p. 2-pg., 2008-01-01. (03/09925-5)

LEMOS, MANOEL; REID, TALMAGE JAMES; WU, HAIDONG. On the circuit-spectrum of binary matroids. EUROPEAN JOURNAL OF COMBINATORICS, v. 32, n. 6, p. 9-pg., 2011-08-01. (03/09925-5)

HOSHINO, EDNA A.; DE SOUZA, CID C.; HU, XD; WANG, J. Column generation algorithms for the capacitated m-ring-star problem. Lecture Notes in Computer Science, v. 5092, p. 2-pg., 2008-01-01. (03/09925-5)

HAXELL‚ P.; LUCZAK‚ T.; PENG‚ Y.; RÖDL‚ V.; RUCINSKI‚ A.; SKOKAN‚ J.. The Ramsey number for 3-uniform tight hypergraph cycles. COMBINATORICS PROBABILITY & COMPUTING, v. 18, n. 1-2, p. 165-203, 2009. (03/09925-5)

LEMOS, MANOEL; MELO, T. R. B.. Connected hyperplanes in binary matroids. Linear Algebra and its Applications, v. 432, n. 1, p. 259-274, JAN 1 2010. (03/09925-5)

CORDOVIL, RAUL; MAIA, JR., BRAULIO; LEMOS, MANOEL. The 3-connected binary matroids with circumference 6 or 7. EUROPEAN JOURNAL OF COMBINATORICS, v. 30, n. 8, p. 1810-1824, NOV 2009. (03/09925-5)

CORREA, JOSE R.; FERNANDES, CRISTINA G.; WAKABAYASHI, YOSHIKO. Approximating a class of combinatorial problems with rational objective function. MATHEMATICAL PROGRAMMING, v. 124, n. 1-2, p. 255-269, JUL 2010. (03/09925-5)

LEMOS, MANOEL; REID, TALMAGE JAMES; WU, HAIDONG. Characterizing 3-Connected Planar Graphs and Graphic Matroids. JOURNAL OF GRAPH THEORY, v. 64, n. 2, p. 165-174, JUN 2010. (03/09925-5)

LEMOS, MANOEL. A characterization of graphic matroids using non-separating cocircuits. ADVANCES IN APPLIED MATHEMATICS, v. 42, n. 1, p. 75-81, JAN 2009. (03/09925-5)

CAVALCANTE‚ V.F.; DE SOUZA‚ C.C.; LUCENA‚ A.. A Relax-and-Cut algorithm for the set partitioning problem. Computers & Operations Research, v. 35, n. 6, p. 1963-1981, 2008. (03/09925-5)

RODRIGUES‚ E.M.; SAGOT‚ M.F.; WAKABAYASHI‚ Y.. The maximum agreement forest problem: Approximation algorithms and computational experiments. THEORETICAL COMPUTER SCIENCE, v. 374, n. 1, p. 91-110, 2007. (03/09925-5)

ADI‚ S.S.; BRAGA‚ M.D.V.; FERNANDES‚ C.G.; FERREIRA‚ C.E.; MARTINEZ‚ F.V.; SAGOT‚ M.F.; STEFANES‚ M.A.; TJANDRAATMADJA‚ C.; WAKABAYASHI‚ Y.. Repetition-free longest common subsequence. DISCRETE APPLIED MATHEMATICS, v. 158, n. 12, p. 1315-1324, 2010. (03/09925-5)

ALON‚ N.; KOHAYAKAWA‚ Y.; MAUDUIT‚ C.; MOREIRA‚ CG; RODL‚ V.. Measures of pseudorandomness for finite sequences: minimal values. COMBINATORICS PROBABILITY & COMPUTING, v. 15, n. 1/2, p. 1, 2006. (03/09925-5)

CHATAIGNER, F.; MANIC, G.; WAKABAYASHI, Y.; YUSTER, R.. Approximation algorithms and hardness results for the clique packing problem. DISCRETE APPLIED MATHEMATICS, v. 157, n. 7, p. 1396-1406, APR 6 2009. (06/01817-7, 03/09925-5)

CORDOVIL, RAUL; MAIA, JR., BRAULIO; LEMOSE, MANOEL. Removing circuits in 3-connected binary matroids. DISCRETE MATHEMATICS, v. 309, n. 4, p. 655-665, MAR 6 2009. (03/09925-5)

CARMO, RENATO; FEDER, TOMAS; KOHAYAKAWA, YOSHIHARU; LABER, EDUARDO; MOTWANI, RAJEEV; O'CALLAGHAN, LIADAN; PANIGRAHY, RINA; THOMAS, DILYS. Querying Priced Information in Databases: The Conjunctive Case. ACM TRANSACTIONS ON ALGORITHMS, v. 3, n. 1, SI, FEB 2007. (03/09925-5)

CAVALCANTE, VICTOR F.; DE SOUZA, CID C.; CHEN, B; PATERSON, M; ZHANG, G. Lagrangian relaxation and cutting planes for the vertex separator problem. Lecture Notes in Computer Science, v. 4614, p. 2-pg., 2007-01-01. (03/09925-5)

CARMO, RENATO; FEDER, TOMAS; KOHAYAKAWA, YOSHIHARU; LABER, EDUARDO; MOTWANI, RAJEEV; O'CALLAGHAN, LIADAN; PANIGRAHY, RINA; THOMAS, DILYS. Querying Priced Information in Databases: The Conjunctive Case. ACM TRANSACTIONS ON ALGORITHMS, v. 3, n. 1, p. 22-pg., 2007-02-01. (03/09925-5)

ZICH, J.; KOHAYAKAWA, Y.; RODL, V.; SUNDERAM, V.. JumpNet: Improving Connectivity and Robustness in Unstructured P2P Networks by Randomness. INTERNET MATHEMATICS, v. 5, n. 3, p. 24-pg., 2008-01-01. (03/09925-5)

CORREA, JOSE R.; FERNANDES, CRISTINA G.; MATAMALA, MARTIN; WAKABAYASHI, YOSHIKO; KAKLAMANIS, C; SKUTELLA, M. A 5/3-approximation for finding spanning trees with many leaves in cubic graphs. Lecture Notes in Computer Science, v. 4927, p. 3-pg., 2008-01-01. (03/09925-5)

HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; MOREIRA, CARLOS GUSTAVO; SAMPAIO, RUDINI MENEZES; SIAM/ACM. Property testing and parameter testing for permutations. PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, v. 135, p. 2-pg., 2010-01-01. (03/09925-5)

MARTINEZ‚ F.V.; DE PINA‚ J.C.; SOARES‚ J.. Algorithms for terminal Steiner trees. THEORETICAL COMPUTER SCIENCE, v. 389, n. 1, p. 133-142, 2007. (03/09925-5)

CORDOVIL, RAUL; LEMOS, MANOEL. The 3-connected matroids with circumference 6. DISCRETE MATHEMATICS, v. 310, n. 8, p. 1354-1365, APR 28 2010. (03/09925-5)

KAWARABAYASHI, KEN-ICHI; LEE, ORLANDO; REED, BRUCE; WOLLAN, PAUL. A weaker version of Lovasz' path removal conjecture. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 98, n. 5, p. 972-979, SEP 2008. (03/09925-5)

KOHAYAKAWA, YOSHIHARU; ROEDL, VOJTECH; SCHACHT, MATHIAS; SZEMEREDI, ENDRE. Sparse partition universal graphs for graphs of bounded degree. ADVANCES IN MATHEMATICS, v. 226, n. 6, p. 5041-5065, APR 1 2011. (03/09925-5)

FERNANDES, CRISTINA G.; LEE, ORLANDO; WAKABAYASHI, YOSHIKO. Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width. DISCRETE APPLIED MATHEMATICS, v. 157, n. 2, p. 272-279, JAN 28 2009. (03/09925-5)

DELLAMONICA, JR., DOMINGOS; KOHAYAKAWA, YOSHIHARU; ROEDL, VOJTECH; RUCINSKI, ANDRZEJ. UNIVERSALITY OF RANDOM GRAPHS. SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 26, n. 1, p. 353-374, 2012. (03/09925-5)

KOHAYAKAWA, YOSHIHARU; NAGLE, BRENDAN; RODL, VOJTECH; SCHACHT, MATHIAS. Weak hypergraph regularity and linear hypergraphs. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 100, n. 2, p. 151-160, MAR 2010. (03/09925-5)

BENEVIDES, FABRICIO SIQUEIRA; SKOKAN, JOZEF. The 3-colored Ramsey number of even cycles. JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 99, n. 4, p. 690-708, JUL 2009. (03/09925-5)

XAVIER‚ E.C.; MIYAZAWA‚ F.K.. The class constrained bin packing problem with applications to video-on-demand. THEORETICAL COMPUTER SCIENCE, v. 393, n. 1, p. 240-259, 2008. (03/09925-5)

KIM‚ S.J.; NAKPRASIT‚ K.; PELSMAJER‚ M.J.; SKOKAN‚ J.. Transversal numbers of translates of a convex body. DISCRETE MATHEMATICS, v. 306, n. 18, p. 2166-2173, 2006. (03/09925-5)

LEMOS‚ M.; MELO‚ TRB. Non-separating cocircuits in matroids. DISCRETE APPLIED MATHEMATICS, v. 156, n. 7, p. 1019-1024, 2008. (03/09925-5)

MIYAZAWA‚ FK; WAKABAYASHI‚ Y.. Two-and three-dimensional parametric packing. Computers & Operations Research, v. 34, n. 9, p. 2589-2603, 2007. (03/09925-5)

XAVIER‚ EC; MIYAZAWA‚ FK. Approximation schemes for knapsack problems with shelf divisions. THEORETICAL COMPUTER SCIENCE, v. 352, n. 1, p. 71-84, 2006. (03/09925-5)

XAVIER‚ EC; MIYAZAWA‚ F.K.. A one-dimensional bin packing problem with shelf divisions. DISCRETE APPLIED MATHEMATICS, v. 156, n. 7, p. 1083-1096, 2008. (03/09925-5)

MARCINISZYN‚ M.; SKOKAN‚ J.; SPÖHEL‚ R.; STEGER‚ A.. Asymmetric Ramsey properties of random graphs involving cliques. RANDOM STRUCTURES & ALGORITHMS, v. 34, n. 4, p. 419-453, 2009. (03/09925-5)