Fundamentos da ciência da computação: algoritmos combinatórios e estruturas discretas

• Processo: 03/09925-5
• Linha de fomento: Auxílio à Pesquisa - Programa PRONEX - Temático
• Vigência: 01 de julho de 2004 - 31 de março de 2008
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Convênio/Acordo: CNPq - Pronex
• Pesquisador responsável: Yoshiharu Kohayakawa
• Beneficiário: Yoshiharu Kohayakawa
• Instituição-sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
• Pesquisadores principais: Carlos Eduardo Ferreira ; Cláudio Leonardo Lucchesi ; Sostenes Luiz Soares Lins ; Yoshiko Wakabayashi
• Auxílios(s) vinculado(s): 05/59048-6 - Bruce alan Reed | McGill university - Canadá, AV.EXT
• Bolsa(s) vinculada(s): 07/06864-6 - Análise de algoritmos heurísticos para problemas ``ricos'' de roteamento de veículos, BP.MS; 07/57149-5 - Abordagens exatas e aproximações para o problema da subsequência comum mais londa sem repetições e variantes, BP.MS; 07/54282-6 - Subseqüência comum mais longa sem repetições e variantes, BP.IC; + mais bolsas vinculadas 06/60177-8 - Aspectos teóricos, estruturais e de otimização de alguns problemas em grafos, BP.PD; 06/58578-4 - Avanços na área de regularidade de grafos e hipergrafos, BP.MS; 06/53152-9 - Problemas extremais para grafos aleatórios, BP.MS; 05/60504-6 - Entropia de grafos, BP.IC; 05/54051-9 - Problemas finitos e infinitos da teoria dos grafos e hipergrafos, BP.PD; 05/52494-0 - Problemas estruturais e numéricos na Teoria de Ramsey para grafos, BP.MS; 05/53840-0 - Algorítimos de aproximação, complexidade e não-aproximabilidade de problemas em grafos, BP.PD; 04/15397-4 - Aplicações de quase-aleatoriedade em combinatória, BP.PD; 04/11338-3 - Relações min-max em otimização combinatória, BP.MS; 04/11501-1 - Pseudoaleatoriedade em combinatória e em teoria da computação, BP.MS; 04/07367-8 - Algorítimos combinatórios, otimização e teoria dos grafos, BP.IC - menos bolsas vinculadas
• Assunto(s): Biologia computacional Algoritmos Otimização combinatória Probabilidade Teoria dos grafos

Resumo

A pesquisa proposta neste projeto tem como foco o desenvolvimento de algoritmos combinatórios eficientes e a investigação de estruturas discretas de interesse intrínseco, com o objetivo global de dar suporte de caráter fundamental à Ciência da computação. O enfoque deste projeto é de natureza clássica. Das múltiplas frentes da Ciência da computação que procuram dar suporte a projetos de pesquisa computacionalmente intensos da Ciência contemporânea, este projeto se classifica na frente matemática, atacando problemas algorítmicos de forma rigorosa. Os algoritmos desenvolvidos são analisados do ponto de vista de correção, desempenho e complexidade, através de uma análise teórica e, quando adequado, complementada por implementações. São os seguintes os principais subtemas a serem abordados: 1) métodos diversos para o desenvolvimento de algoritmos para problemas de otimização combinatória; 2) problemas combinatórios em biologia computacional; 3) aspectos estruturais de grafos e objetos correlatos; 4) propriedades assintóticas de estruturas combinatórias. (AU)

Publicações científicas

(29)

(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)

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. Citações Web of Science: 8.

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. Citações Web of Science: 1.

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. Citações Web of Science: 17.

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. Citações Web of Science: 7.

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. Citações Web of Science: 4.

CORDOVIL, RAUL; LEMOS, MANOEL. The 3-connected matroids with circumference 6. DISCRETE MATHEMATICS, v. 310, n. 8, p. 1354-1365, APR 28 2010. Citações Web of Science: 0.

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. Citações Web of Science: 24.

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. Citações Web of Science: 2.

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.

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. Citações Web of Science: 4.

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. Citações Web of Science: 23.

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. Citações Web of Science: 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. Citações Web of Science: 1.

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. Citações Web of Science: 7.

LEMOS, MANOEL. A characterization of graphic matroids using non-separating cocircuits. ADVANCES IN APPLIED MATHEMATICS, v. 42, n. 1, p. 75-81, JAN 2009. Citações Web of Science: 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.

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.

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. Citações Web of Science: 7.

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.

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

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.

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.

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. Citações Web of Science: 0.

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.

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

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.

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.

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.

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