MTA ELTE Egervary Research Group

Budapest, Hungary

MTA ELTE Egervary Research Group

Budapest, Hungary

Time filter

Source Type

Berczi K.,MTA ELTE Egervary Research Group | Joo A.,MTA ELTE Egervary Research Group
Electronic Journal of Combinatorics | Year: 2017

An open conjecture of Erdős states that for every positive integer k there is a (least) positive integer f(k) so that whenever a tournament has its edges colored with k colors, there exists a set S of at most f(k) vertices so that every vertex has a monochromatic path to some point in S. We consider a related question and show that for every (finite or infinite) cardinal k > 0 there is a cardinal λk such that in every k-edge-coloured tournament there exist disjoint vertex sets K, S with total size at most λk so that every vertex v has a monochromatic path of length at most two from K to v or from v to S. © 2017, Australian National University. All rights reserved.


Fleiner T.,Budapest University of Technology and Economics | Fleiner T.,MTA ELTE Egervary Research Group | Janko Z.,Eötvös Loránd University
Order | Year: 2016

A recent result of Aharoni Berger and Gorelik (Order 31(1), 35–43, 2014) is a weighted generalization of the well-known theorem of Sands Sauer and Woodrow (Theory Ser. B 33(3), 271–275, 1982) on monochromatic paths. The authors prove the existence of a so called weighted kernel for any pair of weighted posets on the same ground set. In this work, we point out that this result is closely related to the stable marriage theorem of Gale and Shapley (Amer. Math. Monthly 69(1), 9–15, 1962), and we generalize Blair’s theorem by showing that weighted kernels form a lattice under a certain natural order. To illustrate the applicability of our approach, we prove further weighted generalizations of the Sands Sauer Woodrow result. © 2015, Springer Science+Business Media Dordrecht.


Cechlarova K.,University of P.J. Šafarik | Fleiner T.,Budapest University of Technology and Economics | Fleiner T.,MTA ELTE Egervary Research Group | Manlove D.F.,University of Glasgow | McBride I.,University of Glasgow
Theoretical Computer Science | Year: 2016

Several countries successfully use centralized matching schemes for school or higher education assignment, or for entry-level labour markets. In this paper we explore the computational aspects of a possible similar scheme for assigning teachers to schools. Our model is motivated by a particular characteristic of the education system in many countries where each teacher specializes in two subjects. We seek stable matchings, which ensure that no teacher and school have the incentive to deviate from their assignments. Indeed we propose two stability definitions depending on the precise format of schools' preferences. If the schools' ranking of applicants is independent of their subjects of specialism, we show that the problem of deciding whether a stable matching exists is NP-complete, even if there are only three subjects, unless there are master lists of applicants or of schools. By contrast, if the schools may order applicants differently in each of their specialization subjects, the problem of deciding whether a stable matching exists is NP-complete even in the presence of subject-specific master lists plus a master list of schools. Finally, we prove a strong inapproximability result for the problem of finding a matching with the minimum number of blocking pairs with respect to both stability definitions. © 2016 The Author(s).


Kiraly Z.,Eötvös Loránd University | Kiraly Z.,MTA ELTE Egervary Research Group | Kovacs E.R.,Eötvös Loránd University
Information Processing Letters | Year: 2015

Network coding is a method for information transmission in a network, based on the idea of enabling internal nodes to forward a function of the incoming messages, typically a linear combination. In this paper we discuss generalizations of the network coding problem with additional constraints on the coding functions called network code completion problem, NCCP. We give both randomized and deterministic algorithms for maximum throughput-achieving network code construction for the NCCP in the multicast case. We also introduce the related problem of fixable pairs, investigating when a certain subset of coding coefficients in the linear combination functions can be fixed to arbitrary non-zero values such that the network code can always be completed to achieve maximum throughput. We give a sufficient condition for a set of coding coefficients to be fixable. For both problems we present applications in different wireless and heterogeneous network models. © 2014 Elsevier B.V. All rights reserved.


Berczi K.,MTA ELTE Egervary Research Group | Bernath A.,MTA ELTE Egervary Research Group | Vizer M.,MTA Alfred Renyi Institute of Mathematics
Electronic Journal of Combinatorics | Year: 2015

An undirected simple graph G = (V,E) is called antimagic if there exists an injective function f: E → {1,…|E|} such that (formula presented) for any pair of different nodes u, v ∈ V. In this note we prove - with a slight modification of an argument of Cranston et al. - that k-regular graphs are antimagic for k ≥ 2. © 2015, Australian National University. All rights reserved.


Frank A.,Eötvös Loránd University | Frank A.,MTA ELTE Egervary Research Group | Kiraly C.,Eötvös Loránd University
Operations Research Letters | Year: 2013

A tree-composition is a tree-like family that serves to describe the obstacles to k-edge-connected orientability of mixed graphs. Here we derive a structural result on tree-compositions that gives rise to a simple algorithm for computing an obstacle when the orientation does not exist. As another application, we show a min-max theorem on the minimal in-degree of a given node set in a k-edge-connected orientation of an undirected graph. This min-max formula can be simplified in the special case of k=1. © 2013 Elsevier B.V. All rights reserved.

Loading MTA ELTE Egervary Research Group collaborators
Loading MTA ELTE Egervary Research Group collaborators