Many questions in various areas of theoretical computer science may be formulated as problems in
hypercubes. The lecture offers an overview of selected problems studied in hypercubes with emphasis on
applications in theoretical computer science. It assumes only elementary knowledge and it is suitable for
students in the M.Sc. programme.
Last update: RNDr. Jan Hric (26.04.2019)
Mnohé otázky v různých oblastech teoretické informatiky lze formulovat jako problémy v hyperkrychlích.
Přednáška nabízí přehled vybraných problémů studovaných na hyperkrychlích s důrazem na aplikace v teoretické
informatice. Nabízí i otevřené otázky pro případný vlastní výzkum. Předpokládá pouze elementární znalosti a je
vhodná pro studenty magisterského cyklu.
Aim of the course -
Last update: T_KTI (28.04.2015)
The course gives an introduction into the area of hypercube problems.
Last update: T_KTI (03.05.2012)
Seznámit se s problematikou hyperkrychlí.
Literature -
Last update: T_KTI (28.04.2015)
B. Bollobás, Combinatorics: set systems, hypergraphs, families of vectors, and combinatorial probability, Cambridge University Press, Cambridge, 1986.
R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, 2011.
S. Jukna, Extremal Combinatorics with Applications in Computer Science, Springer, Berlin, 2001.
F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, 1992.
selected journal papers.
Last update: T_KTI (28.04.2015)
B. Bollobás, Combinatorics: set systems, hypergraphs, families of vectors, and combinatorial probability, Cambridge University Press, Cambridge, 1986.
R. Hammack, W. Imrich, S. Klavžar, Handbook of Product Graphs, Second Edition, CRC Press, 2011.
S. Jukna, Extremal Combinatorics with Applications in Computer Science, Springer, Berlin, 2001.
F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, 1992.
vybraná časopisecká literatura.
Syllabus -
Last update: T_KTI (28.04.2015)
Hypercube characterizations, basic properties.
Orbit and stabilizer theorem, group of automorphisms.
Parcial cubes, median graphs, convex expansion.
Nonexpansive maps, correspondence to 2-SAT.
Matchings, Gray codes, Hamiltonian decomposition.
Independent spanning trees, robustness of communication.