KAM

Studenti katedry aplikované matematiky už během studia pracují na výzkumném záměru, publikují články v prestižních časopisech a jezdí na workshopy a konference. Velká část z nich spolupracuje s Institutem teoretické informatiky.

Workshopy, konference

KAM pořádá celou řadu významných konferencí a workshopů. Tradiční akcí je Midsummer Workshop. Za poslední 3 roky katedra pořádala následující akce:

• The First Czech-Catalan Conference in Mathematics (2005)
• Současné trendy teoretické informatiky (2005)
• Workshop on Graph Colorings and their Generalizations (2004)
• EUROCOMB (2003) - European Conference on Combinatorics, Graph Theory and Applications
• HOMONOLO (2003) - workshop on graph homomorphisms and related topics
• Současné trendy teoretické informatiky (2003)
• HOMONOLO (2002) - workshop on graph homomorphisms

ITI (Institut Teoretické Informatiky) - centrum mladé vědy

Institut teoretické informatiky byl založen v roce 2000, spojuje vědu na Karlově Univerzitě, Matematickém ústavu a Ústavu informatiky Akademie Věd ČR a na Západočeské univerzitě. Je finančně zabezpečen grantem Ministerstva školství a podporuje hlavně mladé vědecké pracovníky.

Publikace v časopisech, příspěvky na konferencích

Za poslední 3 roky magisterští studenti KAM poslali následující články do prestižních časopisů nebo na konference:

• Z. Dvorak, D. Kral', P. Nejedly, and R. Skrekovski: Coloring squares of planar graphs with no short cycles (submitted).
• D. Kral', R. Skrekovski, and M. Tancer : Construction of large graphs with no optimal surjective $L(2,1)$-labelings (submitted).
• P. Nejedly: Choosability of Graphs with Infinite Sets of Forbidden Differences. (submitted).
• J. Kyncl, J. Pach and G. Toth: Long Alternating Paths in Bicolored Point Sets, Graph Drawing 2004, New York, USA.
• Z. Dvorak, V. Jelinek, D. Kral', J. Kyncl and M. Saks Three Optimal Algorithms for Balls of Three Colors, STACS'05, Stuttgart, Germany.
• Z. Dvorak, R. Skrekovski and T. Valla: Four Gravity Results, (submitted).
• Z. Dvorak : Eulerian tours in graphs with forbidden transitions and bounded degree, (submitted).
• Z. Dvorak : Two-factors in Oriented Graphs with Forbidden Transitions, (submitted).
• Z. Dvorak, D. Kral' and O. Pangrac: Locally consistent constraint satisfaction problems, ICALP'04, Turku, Finland.
• Z. Dvorak and V. Jelinek : On the Complexity of the $G$-Reconstruction Problem, (submitted).
• J. Cerny, Z. Dvorak, V. Jelinek, J. Kara: Noncrossing Hamiltonian Paths in Geometric Graphs, Graph Drawing 2003, Perugia, Italy.
• J. Cerny, Z. Dvorak, V. Jelinek, and P. Podbrdsky: Generalization of the polygon-crossing problem, (submitted).
• Z. Dvorak, J. Kara, D. Kral', and O. Pangrac: An Algorithm for Cyclic Edge Connectivity of Cubic Graphs, SWAT'04, Denmark.

Za poslední 3 roky doktorandi KAM poslali následující články do prestižních časopisů nebo na konference:

• Z. Dvorak, D. Kral', P. Nejedly, and R. Skrekovski: Coloring squares of planar graphs with no short cycles.
• M. Hladik: Separation properties of two convex polyhedral sets with RHS-parameters
• J. Kara, A. Por and D. R. Wood: On the Chromatic Number of the Visibility Graph of a Set of Points in the Plane.
• R. Samal and J. Nesetril: Tension continuous maps - their structure and application.
• M. Janata, M. Loebl and J. Szabo: The Edmonds-Gallai Decomposition for the $k$-Piece Packing Problem.
• M. Balek and J. Nesetril: Towards Mathematical Aesthetics.
• D. Kral': Channel assignment problem with variable weights
• R. Babilon, V. Jelinek, D. Kral' and P. Valtr : Labelings of graphs with fixed and variable edge-weights.
• Z. Dvorak, V. Jelinek, D. Kral', J. Kyncl and M. Saks Three Optimal Algorithms for Balls of Three Colors.
• D. Kral' and L. Stacho : Hamiltonian threshold for strong products of graphs.
• M. Janata and J. Szabo : Generalized star packing problems I.
• D. Kral': Polynomial-size binary decision diagrams for the Exactly half-$d$-hyperclique problem reading each input bit twice.
• D. Kral' and O. Pangrac: An Asymptotically Optimal Linear-Time Algorithm for Locally Consistent Constraint Satisfaction Problems.
• J. Hubicka and J. Nesetril : Finite Presentation of Homogeneous Graphs, Posets and Ramsey Classes.
• Z. Dvorak, D. Kral' and O. Pangrac: Locally consistent constraint satisfaction problems
• M. Chrobak, W. Jawor, J. Sgall and T. Tichy : Improved Online Algorithms for Buffer Management in QoS Switches.
• J. Cerny : Geometric graphs with no three disjoint edges.
• D. Kral': Group coloring is $\Pi_2^P$-complete.
• J. Fiala, D. Kral' and R. Skrekovski : A Brooks-type Theorem for the Generalized List $T$-Coloring.
• D. Kral': Mixed Hypergraphs and Other Coloring Problems.
• D. Kral' and J. Sgall : Coloring graphs from lists with bounded size of their union.
• M. Janata: About a new class of matroid-inducing packing families.
• M. Janata: Matroids Induced by Packing Subgraphs.
• D. Kral': Extending partial 5-colorings and 6-colorings in planar graphs.
• T. Kaiser and D. Kral' and R. Skrekovski : A Revival of the Girth Conjecture.
• J. Matousek and P. Skovron : Three views of LP-type optimization problems.
• D. Kral' and L. Stacho: Closure for the Property of Having a Hamiltonian Prism.
• D. Kral': Locally satisfiable formulas.
• M. Balek and J. Nesetril: Measuring of Aesthetic Invariant of Images.
• J. Hubicka, J. Nesetril: Finite Paths are Universal.
• J. Hubicka, J. Nesetril: Universal Partial Order Represented by Means of Trees \\ and Other Simple Graphs.
• M. Loebl, J. Matousek, and O. Pangrac: Triangles in random graphs.
• D. Kral': Coloring Powers of Chordal Graphs.
• J. Hubicka and J. Nesetril: On Homogeneous Graphs and Posets.
• Z. Dvorak, J. Kara, D. Kral', and O. Pangrac: An Algorithm for Cyclic Edge Connectivity of Cubic Graphs.