19 citations · 88 across the 21 of their papers we have counts for
21 papers
Constructing and sampling partite, -uniform hypergraphs with given degree sequence
Andras Hubai, Tamas Robert Mezei, Ferenc Beres +2
Partite, -uniform hypergraphs are -uniform hypergraphs in which each hyperedge contains exactly one point from each of the disjoint vertex classes. We consider the degree…
On the Small Quasi-kernel conjecture
Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei +2
An independent vertex subset of the directed graph is a kernel if the set of out-neighbors of is . An independent vertex subset of is a quasi-k…
Covering simple orthogonal polygons with -stars
Tamás Róbert Mezei
We solve the -star covering problem in simple orthogonal polygons, also known as the point guard problem in simple orthogonal polygons with rectangular vision, in quadratic time…
Minimizing interference-to-signal ratios in multi-cell networks
Péter L. Erdős, Tamás Róbert Mezei
In contemporary wireless communication networks, base-stations are organized into coordinated clusters (called cells) to jointly serve the users. However, such fixed systems are pl…
The sequence of prime gaps is graphic
Péter L. Erdős, Gergely Harcos, Shubha R. Kharel +3
Let us call a simple graph on vertices a prime gap graph if its vertex degrees are and the first prime gaps. We show that such a graph exists for every large $n…
Approximate Sampling of Graphs with Near--stable Degree Intervals
Péter L. Erdős, Tamás Róbert Mezei, István Miklós
The approximate uniform sampling of graph realizations with a given degree sequence is an everyday task in several social science, computer science, engineering etc. projects. One…
New results on graph matching from degree preserving growth
Péter L. Erdős, Shubha R. Kharel, Tamás Róbert Mezei +1
The recently introduced \emph{Degree Preserving Growth} model (Nature Physics, \DOI{10.1038/s41567-021-01417-7}) uses matchings to insert new vertices of prescribed degrees into th…
Degree-preserving graph dynamics -- a versatile process to construct random networks
Péter L. Erdős, Shubha R. Kharel, Tamás R. Mezei +1
Real-world networks evolve over time via additions or removals of vertices and edges. In current network evolution models, vertex degree varies or grows arbitrarily. A recently int…
Algorithms for Interference Minimization in Future Wireless Network Decomposition
Péter L. Erdős, Tamás Róbert Mezei, Yiding Yu +3
We propose a simple and fast method for providing a high quality solution for the sum-interference minimization problem. As future networks are deployed in high density urban areas…
Rooted NNI moves on tree-based phylogenetic networks
Péter L. Erdős, Andrew Francis, Tamás Róbert Mezei
We show that the space of rooted tree-based phylogenetic networks is connected under rooted nearest-neighbour interchange (rNNI) moves.
Half-graphs, other non-stable degree sequences, and the switch Markov chain
Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei +2
One of the simplest methods of generating a random graph with a given degree sequence is provided by the Monte Carlo Markov Chain method using switches. The switch Markov chain con…
The mixing time of the switch Markov chains: a unified approach
Péter L. Erdős, Catherine Greenhill, Tamás Róbert Mezei +3
Since 1997 a considerable effort has been spent to study the mixing time of switch Markov chains on the realizations of graphic degree sequences of simple graphs. Several results w…
Complexity of 2D bootstrap percolation difficulty: Algorithm and NP-hardness
Ivailo Hartarsky, Tamás Róbert Mezei
Bootstrap percolation is a class of cellular automata with random initial state. Two-dimensional bootstrap percolation models have three rough universality classes, the most studie…
Efficiently sampling the realizations of irregular, but linearly bounded bipartite and directed degree sequences
Péter L. Erdős, Tamás Róbert Mezei, István Miklós
Since 1997 a considerable effort has been spent on the study of the swap (switch) Markov chains on graphic degree sequences. Several results were proved on rapidly mixing Markov ch…
Extremal solutions to some art gallery and terminal-pairability problems
Tamás Róbert Mezei
The chosen tool of this thesis is an extremal type approach. The lesson drawn by the theorems proved in the thesis is that surprisingly small compromise is necessary on the efficac…
Mobile vs. point guards
Ervin Győri, Tamás Róbert Mezei
We study the problem of guarding orthogonal art galleries with horizontal mobile guards (alternatively, vertical) and point guards, using "rectangular vision". We prove a sharp bou…
Terminal-Pairability in Complete Bipartite Graphs with Non-Bipartite Demands
Lucas Colucci, Péter L. Erdős, Ervin Győri +1
We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on t…
Terminal-Pairability in Complete Bipartite Graphs
Lucas Colucci, Péter L. Erdős, Ervin Győri +1
We investigate the terminal-pairibility problem in the case when the base graph is a complete bipartite graph, and the demand graph is also bipartite with the same color classes. W…
Note on Terminal-Pairability in Complete Grid Graphs
Ervin Györi, Tamás Róbert Mezei, Gábor Mészáros
We affirmatively answer and generalize the question of Kubicka, Kubicki and Lehel concerning the path-pairability of high-dimensional complete grid graphs. As an intriguing by-prod…
Terminal-Pairability in Complete Graphs
Ervin Györi, Tamás Róbert Mezei, Gábor Mészáros
We investigate terminal-pairability properties of complete graphs and improve the known bounds in two open problems. We prove that the complete graph on vertices is termi…
Partitioning orthogonal polygons into at most 8-vertex pieces, with application to an art gallery theorem
Ervin Győri, Tamás Róbert Mezei
We prove that every simply connected orthogonal polygon of vertices can be partitioned into (simply connected) orthogonal polygons…