Advanced search
Start date
Betweenand
Related content

Foundations of computer science: combinatory algorithms and discrete structures

Grant number: 03/09925-5
Support Opportunities:PRONEX Research - Thematic Grants
Duration: July 01, 2004 - March 31, 2008
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Convênio/Acordo: 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
Pesquisadores principais:
Carlos Eduardo Ferreira ; Cláudio Leonardo Lucchesi ; Sostenes Luiz Soares Lins ; Yoshiko Wakabayashi
Associated 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)

Articles published in Agência FAPESP Newsletter about the research grant:
More itemsLess items
Articles published in other media outlets ( ):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

Scientific publications (37)
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
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, . (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, . (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, . (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, . (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, . (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, . (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, . (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, . (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, . (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, . (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, . (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, . (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, . (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., . (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., . (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., . (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, . (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, . (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, . (03/09925-5)
CORDOVIL, RAUL; LEMOS, MANOEL. The 3-connected matroids with circumference 6. DISCRETE MATHEMATICS, v. 310, n. 8, p. 1354-1365, . (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, . (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, . (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, . (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, . (03/09925-5)
LEMOS‚ M.; MELO‚ TRB. Non-separating cocircuits in matroids. DISCRETE APPLIED MATHEMATICS, v. 156, n. 7, p. 1019-1024, . (03/09925-5)
MIYAZAWA‚ FK; WAKABAYASHI‚ Y.. Two-and three-dimensional parametric packing. Computers & Operations Research, v. 34, n. 9, p. 2589-2603, . (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, . (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, . (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, . (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, . (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, . (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, . (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., . (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., . (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., . (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., . (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., . (03/09925-5)

Please report errors in scientific publications list using this form.
X

Report errors in this page


Error details: