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

• Processo: 03/09925-5
• Modalidade de apoio: Auxílio à Pesquisa - Programa PRONEX - Temático
• Data de Início da vigência: 01 de julho de 2004
• Data de Término da vigência: 31 de março de 2008
• Área do conhecimento: Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
• Acordo de Cooperação: 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ílio(s) vinculado(s): 05/59048-6 - Bruce Alan Reed | McGill University - Canadá, AV.EXT
• Bolsa(s) vinculada(s): 07/57149-5 - Abordagens exatas e aproximacoes para o problema da subsequencia comum mais londa sem repeticoes e variantes., BP.MS; 07/06864-6 - Análise de algoritmos heurísticos para problemas ricos de roteamento de veículos, BP.MS; 07/54282-6 - Subseqüência comum mais longa sem repetições e variantes, BP.IC; + mais bolsas vinculadas 06/60177-8 - Aspectos teoricos, estruturais e de otimizacao de alguns problemas em grafos., BP.PD; 06/58578-4 - Avancos na area de regularidade de grafos e hipergrafos., BP.MS; 06/53152-9 - Problemas extremais para grafos aleatorios., 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 - Algoritimos de aproximacao, complexidade e nao-aproximabilidade de problemas em grafos., BP.PD; 04/15397-4 - Aplicacoes de quase-aleatoriedade em combinatoria., BP.PD; 04/11338-3 - Relacoes min-max em otimizacao combinatoria., BP.MS; 04/11501-1 - Pseudoaleatoriedade em combinatoria e em teoria da computacao., BP.MS; 04/07367-8 - Algoritimos combinatorios, otimizacao e teoria dos grafos., BP.IC - menos bolsas vinculadas
• Assunto(s): Biologia computacional Algoritmos Otimização combinatória Probabilidade Teoria dos grafos
• Palavra(s)-Chave do Pesquisador: Algoritmos | Biologia Computacional | Complexidade | Metodos Probabilisticos | Otimizacao Combinatoria | 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

(37)

(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)

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)

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. (05/53840-0, 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)

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, 04/14335-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, 04/14335-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)

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)

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; 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)

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. (04/15397-4, 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)

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)

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)

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)

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)

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. (05/52494-0, 04/15397-4, 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)

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)

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, 04/15397-4)

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, 04/15397-4)

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)

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)

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)

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. (04/14335-5, 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. (07/56496-3, 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)