Viola Mészáros

Viola Mészáros

Auto-generated profile, based on publicly available information

Viola Mészáros

Bolyai Intézet Aradi vértanúk tere 1 6720 Szeged Hungary

Research Focus & Metrics

Academic Career Length

19Years (2008-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 July 2013 in Theoretical Computer Science
Verified
Journal Article
Closed access
JCJosef Cibulka
Josef Cibulka
JKJan Kynčl
Jan Kynčl
VMViola Mészáros
Viola Mészáros
RSRudolf Stolař
Rudolf Stolař
PVPavel Valtr
Pavel Valtr

27 October 2014
Verified
Thesis
Closed access
VMViola Mészáros
Viola Mészáros

1 January 2010
Verified
Book Chapter
Closed access
PDF file
JCJosef Cibulka
Josef Cibulka
RSRudolf Stolař
Rudolf Stolař
JKJan Kynčl
Jan Kynčl
VMViola Mészáros
Viola Mészáros
PVPavel Valtr
Pavel Valtr

3 March 2013 in arXiv
Verified
Preprint
Open access
PDF file
DGDániel Gerbner
Dániel Gerbner
VMViola Mészáros
Viola Mészáros
DPDömötör Pálvölgyi
Dömötör Pálvölgyi
APAlexey Pokrovskiy
Alexey Pokrovskiy
GRGünter Rote
Günter Rote
We study the discrete Voronoi game, where two players alternately claim vertices of a graph for t rounds. In the end, the remaining vertices are divided such that each player receives the vertices that are closer to his or her claimed vertices. We prove that there are graphs for which the second player gets almost all vertices in this game, but this is not possible for bounded-degree graphs. For trees, the first player can get at least one quarter of the vertices, and we give examples where she can get only little more than one third of them. We make some general observations, relating the result with many rounds to the result for the one-round game on the same graph.

4 February 2011 in arXiv
Verified
Preprint
Open access
PDF file
JCJosef Cibulka
Josef Cibulka
JKJan Kyncl
Jan Kyncl
VMViola Mészáros
Viola Mészáros
RSRudolf Stolar
Rudolf Stolar
PVPavel Valtr
Pavel Valtr
A set S of n points is 2-color universal for a graph G on n vertices if for every proper 2-coloring of G and for every 2-coloring of S with the same sizes of color classes as G has, G is straight-line embeddable on S. We show that the so-called double chain is 2-color universal for paths if each of the two chains contains at least one fifth of all the points, but not if one of the chains is more than approximately 28 times longer than the other. A 2-coloring of G is equitable if the sizes of the color classes differ by at most 1. A bipartite graph is equitable if it admits an equitable proper coloring. We study the case when S is the double-chain with chain sizes differing by at most 1 and G is an equitable bipartite graph. We prove that this S is not 2-color universal if G is not a forest of caterpillars and that it is 2-color universal for equitable caterpillars with at most one half non-leaf vertices. We also show that if this S is equitably 2-colored, then equitably properly 2-colored forests of stars can be embedded on it.

1 March 2012 in arXiv
Verified
Preprint
Open access
PDF file
JCJosef Cibulka
Josef Cibulka
JKJan Kynčl
Jan Kynčl
VMViola Mészáros
Viola Mészáros
RSRudolf Stolař
Rudolf Stolař
PVPavel Valtr
Pavel Valtr
We study the following combinatorial game played by two players, Alice and Bob, which generalizes the Pizza game considered by Brown, Winkler and others. Given a connected graph G with nonnegative weights assigned to its vertices, the players alternately take one vertex of G in each turn. The first turn is Alice's. The vertices are to be taken according to one (or both) of the following two rules: (T) the subgraph of G induced by the taken vertices is connected during the whole game, (R) the subgraph of G induced by the remaining vertices is connected during the whole game. We show that if rules (T) and/or (R) are required then for every epsilon > 0 and for every positive integer k there is a k-connected graph G for which Bob has a strategy to obtain (1-epsilon) of the total weight of the vertices. This contrasts with the original Pizza game played on a cycle, where Alice is known to have a strategy to obtain 4/9 of the total weight. We show that the problem of deciding whether Alice has a winning strategy (i.e., a strategy to obtain more than half of the total weight) is PSPACE-complete if condition (R) or both conditions (T) and (R) are required. We also consider a game played on connected graphs (without weights) where the first player who violates condition (T) or (R) loses the game. We show that deciding who has the winning strategy is PSPACE-complete.