Busca avançada
Ano de início
Entree
Conteúdo relacionado

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)

Matéria(s) publicada(s) na Agência FAPESP sobre o auxílio:
Mais itensMenos itens
Matéria(s) publicada(s) em Outras Mídias ( ):
Mais itensMenos itens
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)

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