Investigation of hard problems from the algorithmic and structural stand points

Send your message by email

Advanced search

Grant number: | 96/04505-2 |

Support type: | Research Projects - Thematic Grants |

Duration: | October 01, 1996 - September 30, 2000 |

Field of knowledge: | Physical Sciences and Mathematics - Computer Science |

Principal Investigator: | Yoshiharu Kohayakawa |

Grantee: | Yoshiharu Kohayakawa |

Home Institution: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil |

Associated grant(s): | 97/14469-6 - Robin Thomas | Georgia Institute of Technology - United States,
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 - France, AV.EXT 96/12820-5 - 1) approximation algorithms for 3-D packing problems. 2) szemeredi's regulanity lemma for sparse grapys, AR.BR |

**Abstract**

The main aim of this thematic project is to investigate structural aspects of combinatorial objects. The specific aspects to be considered are the ones motivated by (i) their intrinsic mathematical interest, and by (ii) their importance for the design of efficient algorithms for computational problems of combinatorial nature, and for the proof of lower bounds for the computational complexity of such problems. The main research themes in this project are the following: 1. asymptotic properties of combinatorial structures, investigated through combinatorial and extra-combinatorial methods, such as probabilistic, algebraic, and topological methods. 2. structural properties of graphs, hypergraphs, and related structures. 3. geometric problems and methods in combinatorics, with special emphasis on polyhedral methods in combinatorial optimization. A list of specific research topics, which is not meant to be comprehensive but only illustrative, is the following: numerical problems in Ramsey theory, Turán type extremal problems, asymptotic enumeration of graphs, pseudorandom objects and their applications, algebraic and topological methods, Hilbert bases, data compression, 3-dimensional packing, polyhedral methods in combinatorial optimization, approximation algorithms. (AU)

Scientific publications
(10)

(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)

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.
Web of Science Citations: 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.

Please report errors in scientific publications list by writing to:
cdi@fapesp.br.