Author name cluster

Petr Gregor

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

MFCS Conference 2022 Conference Paper

The Hamilton Compression of Highly Symmetric Graphs

Petr Gregor
Arturo Merino
Torsten Mütze

We say that a Hamilton cycle C = (x₁, …, x_n) in a graph G is k-symmetric, if the mapping x_i ↦ x_{i+n/k} for all i = 1, …, n, where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices x₁, …, x_n equidistantly on a circle and draw the edges of G as straight lines, then the drawing of G has k-fold rotational symmetry, i. e. , all information about the graph is compressed into a 360^∘/k wedge of the drawing. We refer to the maximum k for which there exists a k-symmetric Hamilton cycle in G as the Hamilton compression of G. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases we determine their Hamilton compression exactly, and in other cases we provide close lower and upper bounds. The cycles we construct have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced.

Details

TCS Journal 2018 Journal Article

Trimming and gluing Gray codes

Petr Gregor
Torsten Mütze

We consider the algorithmic problem of generating each subset of [ n ]: = { 1, 2, …, n } whose size is in some interval [ k, l ], 0 ≤ k ≤ l ≤ n, exactly once (cyclically) by repeatedly adding or removing a single element, or by exchanging a single element. For k = 0 and l = n this is the classical problem of generating all 2 n subsets of [ n ] by element additions/removals, and for k = l this is the classical problem of generating all ( n k ) subsets of [ n ] by element exchanges. We prove the existence of such cyclic minimum-change enumerations for a large range of values n, k, and l, improving upon and generalizing several previous results. For all these existential results we provide optimal algorithms to compute the corresponding Gray codes in constant O ( 1 ) time per generated set and O ( n ) space. Rephrased in terms of graph theory, our results establish the existence of (almost) Hamilton cycles in the subgraph of the n-dimensional cube Q n induced by all levels [ k, l ]. We reduce all remaining open cases to a generalized version of the middle levels conjecture, which asserts that the subgraph of Q 2 k + 1 induced by all levels [ k − c, k + 1 + c ], c ∈ { 0, 1, …, k }, has a Hamilton cycle. We also prove an approximate version of this generalized conjecture, showing that this graph has a cycle that visits a ( 1 − o ( 1 ) ) -fraction of all vertices.

Details DOI

TCS Journal 2017 Journal Article

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 vectors such that consecutive vectors differ in a single bit. It is well-known that given α, β ∈ { 0, 1 } n, an n-bit Gray code between α and β exists iff the Hamming distance d ( α, β ) of α and β is odd. We generalize this classical result to k pairwise disjoint pairs α i, β i ∈ { 0, 1 } n: if d ( α i, β i ) is odd for all i and k < n, then the set of all n-bit vectors can be partitioned into k sequences such that the i-th sequence leads from α i to β i and consecutive vectors differ in a single bit. This holds for every n > 1 with one exception in the case when n = k + 1 = 4. Our result is optimal in the sense that for every n > 2 there are n pairwise disjoint pairs α i, β i ∈ { 0, 1 } n with d ( α i, β i ) odd for which such sequences do not exist.

Details DOI

MFCS Conference 2000 Conference Paper

Embedding Fibonacci Cubes into Hypercubes with Omega (2 cn ) Faulty Nodes

Rostislav Caha
Petr Gregor

Abstract Fibonacci Cubes are special subgraphs of hypercubes based on Fibonacci numbers. We present a construction of a direct embedding of a Fibonacci Cube of dimension n into a faulty hypercube of dimension n with less or equal \( 2^{\left\lceil {\tfrac{n} {4}} \right\rceil - 1} \) faults. In fact, there exists a direct embedding of a Fibonacci Cube of dimension n into a faulty hypercube of dimension n with at most \( \tfrac{{2^n }} {{4f_n }} \) faults ( f n is the n -th Fibonacci number). Thus the number ø( n ) of tolerable faults grows exponentially with respect to dimension n, ø( n ) = Ω(2 cn ), for c = 2−log 2 (1+ \( \sqrt 5 \) ) ≐ 0: 31. On the other hand, ø( n ) = O(2 dn ), for d = (8−3 log 2 3)=4 ≐ 0: 82. As a corollary, there exists a nearly polynomial algorithm constructing a direct embedding of a Fibonacci Cube of dimension n into a faulty hypercube of dimension n (if it exists) provided that faults are given on input by enumeration. However, the problem is NP-complete, if faults are given on input with an asterisk convention.

Details