15 Search Results for "Gregor, Petr"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.21
On Minimum Venn Diagrams

Authors: Sofia Brenner, Petr Gregor, Torsten Mütze, and Francesco Verciani

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
An n-Venn diagram is a diagram in the plane consisting of n simple closed curves that intersect only finitely many times such that each of the 2ⁿ possible intersections of their interiors is represented by a single connected region. An n-Venn diagram has at most 2ⁿ-2 crossings, and if this maximum number of crossings is attained, then only two curves intersect in every crossing. To complement this, Bultena and Ruskey considered n-Venn diagrams that minimize the number of crossings, which implies that many curves intersect in every crossing. Specifically, they proved that the total number of crossings in any n-Venn diagram is at least L_n≔⌈(2ⁿ-2)/(n-1)⌉, and if this lower bound is attained, then essentially all n curves intersect in every crossing. Diagrams achieving this bound are called minimum Venn diagrams, and are known only for n ≤ 7. Bultena and Ruskey conjectured that they exist for all n ≥ 8. In this work, we establish an asymptotic version of their conjecture. For n = 8 we construct a diagram with 40 crossings, only 3 more than the lower bound L₈ = 37. Furthermore, for every n of the form n = 2^k for some integer k ≥ 4, we construct an n-Venn diagram with at most (1+33/8n)L_n = (1+o(1))L_n many crossings. Via a doubling trick this also gives (n+m)-Venn diagrams for all 0 ≤ m < n with at most 40⋅ 2^m crossings for n = 8 and at most (1+33/8n) (n+m)/n L_{n+m} = (2+o(1))L_{n+m} many crossings for k ≥ 4. In particular, we obtain n-Venn diagrams with the smallest known number of crossings for all n ≥ 8. Our constructions are based on partitions of the hypercube into isometric paths and cycles, using a result of Ramras.
Cite as

