Charles University in Prague

Faculty of Mathematics and Physics

 

Department of Theoretical Computer Science and Mathematical Logic

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 Czech, seminar in Czech, lecture in English from the previous year)

Hypercube Problems (in winter term)

Automata and Grammars (seminars, in summer term)

Introduction to Complexity and Computability (from past years)

Topics

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

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

[1] P. Gregor, T. Mütze, and J. Nummenpalo, A short proof of the middle levels theorem, submitted, 2017. preprint available at arXiv:1710.08249.
[2] 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.
[3] 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.
[4] 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. full version available at arXiv:1607.08806.
[5] T. Dvořák, P. Gregor, and V. Koubek, Generalized Gray codes with prescribed ends, Theoretical Computer Science, 668:70-94, 2017.
[6] P. Gregor, R. Škrekovski, and V. Vukašinovic, Modelling simultaneous broadcasting by level-disjoint partitions, submitted, 2016. preprint available at arXiv:1609.01116.
[7] 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.
[8] 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.
[9] P. Gregor and D. Pěgřímek, Hamiltonian Laceability of Hypercubes Without Isometric Subgraphs. Graphs and Combinatorics, 32:2591–2624, 2016.
[10] P. Gregor, R. Škrekovski, and V. Vukašinovic, Rooted level-disjoint partitions of Cartesian products. Applied Mathematics and Computation, 266:244-258, 2015.
[11] J. Fink and P. Gregor. Linear extension diameter of level induced subposets of the boolean lattice. European Journal of Combinatorics, 35:221-231, 2014.
[12] 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).
[13] 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).
[14] V. Vukašinovic, P. Gregor, and R. Škrekovski. On the mutually independent hamiltonian cycles in faulty hypercubes. Information Sciences, 236:224-235, 2013.
[15] 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.
[16] 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.
[17] T. Dvořák, J. Fink, P. Gregor, and V. Koubek. Gray codes with bounded weights. Discrete Mathematics, 312:2599-2611, 2012.
[18] J. Fink and P. Gregor. Long cycles in hypercubes with optimal number of faulty vertices. Journal of Combinatorial Optimization, 24:240-265, 2012.
[19] P. Gregor, R. Škrekovski, and V. Vukašinovic. Queue layouts of hypercubes. SIAM Journal of Discrete Mathematics, 26:77-88, 2012.
[20] P. Gregor and R. Škrekovski. Parity vertex coloring of binomial trees. Discussiones Mathematicae Graph Theory, 32:177-180, 2012.
[21] 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).
[22] 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).
[23] 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.
[24] P. Gregor and R. Škrekovski. On generalized middle level problem. Information Sciences, 180(12):2448-2457, 2010.
[25] 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 ]
[26] 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.
[27] 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).
[28] 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).
[29] J. Fink and P. Gregor. Long paths and cycles in hypercubes with faulty vertices. Information Sciences, 179(20):3634-3644, 2009.
[30] P. Gregor and R. Škrekovski. Long cycles in hypercubes with distant faulty vertices. Discrete Mathematics & Theoretical Computer Science, 11(1):185-198, 2009. [ http ]
[31] P. Gregor. Perfect matchings extending on subcubes to hamiltonian cycles of hypercubes. Discrete Mathematics, 309:1711-1713, 2009.
[32] 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.
[33] T. Dvořák and P. Gregor. Path partitions of hypercubes. Information Processing Letters, 108(6):402-406, 2008.
[34] P. Gregor. On 3-spanners of hypercubes. (withdrawn), 2007. [ .pdf ]
[35] T. Dvořák and P. Gregor. Hamiltonian paths with prescribed edges in hypercubes. Discrete Mathematics, 307(16):1982-1998, 2007.
[36] 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).
[37] 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 ]
[38] P. Gregor. Recursive fault-tolerance of fibonacci cube in hypercubes. Discrete Mathematics, 306(13):1327-1341, 2006.
[39] 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).
[40] 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.