29 citations · 92 across the 53 of their papers we have counts for
6 papers · 1 filter
Search for the end of a path in the d-dimensional grid and in other graphs
Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi +2
We consider the worst-case query complexity of some variants of certain \cl{PPAD}-complete search problems. Suppose we are given a graph and a vertex . We denote th…
Octants are Cover-Decomposable into Many Coverings
Balázs Keszegh, Dömötör Pálvölgyi
We prove that octants are cover-decomposable into multiple coverings, i.e., for any k there is an m(k) such that any m(k)-fold covering of any subset of the space with a finite num…
Online and quasi-online colorings of wedges and intervals
Balázs Keszegh, Nathan Lemons, Dömötör Pálvölgyi
We consider proper online colorings of hypergraphs defined by geometric regions. We prove that there is an online coloring algorithm that colors intervals of the real line usin…
Regular families of forests, antichains and duality pairs of relational structures
Péter L. Erdős, Dömötör Pálvölgyi, Claude Tardif +1
Homomorphism duality pairs play crucial role in the theory of relational structures and in the Constraint Satisfaction Problem. The case where both classes are finite is fully char…
Density-based group testing
Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi +1
In this paper we study a new, generalized version of the well-known group testing problem. In the classical model of group testing we are given n objects, some of which are conside…
Majority and Plurality Problems
Dániel Gerbner, Gyula O. H. Katona, Dömötör Pálvölgyi +1
Given a set of n balls each colored with a color, a ball is said to be majority, k-majority, plurality if its color class has size larger than half of the number of balls, has size…