4 papers
On Diophantine graphs
Gergő Batta, Lajos Hajdu, András Pongrácz
Diophantine tuples are of ancient and modern interest, with a huge literature. In this paper we study Diophantine graphs, i.e., finite graphs whose vertices are distinct positive i…
Finding cliques and dense subgraphs using edge queries
Endre Csóka, András Pongrácz
We consider the problem of finding a large clique in an Erdős--Rényi random graph where we are allowed unbounded computational time but can only query a limited number of edges. Re…
Generalized solution for the Herman Protocol Conjecture
Endre Csóka, Szabolcs Mészáros, András Pongrácz
The Herman Protocol Conjecture states that the expected time of Herman's self-stabilizing algorithm in a system consisting of identical processes organ…
Local algorithms for the maximum flow and minimum cut in bounded-degree networks
Endre Csóka, András Pongrácz
We show a deterministic constant-time local algorithm for constructing an approximately maximum flow and minimum fractional cut in multisource-multitarget networks with bounded deg…