Busca avançada
Ano de início
Entree

Aspectos estruturais e algorítmicos de objetos combinatórios

Processo: 96/04505-2
Linha de fomento:Auxílio à Pesquisa - Temático
Vigência: 01 de outubro de 1996 - 30 de setembro de 2000
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
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
Auxílios(s) vinculado(s):97/14469-6 - Robin Thomas | Georgia Institute of Technology - Estados Unidos, AV.EXT
97/06472-7 - 1) circuit covers in series parallel mixed graphs. 2) approximation algorithms for packing problems with orthogonal rotations, AR.EXT
96/12111-4 - Bruce Reed | Centre National de la Recherche Scientifique - França, AV.EXT
97/01873-3 - Szemeridi's regularity lemma for sparse graphs, AR.BR
96/12820-5 - 1) approximation algorithms for 3-D packing problems. 2) szemeredi's regulanity lemma for sparse grapys, AR.BR
Bolsa(s) vinculada(s):00/03969-2 - Análise experimental de algoritmos para teste de planaridade, BP.MS
98/16274-0 - Problemas dinâmicos em geometria computacional, BP.MS
98/16273-4 - Problemas cinéticos em geometria computacional, BP.MS
+ mais bolsas vinculadas 98/02407-9 - Aproximabilidade de problemas de otimização em grafos, BP.DR
97/09522-5 - Geometria computacional: algoritmos e implementações, BP.IC
97/09521-9 - Geometria computacional: algoritmos e implementações, BP.IC - menos bolsas vinculadas
Assunto(s):Algoritmos  Combinatória  Poliedros 

Resumo

O objeto central da pesquisa proposta neste projeto temático é investigar aspectos estruturais de objetos combinatórios. Os aspectos específicos a serem abordados serão aqueles motivados por (i) seu interesse intrínseco, vistos como tópicos da matemática pura, e pela (ii) sua importância para o desenvolvimento de algoritmos eficientes para problemas computacionais combinatórios específicos ou para a identificação da complexidade computacional de tais problemas. Principais subtemas a serem abordados neste projeto: 1. propriedades assintóticas de estruturas combinatórias, investigadas através de métodos combinatórios e extra-combinatórios, como métodos probabilísticos, algébricos, e topológicos; 2. propriedades estruturais de grafos, hipergrafos, e estruturas correlatas; 3. métodos e problemas geométricos em combinatória, com especial ênfase em métodos poliédricos em otimização combinatória. Uma lista de tópicos específicos de pesquisa, que não esgotam mas ilustram os nossos interesses, é a seguinte: problemas numéricos em teoria de Ramsey, problemas extremais tipo Turán, enumeração assintótica de grafos, objetos pseudo-aleatórios e suas aplicações, métodos algébricos e topológicos, bases de Hilbert, compressão de dados, problemas de empacotamento tridimensional, investigação poliédrica de problemas combinatórios, algoritmos de aproximação.(AU)

Publicações científicas (10)
(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)
SOARES‚ J.; STEFANES‚ M.A. Algorithms for maximum independent set in convex bipartite graphs. ALGORITHMICA, v. 53, n. 1, p. 35-49, 2009.
DE A MOREIRA‚ C.G.T.; KOHAYAKAWA‚ Y. Bounds for optimal coverings. DISCRETE APPLIED MATHEMATICS, v. 141, n. 1, p. 263-276, 2004.
KOHAYAKAWA‚ Y.; NAGLE‚ B.; RÖDL‚ V. Hereditary properties of triple systems. COMBINATORICS PROBABILITY & COMPUTING, v. 12, n. 02, p. 155-189, 2003.
KOHAYAKAWA‚ Y.; RÖDL‚ V. Regular pairs in sparse random graphs I. RANDOM STRUCTURES & ALGORITHMS, v. 22, n. 4, p. 359-434, 2003.
DONADELLI, JAIR; KOHAYAKAWA, YOSHIHARU. A density result for random sparse oriented graphs and its relation to a conjecture of Woodall. ELECTRONIC JOURNAL OF COMBINATORICS, v. 9, 2002. Citações Web of Science: 1.
LEE‚ O.; WAKABAYASHI‚ Y. On the circuit cover problem for mixed graphs. COMBINATORICS PROBABILITY & COMPUTING, v. 11, n. 01, p. 43-59, 2002.
VAN DER HOLST‚ H.; DE PINA‚ JC. Length-bounded disjoint paths in planar graphs. DISCRETE APPLIED MATHEMATICS, v. 120, n. 1, p. 251-261, 2002.
KOHAYAKAWA‚ Y.; KREUTER‚ B.; OSTHUS‚ D. The length of random subsets of Boolean lattices. RANDOM STRUCTURES & ALGORITHMS, v. 16, n. 2, p. 177-194, 2000.
KOHAYAKAWA‚ Y.; KREUTER‚ B.; STEGER‚ A. An extremal problem for random graphs and the number of graphs with large even-girth. COMBINATORICA, v. 18, n. 1, p. 101-120, 1998.
KOHAYAKAWA‚ Y.; PRÖMEL‚ H.J.; RÖDL‚ V. Induced ramsey numbers. COMBINATORICA, v. 18, n. 3, p. 373-404, 1998.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.