Busca avançada
Ano de início
Entree
Conteúdos relacionados

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
Município da Instituição Sede:São Paulo
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 - Subsequencia comum mais longa sem repeticoes 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)
(As publicações científicas contidas nesta página são originárias da Web of Science ou da SciELO, cujos autores mencionaram números dos processos FAPESP concedidos a Pesquisadores Responsáveis e Beneficiários, sejam ou não autores das publicações. Sua coleta é automática e realizada diretamente naquelas bases bibliométricas)
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)
HAXELL‚ P.; LUCZAK‚ T.; PENG‚ Y.; RÖDL‚ V.; RUCINSKI‚ A.; SKOKAN‚ J.. . COMBINATORICS PROBABILITY & COMPUTING, v. 18, n. 1-2, p. 165-203, . (04/15397-4, 03/09925-5)
LEMOS, MANOEL; MELO, T. R. B.. . Linear Algebra and its Applications, v. 432, n. 1, p. 259-274, . (03/09925-5)
CORDOVIL, RAUL; MAIA, JR., BRAULIO; LEMOS, MANOEL. . EUROPEAN JOURNAL OF COMBINATORICS, v. 30, n. 8, p. 1810-1824, . (03/09925-5)
CORREA, JOSE R.; FERNANDES, CRISTINA G.; WAKABAYASHI, YOSHIKO. . MATHEMATICAL PROGRAMMING, v. 124, n. 1-2, p. 255-269, . (03/09925-5)
LEMOS, MANOEL; REID, TALMAGE JAMES; WU, HAIDONG. . JOURNAL OF GRAPH THEORY, v. 64, n. 2, p. 165-174, . (03/09925-5)
LEMOS, MANOEL. . ADVANCES IN APPLIED MATHEMATICS, v. 42, n. 1, p. 75-81, . (03/09925-5)
CHATAIGNER, F.; MANIC, G.; WAKABAYASHI, Y.; YUSTER, R.. . 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. . DISCRETE MATHEMATICS, v. 309, n. 4, p. 655-665, . (03/09925-5)
CAVALCANTE‚ V.F.; DE SOUZA‚ C.C.; LUCENA‚ A.. . Computers & Operations Research, v. 35, n. 6, p. 1963-1981, . (03/09925-5)
RODRIGUES‚ E.M.; SAGOT‚ M.F.; WAKABAYASHI‚ Y.. . 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.. . 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.. . COMBINATORICS PROBABILITY & COMPUTING, v. 15, n. 1/2, p. 1, . (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. . SEVENTH INTERNATIONAL CONFERENCE ON MACHINE LEARNING AND APPLICATIONS, PROCEEDINGS, v. N/A, p. 2-pg., . (03/09925-5)
LEMOS, MANOEL; REID, TALMAGE JAMES; WU, HAIDONG. . EUROPEAN JOURNAL OF COMBINATORICS, v. 32, n. 6, p. 9-pg., . (03/09925-5)
HOSHINO, EDNA A.; DE SOUZA, CID C.; HU, XD; WANG, J. . Lecture Notes in Computer Science, v. 5092, 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)
DELLAMONICA, JR., DOMINGOS; KOHAYAKAWA, YOSHIHARU; ROEDL, VOJTECH; RUCINSKI, ANDRZEJ. . SIAM JOURNAL ON DISCRETE MATHEMATICS, v. 26, n. 1, p. 353-374, . (03/09925-5)
CORDOVIL, RAUL; LEMOS, MANOEL. . DISCRETE MATHEMATICS, v. 310, n. 8, p. 1354-1365, . (03/09925-5)
BENEVIDES, FABRICIO SIQUEIRA; SKOKAN, JOZEF. . JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 99, n. 4, p. 690-708, . (05/52494-0, 04/15397-4, 03/09925-5)
XAVIER‚ E.C.; MIYAZAWA‚ F.K.. . THEORETICAL COMPUTER SCIENCE, v. 393, n. 1, p. 240-259, . (03/09925-5)
KIM‚ S.J.; NAKPRASIT‚ K.; PELSMAJER‚ M.J.; SKOKAN‚ J.. . DISCRETE MATHEMATICS, v. 306, n. 18, p. 2166-2173, . (03/09925-5, 04/15397-4)
LEMOS‚ M.; MELO‚ TRB. . DISCRETE APPLIED MATHEMATICS, v. 156, n. 7, p. 1019-1024, . (03/09925-5)
MIYAZAWA‚ FK; WAKABAYASHI‚ Y.. . Computers & Operations Research, v. 34, n. 9, p. 2589-2603, . (03/09925-5)
XAVIER‚ EC; MIYAZAWA‚ FK. . THEORETICAL COMPUTER SCIENCE, v. 352, n. 1, p. 71-84, . (03/09925-5)
XAVIER‚ EC; MIYAZAWA‚ F.K.. . DISCRETE APPLIED MATHEMATICS, v. 156, n. 7, p. 1083-1096, . (03/09925-5)
MARCINISZYN‚ M.; SKOKAN‚ J.; SPÖHEL‚ R.; STEGER‚ A.. . RANDOM STRUCTURES & ALGORITHMS, v. 34, n. 4, p. 419-453, . (03/09925-5, 04/15397-4)
KAWARABAYASHI, KEN-ICHI; LEE, ORLANDO; REED, BRUCE; WOLLAN, PAUL. . JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 98, n. 5, p. 972-979, . (03/09925-5)
KOHAYAKAWA, YOSHIHARU; ROEDL, VOJTECH; SCHACHT, MATHIAS; SZEMEREDI, ENDRE. . ADVANCES IN MATHEMATICS, v. 226, n. 6, p. 5041-5065, . (03/09925-5)
FERNANDES, CRISTINA G.; LEE, ORLANDO; WAKABAYASHI, YOSHIKO. . DISCRETE APPLIED MATHEMATICS, v. 157, n. 2, p. 272-279, . (03/09925-5)
KOHAYAKAWA, YOSHIHARU; NAGLE, BRENDAN; RODL, VOJTECH; SCHACHT, MATHIAS. . JOURNAL OF COMBINATORIAL THEORY SERIES B, v. 100, n. 2, p. 151-160, . (03/09925-5)
MARTINEZ‚ F.V.; DE PINA‚ J.C.; SOARES‚ J.. . THEORETICAL COMPUTER SCIENCE, v. 389, n. 1, p. 133-142, . (04/14335-5, 03/09925-5)
CAVALCANTE, VICTOR F.; DE SOUZA, CID C.; CHEN, B; PATERSON, M; ZHANG, G. . 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. . ACM TRANSACTIONS ON ALGORITHMS, v. 3, n. 1, p. 22-pg., . (03/09925-5)
ZICH, J.; KOHAYAKAWA, Y.; RODL, V.; SUNDERAM, V.. . 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. . Lecture Notes in Computer Science, v. 4927, p. 3-pg., . (03/09925-5)
HOPPEN, CARLOS; KOHAYAKAWA, YOSHIHARU; MOREIRA, CARLOS GUSTAVO; SAMPAIO, RUDINI MENEZES; SIAM/ACM. . PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, v. 135, p. 2-pg., . (07/56496-3, 03/09925-5)