IUUK-CE-ITI series 2004

2004-175 J. Krajíček
Diagonalization in proof complexity
PDF
2004-176 P. Hliněný
Crossing number is hard for cubic graphs
PDF
2004-177 J. Fiala, V. B. Le
The subchromatic index of graphs
PDF
2004-178 D. Král' and R. Škrekovski
The last excluded case of Dirac's map-color theorem for choosability
PDF
2004-179 J. Nešetřil, P. O. de Mendez
Tree depth, subgraph coloring and homomorphism bounds
PDF
2004-180 M. Bläser, B. Manthey, J. Sgall
An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality
PDF
2004-181 M. Chrobak, W. Jawor, J. Sgall, T. Tichý
Improved online algorithms for buffer management in QoS switches
PDF
2004-182 M. Chrobak, W. Jawor, J. Sgall, T. Tichý
Online scheduling of equal-length jobs: randomization and restarts help
PDF
2004-183 J. Krajíček
Structured pigeonhole principle, search problems and hard tautologies
PDF
2004-184 R. Barták
Validating plans with durative actions via integrating Boolean and numerical constraints
PDF
2004-185 Z. Dvořák, D. Král', O. Pangrác
Locally consistent constraint satisfaction problems
PDF
2004-186 A. Bagchi, A. Chaudhary, P. Kolman, and J. Sgall
A simple combinatorial proof of duality of multiroute flows and cuts
PDF
2004-187 V. Jungić, J. Nešetřil, R. Radoičić
Rainbow Ramsey theory
PDF
2004-188 A. Bagchi, A. Chaudhary, P. Kolman
Short Length Menger's Theorem and its Relation to Reliable Optical Routing
PDF
2004-189 Banaschewski, E. Giuli, A. Pultr
Epimorphisms of uniform frames
PDF
2004-190 G. Tóth, P. Valtr
The Erdös-Szekeres theorem: upper bounds and related results
PDF
2004-191 P. Valtr
Open caps and cups in planar point sets
PDF
2004-192 J. Nešetřil, J. Solymosi, P. Valtr
A Ramsey property of planar graphs
PDF
2004-193 K.J. Swanepoel, P. Valtr
The unit distance problem on spheres
PDF
2004-194 I. Bárány, P. Valtr
Planar point sets with a small number of empty convex polygons
PDF
2004-195 J. Hubička, J. Nešetřil
Finite presentation of homogeneous graphs, posets and Ramsey classes
PDF
2004-196 D. Král' and O. Pangrác
An asymptotically optimal linear-time algorithm for locally consistent constraint satisfaction problems
PDF
2004-197 R. Ball, A. Pultr, J. Sichler
Combinatorial trees in Priestley spaces
PDF
2004-198 J. Nešetřil
Metric spaces are Ramsey
PDF
2004-199 D. Král'
Polynomial-size binary decision diagrams for the Exactly half-d-hyperclique problem reading each input bit twice
PDF
2004-201 B. Grünbaum, T. Kaiser, D. Král', M. Rosenfeld
Equipartite polytopes and graphs
PDF
2004-202 V. Jungić
On Brown's conjecture on accessible sets
PDF
2004-203 H. Broersma, G. Fijavž, T. Kaiser, R. Kužel, and Z. Ryjáček
Contractible subgraphs, Thomassen's conjecture and the dominating cycle conjecture for snarks
PDF
2004-204 Z. Dvořák, R. Škrekovski, T. Valla
Four gravity results
PDF
2004-205 P. Surynek, R. Barták
A new algorithm for maintaining arc consistency after constraint retraction
PDF
2004-206 T. Feder, P. Hell, D. Král', J. Sgall
Two algorithms for general list matrix partitions
PDF
2004-207 M. Chrobak, P. Kolman, J. Sgall
The greedy algorithm for the minimum common string partition problem
PDF
2004-208 G. J. Woeginger, J. Sgall
On the complexity of cake cutting
PDF
2004-209 D. Král', and L. Stacho
Hamiltonian threshold for strong products of graphs
PDF
2004-210 A. Goldstein, P. Kolman, J.Zheng
Minimum common string partition problem: hardness and approximations
PDF
2004-211 T. Kaiser, D. Král', R. Škrekovski, X. Zhu
The circular chromatic index of graphs of high girth
PDF
2004-212 J. Krajíček
Proof complexity
PDF
2004-213 P. Hliněný
Equivalence-free exhaustive generation of matroid representations
PDF
2004-214 Z. Dvořák, V. Jelínek, D. Král', J. Kynčl, M. Saks
Three optimal algorithms for balls of three colors
PDF
2004-215 J. Kynčl, J. Pach, and G. Tóth
Long alternating paths in bicolored point sets
PDF
2004-216 J. Šíma, J. Sgall
On the non-learnability of a single spiking neuron
PDF
2004-217 P. Kolman
Linear Time Approximation Algorithm for Sorting by Reversals with Bounded Number of Duplicates
PDF
2004-218 J. Fiala, P. Golovach, J. Kratochvíl
Elegant distance constrained labelings of trees
PDF
2004-219 J. Montellano-Ballesteros, A. Pór, R. Strausz
Tverberg-type theorems for separoids
PDF
2004-220 M. Klazar
Prvočísla obsahují libovolně dlouhé aritmetické posloupnosti
PDF
2004-221 M. Klazar
Counting set systems by weight
PDF
2004-222 J.Nešetřil, C.Tardif
Short answers to exponentially long questions: Extremal aspects of homomorphism duality
PDF
2004-223 R. Barták
On Generators of Random Quasigroup Problems
PDF
2004-224 R. Barták
Propagating Deletions in Tabular Constraints
PDF
2004-225 T.Kaiser, R.Škrekovski
Cycles intersecting edge-cuts of prescribed sizes
PDF
2004-226 R. Babilon, V. Jelínek, D. Král', P. Valtr
Labelings of Graphs with Fixed and Variable Edge-Weights
PDF
2004-227 R.N. Ball, A. Pultr, J. Sichler
The mysterious 2-crown
PDF
2004-228 J. Nešetřil, R. Strausz
Universality of separoids
PDF
2004-229 D. Král'
Channel assignment problem with variable weights
PDF
2004-230 P. Nejedlý
Choosability of graphs with infinite sets of forbidden differences
PDF
2004-231 M. Bálek, J. Nešetřil
Towards Mathematical Aesthetics
PDF
2004-232 W.Krauth, M.Loebl
Jamming and geometric representations of graphs
PDF
2004-233 M.Janata, M.Loebl, J.Szabó
The Edmonds-Gallai decompositions for the k-piece packing problem
PDF
2004-234 R.A.Brualdi, M.Loebl, O.Pangrác
Perfect matching preservers
PDF