Judit Nagy-György
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Judit Nagy-György has a total of 29 co-authors. Here are the top co-authors by number of shared publications:
Cs. Imreh
4 shared publications- Szabolcs Iván
University of Szeged
3 shared publications - Chuanqi Xiao
Central European University Budapest
2 shared publications Csanád Imreh
Department of Informatics, University of Szeged, Szeged, Árpád tér 2, H-6720, Hungary
2 shared publications- Csanád Imreh
University of Szeged
2 shared publications - Debarun Ghosh
Central European University Budapest
2 shared publications
Latest Publications
- Open Access
- 7 December 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (3)
Book free 3-uniform hypergraphs
- 7 December 2023
- Published by Elsevier in Discrete Mathematics
- Vol. 347 (3)
Open AccessBook free 3-uniform hypergraphs
- Open Access
Book free $3$-Uniform Hypergraphs
A $k$-book in a hypergraph consists of $k$ Berge triangles sharing a common edge. In this paper we prove that the number of the hyperedges in a $k$-book-free 3-uniform hypergraph on $n$ vertices is at most $\frac{n^2}{8}(1+o(1))$.Open AccessBook free $3$-Uniform Hypergraphs
A $k$-book in a hypergraph consists of $k$ Berge triangles sharing a common edge. In this paper we prove that the number of the hyperedges in a $k$-book-free 3-uniform hypergraph on $n$ vertices is at most $\frac{n^2}{8}(1+o(1))$. - 1 January 2018
- Published by University of Szeged in Acta Cybernetica
- Vol. 23 (3) , 929-938
On the Advice Complexity of Coloring Bipartite Graphs and Two-Colorable Hypergraphs
- 1 January 2018
- Published by University of Szeged in Acta Cybernetica
- Vol. 23 (3) , 929-938
On the Advice Complexity of Coloring Bipartite Graphs and Two-Colorable Hypergraphs
- 1 August 2016
- Published by Elsevier in Theoretical Computer Science
- Vol. 640, 94-103
New models of graph-bin packing
- 1 August 2016
- Published by Elsevier in Theoretical Computer Science
- Vol. 640, 94-103
New models of graph-bin packing
- 1 January 2016
- Published by University of Szeged in Acta Cybernetica
- Vol. 22 (3) , 687-701
On Nonpermutational Transformation Semigroups with an Application to Syntactic Complexity
- 1 January 2016
- Published by University of Szeged in Acta Cybernetica
- Vol. 22 (3) , 687-701
On Nonpermutational Transformation Semigroups with an Application to Syntactic Complexity
- Open Access
- 1 June 2015
- Published by Springer Nature in Acta Universitatis Sapientiae, Informatica
- Vol. 7 (1) , 5-17
Online hypergraph coloring with rejection
In this paper we investigate the online hypergraph coloring problem with rejection, where the algorithm is allowed to reject a vertex instead of coloring it but each vertex has a penalty which has to be paid if it is not colored. The goal is to minimize the sum of the number of the used colors for the accepted vertices and the total penalty paid for the rejected ones. We study the online problem which means that the algorithm receives the vertices of the hypergraph in some order v 1, . . . , vn and it must decide about vi by only looking at the subhypergraph Hi = (Vi , Ei ) where Vi = {v 1, . . . , vi } and E i contains the edges of the hypergraph which are subsets of Vi . We consider two models: in the full edge model only the edges where each vertex is accepted must be well-colored, in the trace model the subsets of the edges formed by the accepted vertices must be well colored as well. We consider proper and conflict free colorings. We present in each cases optimal online algorithms in the sense that they achieve asymptotically the smallest possible competitive ratio.
- 1 June 2015
- Published by Springer Nature in Acta Universitatis Sapientiae, Informatica
- Vol. 7 (1) , 5-17
Open AccessOnline hypergraph coloring with rejection
In this paper we investigate the online hypergraph coloring problem with rejection, where the algorithm is allowed to reject a vertex instead of coloring it but each vertex has a penalty which has to be paid if it is not colored. The goal is to minimize the sum of the number of the used colors for the accepted vertices and the total penalty paid for the rejected ones. We study the online problem which means that the algorithm receives the vertices of the hypergraph in some order v 1, . . . , vn and it must decide about vi by only looking at the subhypergraph Hi = (Vi , Ei ) where Vi = {v 1, . . . , vi } and E i contains the edges of the hypergraph which are subsets of Vi . We consider two models: in the full edge model only the edges where each vertex is accepted must be well-colored, in the trace model the subsets of the edges formed by the accepted vertices must be well colored as well. We consider proper and conflict free colorings. We present in each cases optimal online algorithms in the sense that they achieve asymptotically the smallest possible competitive ratio.
- 1 August 2014
- Published by Elsevier in Discrete Optimization
- Vol. 13, 1-15
The online-server problem with rejection- 1 August 2014
- Published by Elsevier in Discrete Optimization
- Vol. 13, 1-15
The online-server problem with rejection- 1 January 2014
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 174-185
Biclique Coverings, Rectifier Networks and the Cost of ε-Removal
- 1 January 2014
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 174-185
Biclique Coverings, Rectifier Networks and the Cost of ε-Removal
- 23 May 2013
- Published by Springer Nature in Algorithmica
- Vol. 71 (2) , 279-306
Online File Caching with Rejection Penalties
- 23 May 2013
- Published by Springer Nature in Algorithmica
- Vol. 71 (2) , 279-306
Online File Caching with Rejection Penalties
- 1 December 2011
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 22 (08) , 1971-1993
THE GRAPH-BIN PACKING PROBLEM
We deal with a very general problem: a given graph G is to be "packed" into a host graph H, and we are asked about some natural optimization questions concerning this packing. The problem has never been investigated before in this general form. The input of the problem is a simple graph G = (V, E) with lower and upper bounds on its edges and weights on its vertices. The vertices correspond to items which have to be packed into the vertices (bins) of a host graph, such that each host vertex can accommodate at most L weight in total, and if two items are adjacent in G, then the distance of their host vertices in H must be between the lower and upper bounds of the edge joining the two items. Special cases are bin packing with conflicts, chromatic number, and many more. We give some general structure statements, treat some special cases, and investigate the performance guarantee of polynomial-time algorithms both in the offline and online setting.
- 1 December 2011
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 22 (08) , 1971-1993
THE GRAPH-BIN PACKING PROBLEM
We deal with a very general problem: a given graph G is to be "packed" into a host graph H, and we are asked about some natural optimization questions concerning this packing. The problem has never been investigated before in this general form. The input of the problem is a simple graph G = (V, E) with lower and upper bounds on its edges and weights on its vertices. The vertices correspond to items which have to be packed into the vertices (bins) of a host graph, such that each host vertex can accommodate at most L weight in total, and if two items are adjacent in G, then the distance of their host vertices in H must be between the lower and upper bounds of the edge joining the two items. Special cases are bin packing with conflicts, chromatic number, and many more. We give some general structure statements, treat some special cases, and investigate the performance guarantee of polynomial-time algorithms both in the offline and online setting.