Project information
Utilization of Structural and Width Parametres in Combinatorics and Algorithmic Complexity

Information

This project doesn't include Institute of Computer Science. It includes Faculty of Informatics. Official project website can be found on muni.cz.

Project Identification

GA201/08/0308

Project Period

1/2008 - 12/2010

Investor / Pogramme / Project type

Czech Science Foundation

Standard Projects

MU Faculty or unit

Faculty of Informatics

prof. RNDr. Petr Hliněný, Ph.D.

Keywords

tree-width, fixed parameter algorithms, graph minors, graph searching, crossing number

Many practical algorithmic problems have a core based on combinatorial structures, such as graphs, digraphs, or matroids. Although it is typically infeasible to give general algorithmic solutions of (majority of) these problems, it is often the case that such hard problems are indeed efficiently solvable for all inputs of certain internal stucture like those having bounded width.

Results

Publications

Total number of publications: 24

2008

Finding branch-decomposition and rank-decomposition

HLINĚNÝ Petr OUM Sang-il

Article in Periodical

SIAM Journal on Computing, year: 2008, volume: 38, edition: 3
New infinite families of almost-planar crossing-critical graphs

HLINĚNÝ Petr

Article in Periodical

Electronic Journal of Combinatorics, year: 2008, volume: 15, edition: 1
Stars and Bonds in Crossing-Critical Graphs

HLINĚNÝ Petr SALAZAR Gelasio

Article in Periodical

Electronic Notes in Discrete Mathematics, year: 2008, volume: 31, edition: 1
The crossing number of a projective graph is quadratic in the face--width

HLINĚNÝ Petr SALAZAR Gelasio GITLER Isidoro LEANOS Jesus

Article in Periodical

Electronic Journal of Combinatorics, year: 2008, volume: 15, edition: 1