Petr Gregor

activity

20152026

most citedTrimming and gluing Gray codes

11 citations · 31 across the 6 of their papers we have counts for

collaborators

11 papers

cs.AI2026

Intermediate Results on the Complexity of STRIPS $_{1}^{1}$

Stefan Edelkamp, Jiří Fink, Petr Gregor +2

This paper is based on Bylander's results on the computational complexity of propositional STRIPS planning. He showed that when only ground literals are permitted, determining plan…

math.CO2023★ 2 cited

Packing coloring of hypercubes with extended Hamming codes

Petr Gregor, Jaka Kranjc, Borut Lužar +1

A {\em packing coloring} of a graph $G$ is a mapping assigning a positive integer (a color) to every vertex of $G$ such that every two vertices of color $k$ are at distance at leas…

math.CO2022

The Hamilton compression of highly symmetric graphs

Petr Gregor, Arturo Merino, Torsten Mütze

We say that a Hamilton cycle $C = (x_{1}, \dots, x_{n})$ in a graph $G$ is $k$ -symmetric, if the mapping $x_{i} \mapsto x_{i + n / k}$ for all $i = 1, \dots, n$ , where indices are considered modulo…

math.CO2021

Star transposition Gray codes for multiset permutations

Petr Gregor, Arturo Merino, Torsten Mütze

Given integers $k \geq 2$ and $a_{1}, \dots, a_{k} \geq 1$ , let $a := (a_{1}, \dots, a_{k})$ and $n := a_{1} + \dots + a_{k}$ . An $a$ -multiset permutation is a string of length…

math.CO2019

On the central levels problem

Petr Gregor, Ondřej Mička, Torsten Mütze

The central levels problem asserts that the subgraph of the $(2 m + 1)$ -dimensional hypercube induced by all bitstrings with at least $m + 1 - ℓ$ many 1s and at most $m + ℓ$ many 1s,…

math.CO2018★ 8 cited

Gray codes and symmetric chains

Petr Gregor, Sven Jäger, Torsten Mütze +2

We consider the problem of constructing a cyclic listing of all bitstrings of length $2 n + 1$ with Hamming weights in the interval $[n + 1 - ℓ, n + ℓ]$ , where $1 \leq ℓ \leq n + 1$ , by…

math.CO2017

A short proof of the middle levels theorem

Petr Gregor, Torsten Mütze, Jerri Nummenpalo

Consider the graph that has as vertices all bitstrings of length $2 n + 1$ with exactly $n$ or $n + 1$ entries equal to 1, and an edge between any two bitstrings that differ in exactly…

cs.DM2016

Modelling simultaneous broadcasting by level-disjoint partitions

Petr Gregor, Riste Skrekovski, Vida Vukasinovic

Simultaneous broadcasting of multiple messages from the same source vertex in synchronous networks is considered under restrictions that each vertex receives at most one message in…

math.CO2016★ 11 cited

Trimming and gluing Gray codes

Petr Gregor, Torsten Mütze

We consider the algorithmic problem of generating each subset of $[n] := {1, 2, \dots, n}$ whose size is in some interval $[k, l]$ , $0 \leq k \leq l \leq n$ , exactly once (cyclically) by…

cs.DM2016★ 10 cited

Generalized Gray codes with prescribed ends

Tomáš Dvořák, Petr Gregor, Václav Koubek

An $n$ -bit Gray code is a sequence of all $n$ -bit strings such that consecutive strings differ in a single bit. It is well-known that given $α, β \in {0, 1}^{n}$ , an $n$ -bit Gray code…

math.CO2015

On incidence coloring conjecture in Cartesian products of graphs

Petr Gregor, Borut Lužar, Roman Soták

An incidence in a graph $G$ is a pair $(v, e)$ where $v$ is a vertex of $G$ and $e$ is an edge of $G$ incident to $v$ . Two incidences $(v, e)$ and $(u, f)$ are adjacent if at least on…

Intermediate Results on the Complexity of STRIPS11​