Sofia Brenner, Petr Gregor, Torsten Mütze, and Francesco Verciani. On Minimum Venn Diagrams. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brenner_et_al:LIPIcs.SoCG.2026.21,
  author =	{Brenner, Sofia and Gregor, Petr and M\"{u}tze, Torsten and Verciani, Francesco},
  title =	{{On Minimum Venn Diagrams}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.21},
  URN =		{urn:nbn:de:0030-drops-258278},
  doi =		{10.4230/LIPIcs.SoCG.2026.21},
  annote =	{Keywords: Venn diagram, crossing, conjecture, hypercube, partition}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.23
Pyramid Schemes for Eating M&Ms: Enumeration, Generation, and Gray Codes

Authors: Elizabeth Hartung, Brett Stevens, and Aaron Williams

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
Consider the following problem. You have a rainbow pyramid of M&Ms with n rows. For example, when n = 4 you may have one red, two orange, three yellow, and four green {inline.pdf}. You want to eat n of the M&Ms in such a way that the remaining M&Ms can be rearranged into a rainbow pyramid with n-1 rows. Two approaches are distinct if a different number from a particular row are eaten. In other words, we only care about the multiset of row frequencies (or colours) that are eaten and not the order in which they are eaten. One solution eats one M&M per row (e.g., 1234 → {inline.pdf}). Another eats the entire bottom row (e.g., 4444 → {inline.pdf}). How many different solutions are there? We show that the answer is 2^{n-1}. Furthermore, each solution can be naturally encoded with combinatorial objects enumerated by 2^{n-1} including binary words of length n-1, compositions of n, and subsets of [n-1]. Less obviously they are encoded by M&M permutations where each value in [n] is at most one position to the right of its position in the identity (e.g., 123, 132, 213, 312 for n = 3). What if at most m from each row can be eaten? When m = 1 the only solution is to eat one of each colour. Otherwise, the solutions are counted by Fibonacci (m = 2), Tribonacci (m = 3), Tetranacci (m = 4), and so on, up to 2^{n-1} (m = n). Furthermore, solutions can be naturally encoded by limited versions of the aforementioned objects including binary strings avoiding the substring 0^{m} and M&M permutations where values are limited by moving at most 𝓁 = m-1 positions to the left. Motivated by the works of Samuel Beckett, we consider minimal-change orders of the solutions. We obtain a satisfying result by filtering the binary reflected Gray code to words avoiding 0^{m}. For example, when n = 4 we have BRGC(n) = 000, 100, 110, 010, 011, 111, 101, 001 and the words avoiding 00 are BRGC_𝓁(3) = 110, 010, 011, 111, 101 where 𝓁 = 1 is the limit on the run-lengths of 0s. Our bijection then creates solutions that differ in by a single M&M 1244, 2244, 2234,1234, 1334. Thus, Beckett’s character Murphy can imagine every experience by changing one M&M at a time. The generalized Gray code BRGC_𝓁(n) was previously defined recursively [Bernini et. al Acta Informatica 2015] with its change sequence supporting amortized 𝒪(1)-time generation [Arndt Matters Computational 2010]. We uncover a simple greedy definition - flip the leftmost bit that creates a new binary word avoiding 0^m starting from w = ⋯ 110^{𝓁}110^{𝓁} - and a successor rule that supports loopless worst-case 𝒪(1)-time generation. Furthermore, the corresponding limited M&M permutations are greedily generated by swapping the smallest value (or the leftmost pair of adjacent values) that gives a valid new permutation (e.g., ̅{12}43, 21 ̅{43}, ̅{21}34, 1 ̅{23}4, 1324 for n = 4 and 𝓁 = 1). We also consider a relaxed version of the problem in which the initial pyramid’s n rows have respective widths r, r+1, r+2, …, n, n, …, n. Here the answer is an n-term product ⟨n,r⟩! = 1 ⋅ 2 ⋅ 3 ⋯ r ⋅ (r+1) ⋅ (r+1) ⋯ (r+1) that we refer to as a flatorial number. Furthermore, the solutions are represented by a generalization of M&M permutations in which each symbol can appear at most r positions to the right of its position in the identity. We complete our investigation by showing that eight distinct classes of permutations are enumerated by flatorial numbers.
Cite as

Elizabeth Hartung, Brett Stevens, and Aaron Williams. Pyramid Schemes for Eating M&Ms: Enumeration, Generation, and Gray Codes. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{hartung_et_al:LIPIcs.FUN.2026.23,
  author =	{Hartung, Elizabeth and Stevens, Brett and Williams, Aaron},
  title =	{{Pyramid Schemes for Eating M\&Ms: Enumeration, Generation, and Gray Codes}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{23:1--23:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.23},
  URN =		{urn:nbn:de:0030-drops-257420},
  doi =		{10.4230/LIPIcs.FUN.2026.23},
  annote =	{Keywords: combinatorial enumeration, generation, Gray code, loopless algorithm}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.15
Parameterized Complexity of Directed Traveling Salesman Problem

Authors: Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Directed Traveling Salesman Problem (DTSP) is a variant of the classical Traveling Salesman Problem in which the edges in the graph are directed and a vertex and edge can be visited multiple times. The goal is to find a directed closed walk of minimum length (or total weight) that visits every vertex of the given graph at least once. In a yet more general version, Directed Waypoint Routing Problem (DWRP), some vertices are marked as terminals and we are only required to visit all terminals. Furthermore, each edge has its capacity bounding the number of times this edge can be used by a solution. While both problems (and many other variants of TSP) were extensively investigated, mostly from the approximation point of view, there are surprisingly few results concerning the parameterized complexity. Our starting point is the result of Marx et al. [APPROX/RANDOM 2016] who proved that DTSP is W[1]-hard parameterized by distance to pathwidth 3. In this paper we aim to initiate the systematic complexity study of variants of Directed Traveling Salesman Problem with respect to various, mostly structural, parameters. We show that DWRP is FPT parameterized by the solution size, the feedback edge number and the vertex integrity of the underlying undirected graph. Furthermore, the problem is XP parameterized by treewidth. On the complexity side, we show that the problem is W[1]-hard parameterized by the distance to constant treedepth.
Cite as

Václav Blažej, Andreas Emil Feldmann, Foivos Fioravantes, Paweł Rzążewski, and Ondřej Suchý. Parameterized Complexity of Directed Traveling Salesman Problem. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.ISAAC.2025.15,
  author =	{Bla\v{z}ej, V\'{a}clav and Feldmann, Andreas Emil and Fioravantes, Foivos and Rz\k{a}\.{z}ewski, Pawe{\l} and Such\'{y}, Ond\v{r}ej},
  title =	{{Parameterized Complexity of Directed Traveling Salesman Problem}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.15},
  URN =		{urn:nbn:de:0030-drops-249231},
  doi =		{10.4230/LIPIcs.ISAAC.2025.15},
  annote =	{Keywords: Directed TSP, parameterized complexity, vertex integrity, treedepth}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.27
On the h-Majority Dynamics with Many Opinions

Authors: Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, and Emanuele Natale

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We present the first upper bound on the convergence time to consensus of the well-known h-majority dynamics with k opinions, in the synchronous setting, for h and k that are both non-constant values. We suppose that, at the beginning of the process, there is some initial additive bias towards some plurality opinion, that is, there is an opinion that is supported by x nodes while any other opinion is supported by strictly fewer nodes. We prove that, with high probability, if the bias is ω(√x) and the initial plurality opinion is supported by at least x = ω(log n) nodes, then the process converges to plurality consensus in O(log n) rounds whenever h = ω(n log n / x). A main corollary is the following: if k = o(n / log n) and the process starts from an almost-balanced configuration with an initial bias of magnitude ω(√{n/k}) towards the initial plurality opinion, then any function h = ω(k log n) suffices to guarantee convergence to consensus in O(log n) rounds, with high probability. Our upper bound shows that the lower bound of Ω(k / h²) rounds to reach consensus given by Becchetti et al. (2017) cannot be pushed further than Ω̃(k / h). Moreover, the bias we require is asymptotically smaller than the Ω(√{nlog n}) bias that guarantees plurality consensus in the 3-majority dynamics: in our case, the required bias is at most any (arbitrarily small) function in ω(√x) for any value of k ≥ 2.
Cite as

Francesco d'Amore, Niccolò D'Archivio, George Giakkoupis, and Emanuele Natale. On the h-Majority Dynamics with Many Opinions. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 27:1-27:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{damore_et_al:LIPIcs.DISC.2025.27,
  author =	{d'Amore, Francesco and D'Archivio, Niccol\`{o} and Giakkoupis, George and Natale, Emanuele},
  title =	{{On the h-Majority Dynamics with Many Opinions}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{27:1--27:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.27},
  URN =		{urn:nbn:de:0030-drops-248448},
  doi =		{10.4230/LIPIcs.DISC.2025.27},
  annote =	{Keywords: Distributed Algorithms, Randomized Algorithms, Markov Chains, Consensus Problem, Opinion dynamics, Plurality Consensus}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.15
Symmetry Classes of Hamiltonian Cycles

Authors: Júlia Baligács, Sofia Brenner, Annette Lutz, and Lena Volk

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We initiate the study of Hamiltonian cycles up to symmetries of the underlying graph. Our focus lies on the extremal case of Hamiltonian-transitive graphs, i.e., Hamiltonian graphs where, for every pair of Hamiltonian cycles, there is a graph automorphism mapping one cycle to the other. This generalizes the extensively studied uniquely Hamiltonian graphs. In this paper, we show that Cayley graphs of abelian groups are not Hamiltonian-transitive (under some mild conditions and some non-surprising exceptions), i.e., they contain at least two structurally different Hamiltonian cycles. To show this, we reduce Hamiltonian-transitivity to properties of the prime factors of a Cartesian product decomposition, which we believe is interesting in its own right. We complement our results by constructing infinite families of regular Hamiltonian-transitive graphs and take a look at the opposite extremal case by constructing a family with many different Hamiltonian cycles up to symmetry.
Cite as

Júlia Baligács, Sofia Brenner, Annette Lutz, and Lena Volk. Symmetry Classes of Hamiltonian Cycles. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.MFCS.2025.15,
  author =	{Balig\'{a}cs, J\'{u}lia and Brenner, Sofia and Lutz, Annette and Volk, Lena},
  title =	{{Symmetry Classes of Hamiltonian Cycles}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.15},
  URN =		{urn:nbn:de:0030-drops-241221},
  doi =		{10.4230/LIPIcs.MFCS.2025.15},
  annote =	{Keywords: Hamiltonian cycles, graph automorphisms, Cayley graphs, abelian groups, Cartesian product of graphs}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2025.19
Profile-Guided Field Externalization in an Ahead-Of-Time Compiler

Authors: Sebastian Kloibhofer, Lukas Makor, Peter Hofer, David Leopoldseder, and Hanspeter Mössenböck

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
Field externalization is a technique to reduce the footprint of objects by removing fields that most frequently contain zero or null. While researchers have developed ways to bring this optimization into the Java world, these have been limited to research compilers or virtual machines for embedded systems. In this work, we present a novel field externalization technique that uses information from static analysis and profiling to determine externalizable fields. During compilation, we remove those fields and define companion classes. These are used in case of non-default-value writes to the externalized fields. Our approach also correctly handles synchronization to prevent issues in multithreaded environments. We integrated our approach into the modern Java ahead-of-time compiler GraalVM Native Image. We conducted an evaluation on a diverse set of benchmarks that includes standard and microservice-based benchmarks. For standard benchmarks, our approach reduces the total allocated bytes by 2.76% and the maximum resident set size (max-RSS) by 2.55%. For microservice benchmarks, we achieved a reduction of 6.88% for normalized allocated bytes and 2.45% for max-RSS. We computed these improvements via the geometric mean. The median reductions are are 1.46% (alloc. bytes) and 0.22% (max-RSS) in standard benchmarks, as well as 3.63% (alloc. bytes) and 0.20% (max-RSS) in microservice benchmarks.
Cite as

Sebastian Kloibhofer, Lukas Makor, Peter Hofer, David Leopoldseder, and Hanspeter Mössenböck. Profile-Guided Field Externalization in an Ahead-Of-Time Compiler. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 19:1-19:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kloibhofer_et_al:LIPIcs.ECOOP.2025.19,
  author =	{Kloibhofer, Sebastian and Makor, Lukas and Hofer, Peter and Leopoldseder, David and M\"{o}ssenb\"{o}ck, Hanspeter},
  title =	{{Profile-Guided Field Externalization in an Ahead-Of-Time Compiler}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{19:1--19:32},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.19},
  URN =		{urn:nbn:de:0030-drops-233121},
  doi =		{10.4230/LIPIcs.ECOOP.2025.19},
  annote =	{Keywords: compilation, instrumentation, profiling, fields, externalization, memory footprint reduction, memory footprint optimization}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2025.25
Reusing Highly Optimized IR in Dynamic Compilation

Authors: Andrej Pečimúth, David Leopoldseder, and Petr Tůma

Published in: LIPIcs, Volume 333, 39th European Conference on Object-Oriented Programming (ECOOP 2025)

Abstract
Virtual machines (VMs) with dynamic compilers typically specialize compiled code to the state of the running VM instance and thus cannot reuse the code between multiple runs of the same application. The JIT compiler must recompile the same methods for each run of the application separately, which can prolong the application’s warmup time. We propose a technique to reduce compilation time by reusing a highly optimized intermediate representation (IR). We achieve this by tracing compiler-interface calls during compilation. The validity of the specializations in the IR is verified during a replay stage, and the replay also facilitates the relocation of runtime object references. The IR is stored on a compilation server, which can compile it to machine code and provide the code to local or remote VM instances. We implemented a compilation server with IR caching for GraalVM, a high-performance production-grade Java Virtual Machine (JVM). We present an evaluation based on four industry-standard benchmark suites. In each suite, our approach reduces compilation time by 23.6% to 36.8% and warmup time by 13.1% to 21.2% on average while preserving peak application performance.
Cite as

Andrej Pečimúth, David Leopoldseder, and Petr Tůma. Reusing Highly Optimized IR in Dynamic Compilation. In 39th European Conference on Object-Oriented Programming (ECOOP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 333, pp. 25:1-25:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pecimuth_et_al:LIPIcs.ECOOP.2025.25,
  author =	{Pe\v{c}im\'{u}th, Andrej and Leopoldseder, David and T\r{u}ma, Petr},
  title =	{{Reusing Highly Optimized IR in Dynamic Compilation}},
  booktitle =	{39th European Conference on Object-Oriented Programming (ECOOP 2025)},
  pages =	{25:1--25:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-373-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{333},
  editor =	{Aldrich, Jonathan and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2025.25},
  URN =		{urn:nbn:de:0030-drops-233176},
  doi =		{10.4230/LIPIcs.ECOOP.2025.25},
  annote =	{Keywords: code reuse, compilation time, warmup, remote compilation, dynamic compilation, virtual machines}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.35
Generating All Invertible Matrices by Row Operations

Authors: Petr Gregor, Hung P. Hoang, Arturo Merino, and Ondřej Mička

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
We show that all invertible n × n matrices over any finite field 𝔽_q can be generated in a Gray code fashion. More specifically, there exists a listing such that (1) each matrix appears exactly once, and (2) two consecutive matrices differ by adding or subtracting one row from a previous or subsequent row, or by multiplying or dividing a row by the generator of the multiplicative group of 𝔽_q. This even holds in the more general setting where the pairs of rows that can be added or subtracted are specified by an arbitrary transition tree that has to satisfy some mild constraints. Moreover, we can prescribe the first and the last matrix if n ≥ 3, or n = 2 and q > 2. In other words, the corresponding flip graph on all invertible n × n matrices over 𝔽_q is Hamilton connected if it is not a cycle. This solves yet another special case of Lovász conjecture on Hamiltonicity of vertex-transitive graphs.
Cite as

Petr Gregor, Hung P. Hoang, Arturo Merino, and Ondřej Mička. Generating All Invertible Matrices by Row Operations. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.ISAAC.2024.35,
  author =	{Gregor, Petr and Hoang, Hung P. and Merino, Arturo and Mi\v{c}ka, Ond\v{r}ej},
  title =	{{Generating All Invertible Matrices by Row Operations}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{35:1--35:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.35},
  URN =		{urn:nbn:de:0030-drops-221621},
  doi =		{10.4230/LIPIcs.ISAAC.2024.35},
  annote =	{Keywords: Hamilton cycle, combinatorial Gray code, invertible matrices, finite field, general linear group, generation algorithms}
}
Document
Vision
DOI: 10.4230/TGDK.1.1.6
Towards Ordinal Data Science

Authors: Gerd Stumme, Dominik Dürrschnabel, and Tom Hanika

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Order is one of the main instruments to measure the relationship between objects in (empirical) data. However, compared to methods that use numerical properties of objects, the amount of ordinal methods developed is rather small. One reason for this is the limited availability of computational resources in the last century that would have been required for ordinal computations. Another reason - particularly important for this line of research - is that order-based methods are often seen as too mathematically rigorous for applying them to real-world data. In this paper, we will therefore discuss different means for measuring and ‘calculating’ with ordinal structures - a specific class of directed graphs - and show how to infer knowledge from them. Our aim is to establish Ordinal Data Science as a fundamentally new research agenda. Besides cross-fertilization with other cornerstone machine learning and knowledge representation methods, a broad range of disciplines will benefit from this endeavor, including, psychology, sociology, economics, web science, knowledge engineering, scientometrics.
Cite as

Gerd Stumme, Dominik Dürrschnabel, and Tom Hanika. Towards Ordinal Data Science. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 6:1-6:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{stumme_et_al:TGDK.1.1.6,
  author =	{Stumme, Gerd and D\"{u}rrschnabel, Dominik and Hanika, Tom},
  title =	{{Towards Ordinal Data Science}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{6:1--6:39},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.6},
  URN =		{urn:nbn:de:0030-drops-194801},
  doi =		{10.4230/TGDK.1.1.6},
  annote =	{Keywords: Order relation, data science, relational theory of measurement, metric learning, general algebra, lattices, factorization, approximations and heuristics, factor analysis, visualization, browsing, explainability}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2023.33
Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections

Authors: Petr Gregor, Torsten Mütze, and Namrata

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
In this paper we propose a notion of pattern avoidance in binary trees that generalizes the avoidance of contiguous tree patterns studied by Rowland and non-contiguous tree patterns studied by Dairyko, Pudwell, Tyner, and Wynn. Specifically, we propose algorithms for generating different classes of binary trees that are characterized by avoiding one or more of these generalized patterns. This is achieved by applying the recent Hartung-Hoang-Mütze-Williams generation framework, by encoding binary trees via permutations. In particular, we establish a one-to-one correspondence between tree patterns and certain mesh permutation patterns. We also conduct a systematic investigation of all tree patterns on at most 5 vertices, and we establish bijections between pattern-avoiding binary trees and other combinatorial objects, in particular pattern-avoiding lattice paths and set partitions.
Cite as

Petr Gregor, Torsten Mütze, and Namrata. Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.ISAAC.2023.33,
  author =	{Gregor, Petr and M\"{u}tze, Torsten and Namrata},
  title =	{{Pattern-Avoiding Binary Trees - Generation, Counting, and Bijections}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.33},
  URN =		{urn:nbn:de:0030-drops-193350},
  doi =		{10.4230/LIPIcs.ISAAC.2023.33},
  annote =	{Keywords: Generation, binary tree, pattern avoidance, permutation, bijection}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2022.54
The Hamilton Compression of Highly Symmetric Graphs

Authors: Petr Gregor, Arturo Merino, and Torsten Mütze

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract
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.
Cite as

Petr Gregor, Arturo Merino, and Torsten Mütze. The Hamilton Compression of Highly Symmetric Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.MFCS.2022.54,
  author =	{Gregor, Petr and Merino, Arturo and M\"{u}tze, Torsten},
  title =	{{The Hamilton Compression of Highly Symmetric Graphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{54:1--54:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.54},
  URN =		{urn:nbn:de:0030-drops-168529},
  doi =		{10.4230/LIPIcs.MFCS.2022.54},
  annote =	{Keywords: Hamilton cycle, Gray code, hypercube, permutahedron, Johnson graph, Cayley graph, abelian group, vertex-transitive}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.34
Star Transposition Gray Codes for Multiset Permutations

Authors: Petr Gregor, Torsten Mütze, and Arturo Merino

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
Given integers k ≥ 2 and a_1,…,a_k ≥ 1, let a: = (a_1,…,a_k) and n: = a_1+⋯+a_k. An a-multiset permutation is a string of length n that contains exactly a_i symbols i for each i = 1,…,k. In this work we consider the problem of exhaustively generating all a-multiset permutations by star transpositions, i.e., in each step, the first entry of the string is transposed with any other entry distinct from the first one. This is a far-ranging generalization of several known results. For example, it is known that permutations (a_1 = ⋯ = a_k = 1) can be generated by star transpositions, while combinations (k = 2) can be generated by these operations if and only if they are balanced (a_1 = a_2), with the positive case following from the middle levels theorem. To understand the problem in general, we introduce a parameter Δ(a): = n-2max{a_1,…,a_k} that allows us to distinguish three different regimes for this problem. We show that if Δ(a) < 0, then a star transposition Gray code for a-multiset permutations does not exist. We also construct such Gray codes for the case Δ(a) > 0, assuming that they exist for the case Δ(a) = 0. For the case Δ(a) = 0 we present some partial positive results. Our proofs establish Hamilton-connectedness or Hamilton-laceability of the underlying flip graphs, and they answer several cases of a recent conjecture of Shen and Williams. In particular, we prove that the middle levels graph is Hamilton-laceable.
Cite as

Petr Gregor, Torsten Mütze, and Arturo Merino. Star Transposition Gray Codes for Multiset Permutations. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.STACS.2022.34,
  author =	{Gregor, Petr and M\"{u}tze, Torsten and Merino, Arturo},
  title =	{{Star Transposition Gray Codes for Multiset Permutations}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.34},
  URN =		{urn:nbn:de:0030-drops-158448},
  doi =		{10.4230/LIPIcs.STACS.2022.34},
  annote =	{Keywords: Gray code, permutation, combination, transposition, Hamilton cycle}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.60
On the Central Levels Problem

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

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
The central levels problem asserts that the subgraph of the (2m+1)-dimensional hypercube induced by all bitstrings with at least m+1-𝓁 many 1s and at most m+𝓁 many 1s, i.e., the vertices in the middle 2𝓁 levels, has a Hamilton cycle for any m ≥ 1 and 1 ≤ 𝓁 ≤ m+1. This problem was raised independently by Savage, by Gregor and Škrekovski, and by Shen and Williams, and it is a common generalization of the well-known middle levels problem, namely the case 𝓁 = 1, and classical binary Gray codes, namely the case 𝓁 = m+1. In this paper we present a general constructive solution of the central levels problem. Our results also imply the existence of optimal cycles through any sequence of 𝓁 consecutive levels in the n-dimensional hypercube for any n ≥ 1 and 1 ≤ 𝓁 ≤ n+1. Moreover, extending an earlier construction by Streib and Trotter, we construct a Hamilton cycle through the n-dimensional hypercube, n≥ 2, that contains the symmetric chain decomposition constructed by Greene and Kleitman in the 1970s, and we provide a loopless algorithm for computing the corresponding Gray code.
Cite as

Petr Gregor, Ondřej Mička, and Torsten Mütze. On the Central Levels Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.ICALP.2020.60,
  author =	{Gregor, Petr and Mi\v{c}ka, Ond\v{r}ej and M\"{u}tze, Torsten},
  title =	{{On the Central Levels Problem}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{60:1--60:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.60},
  URN =		{urn:nbn:de:0030-drops-124678},
  doi =		{10.4230/LIPIcs.ICALP.2020.60},
  annote =	{Keywords: Gray code, Hamilton cycle, hypercube, middle levels, symmetric chain decomposition}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.66
Gray Codes and Symmetric Chains

Authors: Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, and Kaja Wille

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We consider the problem of constructing a cyclic listing of all bitstrings of length 2n+1 with Hamming weights in the interval [n+1-l,n+l], where 1 <= l <= n+1, by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem (l=1). We provide a solution for the case l=2 and solve a relaxed version of the problem for general values of l, by constructing cycle factors for those instances. Our proof uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets, and we present several new constructions of such decompositions. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the n-dimensional hypercube for any n >= 12.
Cite as

Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, and Kaja Wille. Gray Codes and Symmetric Chains. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.ICALP.2018.66,
  author =	{Gregor, Petr and J\"{a}ger, Sven and M\"{u}tze, Torsten and Sawada, Joe and Wille, Kaja},
  title =	{{Gray Codes and Symmetric Chains}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.66},
  URN =		{urn:nbn:de:0030-drops-90703},
  doi =		{10.4230/LIPIcs.ICALP.2018.66},
  annote =	{Keywords: Gray code, Hamilton cycle, hypercube, poset, symmetric chain}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.40
Trimming and Gluing Gray Codes

Authors: Petr Gregor and Torsten Mütze

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
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 over 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 time O(1) per generated set and space O(n). 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_(2k+1) induced by all levels [k-c,k+1+c], c in {0, 1, ... , k}, has a Hamilton cycle. We also prove an approximate version of this conjecture, showing that this graph has a cycle that visits a (1-o(1))-fraction of all vertices.
Cite as

Petr Gregor and Torsten Mütze. Trimming and Gluing Gray Codes. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 40:1-40:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.STACS.2017.40,
  author =	{Gregor, Petr and M\"{u}tze, Torsten},
  title =	{{Trimming and Gluing Gray Codes}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{40:1--40:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.40},
  URN =		{urn:nbn:de:0030-drops-69930},
  doi =		{10.4230/LIPIcs.STACS.2017.40},
  annote =	{Keywords: Gray code, subset, combination, loopless algorithm}
}
  • Refine by Type
  • 15 Document/PDF
  • 8 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 5 2025
  • 1 2024
  • 2 2023
  • 2 2022
  • Show More...

  • Refine by Author
  • 8 Gregor, Petr
  • 7 Mütze, Torsten
  • 3 Merino, Arturo
  • 2 Brenner, Sofia
  • 2 Leopoldseder, David
  • Show More...

  • Refine by Series/Journal
  • 14 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 4 Mathematics of computing → Combinatorial algorithms
  • 4 Mathematics of computing → Combinatorics
  • 4 Mathematics of computing → Graph theory
  • 2 Mathematics of computing → Matchings and factors
  • 2 Mathematics of computing → Permutations and combinations
  • Show More...

  • Refine by Keyword
  • 6 Gray code
  • 5 Hamilton cycle
  • 4 hypercube
  • 2 combination
  • 2 loopless algorithm
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact