Charles University in Prague

Faculty of Mathematics and Physics

 

Department of Theoretical Computer Science and Mathematical Logic

doc. Mgr. Petr Gregor, Ph.D.

I study algorithmic and structural problems in the theory of interconnection networks motivated for example by effective communication. These areas serve as a resource of many interesting questions that can be approached with the means of extremal combinatorics, graph theory, or coding theory.

Teaching

Propositional and Predicate Logic (lecture in English, lecture and seminar in Czech from previous years)

Introduction to Complexity and Computability (practicals, in winter term, from previous years)

Hypercube Structures (in winter term)

Automata and Grammars (seminars in Czech, in summer term)

Data Structures I (lecture in Czech, winter term 2020/21, lecture in English).


Topics

Topics for a bachelor / master thesis or for an individual software project are available here.

Contact

Department of Theoretical Computer Science and Mathematical Logic

Charles University

Malostranské nám. 25

118 00 Prague 1

Czech Republic

tel: +420 95155 4140

fax: +420 95155 4323

gregor(at)ktiml.mff.cuni.cz

 

 













List of publications
[59] P. Gregor, A. Merino, T. Mütze, F. Verciani, Graphs that admit a Hamilton path are cup-stackable, an extended abstract has been accepted for presentation at the 26th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCGGG 2024), Full preprint available at arXiv:2401.06189.
[58] P. Gregor, H. P. Hoang, A. Merino, O. Mička, Generating all invertible matrices by row operations, an extended abstract has been accepted for presentation at the 35th International Symposium on Algorithms and Computation (ISAAC 2024). Full preprint available at arXiv:2405.01863.
[57] P. Gregor, J. Kranjc, B. Lužar, K. Štorgel, Packing coloring of hypercubes with extended Hamming codes, Discrete Applied Mathematics, 359:269-277, 2024.
[56] P. Gregor, T. Mütze, and Namrata, Combinatorial generation via permutation languages. VI. Binary trees, European Journal of Combinatorics, 122:104020, 2024.
[55] P. Gregor, A. Merino, and T. Mütze, The Hamilton Compression of Highly Symmetric Graphs, Annals of Combinatorics, 28:379–437, 2024.
[54] P. Gregor, T. Mütze, and Namrata, Pattern-avoiding binary trees - generation, counting, and bijections, Proc. 34th International Symposium on Algorithms and Computation (ISAAC 2023), Leibniz International Proceedings in Informatics (LIPIcs), vol. 283 (2023), pp. 33:1-33:19.
[53] P. Gregor, A. Merino, and T. Mütze, Star transposition Gray codes for multiset permutations. Journal of Graph Theory, 103:212-270, 2023.
[52] P. Gregor, O. Mička, and T. Mütze, On the central levels problem. Journal of Combinatorial Theory, Series B, 160:163-205, 2023.
[51] P. Gregor, A. Merino, and T. Mütze, The Hamilton compression of highly symmetric graphs. Proc. 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Leibniz International Proceedings in Informatics (LIPIcs), vol. 241 (2022), pp. 54:1-54:14. Best paper award at MFCS 2022.
[50] P. Gregor, A. Merino, and T. Mütze, Star transposition Gray codes for multiset permutations. Proc. 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Leibniz International Proceedings in Informatics (LIPIcs), vol. 219 (2022), pp. 34:1 -34:14.
[49] P. Gregor, S. Jager, T. Mütze, J. Savada, and K. Wille, Gray codes and symmetric chains. Journal of Combinatorial Theory, Series B, 153:31-60, 2022.
[48] P. Gregor, O. Mička, and T. Mütze, On the central levels problem, Proc. 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), Leibniz International Proceedings in Informatics (LIPIcs), vol. 168 (2020), pp. 60:1-60:17.
[47] V. Vukašinovic, D. Kuboň, R. Škrekovski, and P. Gregor, Redundant Binary Representations with Rigorous Tradeoff Between Connectivity and Locality, Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion (GECCO 2020), pp. 325-326, 2020.
[46] P. Gregor, Combinatorial structures in hypercubes, Habilitation thesis, Charles University, 2019. [pdf]
[45] P. Gregor, T. Novotný, and R. Škrekovski, Extending Perfect Matchings to Gray Codes with Prescribed Ends, Electronic Journal of Combinatorics 25 (2018), #P2.56.
[44] P. Gregor, S. Jager, T. Mütze, J. Savada, and K. Wille, Gray codes and symmetric chains. Proc. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 107 (2018), pp. 66:1-66.14.
[43] P. Gregor, T. Mütze, and J. Nummenpalo, A short proof of the middle levels theorem, Discrete Analysis 2018:8, 12 pp. Available at arXiv:1710.08249.
[42] D. Kuboň and P. Gregor, Quest for good spanners in hypercubes. 2018 IEEE Congress on Evolutionary Computation (CEC) , IEEE Proceedings, 2018, pp. 1-8.
[41] P. Gregor, R. Škrekovski, and V. Vukašinovic, Broadcasting multiple messages in the 1-in port model in optimal time, Journal of Combinatorial Optimization, 36:1333-1355, 2018.
[40] P. Gregor, R. Škrekovski, and V. Vukašinovic, Modelling simultaneous broadcasting by level-disjoint partitions, Applied Mathematics and Computation, 325:15-23, 2018.
[39] P. Gregor and T. Mütze, Trimming and gluing Gray codes. Theoretical Computer Science, 714:74-95, 2018.
[38] J. Fink, T. Dvořák, P. Gregor, and T. Novotný, Towards a problem of Ruskey and Savage on matching extendability. Electronic Notes in Discrete Mathematics, 61:437-443, 2017.
[37] P. Gregor, B. Lužar, and R. Soták, Note on incidence chromatic number of subquartic graphs. Journal of Combinatorial Optimization, 34:174-181, 2017.
[36] P. Gregor and T. Mütze, Trimming and gluing Gray codes, Proc. 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), Leibniz International Proceedings in Informatics (LIPIcs), vol. 66 (2017), pp. 40:1-40.14.
[35] T. Dvořák, P. Gregor, and V. Koubek, Generalized Gray codes with prescribed ends, Theoretical Computer Science, 668:70-94, 2017.
[34] P. Gregor, R. Škrekovski, and V. Vukašinovic, Time-optimal broadcasting of multiple messages in 1-in port model. Proceedings of Combinatorial Optimization and Applications (COCOA 2016), volume 10043 of Lecture Notes in Computer Science, pages 144-158, 2016.
[33] P. Gregor, B. Lužar, and R. Soták, On incidence coloring conjecture in Cartesian products of graphs. Discrete Applied Mathematics, 213:93-100, 2016.
[32] P. Gregor and D. Pěgřímek, Hamiltonian Laceability of Hypercubes Without Isometric Subgraphs. Graphs and Combinatorics, 32:2591–2624, 2016.
[31] P. Gregor, R. Škrekovski, and V. Vukašinovic, Rooted level-disjoint partitions of Cartesian products. Applied Mathematics and Computation, 266:244-258, 2015.
[30] J. Fink and P. Gregor. Linear extension diameter of level induced subposets of the boolean lattice. European Journal of Combinatorics, 35:221-231, 2014.
[29] P. Gregor and P. Kovář. Distance magic labelings of hypercubes. In Proceedings of Combinatorics 2012, volume 40 of Electronic Notes in Discrete Mathematics, pages 145-149, 2013. (extended abstract).
[28] K. Měkuta and P. Gregor. Edge-fault-tolerant hamiltonicity of augmented cubes. In Proceedings of Combinatorics 2012, volume 40 of Electronic Notes in Discrete Mathematics, pages 239-243, 2013. (extended abstract).
[27] V. Vukašinovic, P. Gregor, and R. Škrekovski. On the mutually independent hamiltonian cycles in faulty hypercubes. Information Sciences, 236:224-235, 2013.
[26] D. Dimitrov, T. Dvořák, P. Gregor, and R. Škrekovski. Linear time construction of a compressed gray code. European Journal of Combinatorics, 34:69-81, 2013.
[25] T. Dvořák, J. Fink, P. Gregor, V. Koubek, and T. Radzik. Testing connectivity of faulty networks in sublinear time. Journal of Discrete Algorithms, 14:223-231, 2012.
[24] T. Dvořák, J. Fink, P. Gregor, and V. Koubek. Gray codes with bounded weights. Discrete Mathematics, 312:2599-2611, 2012.
[23] J. Fink and P. Gregor. Long cycles in hypercubes with optimal number of faulty vertices. Journal of Combinatorial Optimization, 24:240-265, 2012.
[22] P. Gregor, R. Škrekovski, and V. Vukašinovic. Queue layouts of hypercubes. SIAM Journal of Discrete Mathematics, 26:77-88, 2012.
[21] P. Gregor and R. Škrekovski. Parity vertex coloring of binomial trees. Discussiones Mathematicae Graph Theory, 32:177-180, 2012.
[20] J. Fink and P. Gregor. Linear extension diameter of subposets of boolean lattice induced by two levels. In Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2011), volume 38 of Electronic Notes in Discrete Mathematics, pages 337-342, 2011. (extended abstract).
[19] P. Gregor, R. Škrekovski, and V. Vukašinovic. On the queue-number of the hypercube. In Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2011), volume 38 of Electronic Notes in Discrete Mathematics, pages 413-418, 2011. (extended abstract).
[18] T. Dvořák, J. Fink, P. Gregor, V. Koubek, and T. Radzik. Efficient connectivity testing of hypercubic networks with faults. In Combinatorial Algorithms, volume 6460 of Lecture Notes in Computer Science, pages 181-191, 2011.
[17] P. Gregor and R. Škrekovski. On generalized middle level problem. Information Sciences, 180(12):2448-2457, 2010.
[16] D. Dimitrov, T. Dvořák, P. Gregor, and R. Škrekovski. Gray codes avoiding matchings. Discrete Mathematics & Theoretical Computer Science, 11(2):123-147, 2009. [ http ]
[15] D. Dimitrov, T. Dvořák, P. Gregor, and R. Škrekovski. Gray code compression. In Proceedings of International Workshop on Combinatorial Algorithms (IWOCA 2009), volume 5874 of Lecture Notes in Computer Science, pages 183-193, 2009.
[14] P. Gregor. Hypercube 1-factorizations from extended hamming codes. In Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), volume 34 of Electronic Notes in Discrete Mathematics, pages 627-631, 2009. (extended abstract).
[13] T. Dvořák, J. Fink, P. Gregor, and V. Koubek. Long paths and cycles in faulty hypercubes: existence, optimality, complexity. In Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2009), volume 34 of Electronic Notes in Discrete Mathematics, pages 35-39, 2009. (extended abstract).
[12] J. Fink and P. Gregor. Long paths and cycles in hypercubes with faulty vertices. Information Sciences, 179(20):3634-3644, 2009.
[11] P. Gregor and R. Škrekovski. Long cycles in hypercubes with distant faulty vertices. Discrete Mathematics & Theoretical Computer Science, 11(1):185-198, 2009. [ http ]
[10] P. Gregor. Perfect matchings extending on subcubes to hamiltonian cycles of hypercubes. Discrete Mathematics, 309:1711-1713, 2009.
[9] T. Dvořák and P. Gregor. Partitions of faulty hypercubes into paths with prescribed endvertices. SIAM Journal of Discrete Mathematics, 22(4):1448-1461, 2008.
[8] T. Dvořák and P. Gregor. Path partitions of hypercubes. Information Processing Letters, 108(6):402-406, 2008.
[7] P. Gregor. On 3-spanners of hypercubes. (withdrawn), 2007. [ .pdf ]
[6] T. Dvořák and P. Gregor. Hamiltonian paths with prescribed edges in hypercubes. Discrete Mathematics, 307(16):1982-1998, 2007.
[5] T. Dvořák and P. Gregor. Hamiltonian fault-tolerance of hypercubes. In Proceedings of European Conference on Combinatorics, Graph Theory and Applications (EuroComb 2007), volume 29 of Electronic Notes in Discrete Mathematics, pages 471-477, 2007. (extended abstract).
[4] P. Gregor. Subgraphs of Hypercubes - Embeddings with Restrictions or Prescriptions. PhD thesis, Department of Theoretical Computer Science and Mathematical Logic, Charles University in Prague, 2006. [ .pdf ]
[3] P. Gregor. Recursive fault-tolerance of fibonacci cube in hypercubes. Discrete Mathematics, 306(13):1327-1341, 2006.
[2] T. Dvořák, P. Gregor, and V. Koubek. Spanning paths in hypercubes. In European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), Discrete Mathematics and Theoretical Computer Science AE, pages 363-368, 2005. (extended abstract).
[1] R. Caha and P. Gregor. Embedding fibonacci cubes into hypercubes with ω(2cn) faulty nodes. In Mathematical Foundations of Computer Science 2000 (MFCS 2000), volume 1893 of Lecture Notes in Computer Science, pages 253-263, 2000.