Publications of Tamás Király

 

Published and submitted papers

T. Király, Zs. Mészáros-Karkus, Finding strongly popular b-matchings in bipartite graphs, accepted to EUROCOMB, EGRES Technical Report no. 2017-04.

K. Bérczi, K. Chandrasekaran, T. Király, E. Lee, C. Xu, Global and fixed-terminal cuts in digraphs, submitted to APPROX, arXiv link.

K. Bérczi, T. Király, Y. Kobayashi, Covering intersecting bi-set families under matroid constraints, SIAM Journal on Discrete Mathematics 30 (2016), 1758-1774, DOI link. Preliminary version: EGRES Technical Report no. 2013-06.

T. Király, Base polyhedra and the linking property, to appear in Journal of Combinatorial Optimization, EGRES Technical Report no. 2016-06.

A. Bernáth, T. Király, Blocking optimal k-arborescences, Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (2016), 1682-1694, DOI link, EGRES Technical Report no. 2015-09.

S. Fujishige, T. Király, K. Makino, K. Takazawa, S. Tanigawa, Minimizing submodular functions on diamonds via generalized fractional matroid matchings, submitted, EGRES Technical Report no. 2014-14.

T. Király, J. Pap, An extension of Lehman's theorem and ideal set functions, Discrete Applied Mathematics 209 (2016), 251-263 DOI link. Preliminary version: EGRES Technical Report no. 2013-09.

A. Frank, T. Király, J. Pap, D. Pritchard, Characterizing and recognizing generalized polymatroids, Mathematical Programming, Volume 146, Issue 1-2 (2014), pp 245-273, journal link. Preliminary version: EGRES Technical Report no. 2012-03

T. Király, J. Pap, PPAD-completeness of polyhedral versions of Sperner's Lemma, Discrete Mathematics 313:15 (2013), 1594-1599, journal link, EGRES link.

T. Király, J. Pap, Stable multicommodity flows, Algorithms 6:1 (2013), 161-168, journal link (open access).

T. Király, L.C. Lau, M. Singh, Degree bounded matroids and submodular flows, Combinatorica 32 (2012), 703-720, journal link .

A. Bernáth, T. Király, A unifying approach to splitting-off, Combinatorica 32 (2012), 373-401. Preliminary version: EGRES Technical Report no. 2008-02.

A. Bernáth, T. Király, E.R. Kovács, G. Mádi-Nagy, Gy. Pap, J. Pap, J. Szabó, L. Végh, Algorithms for multiplayer multicommodity flow problems, Central European Journal of Operations Research 21 (2013), 699-712. Preliminary version: EGRES Technical Report no. 2012-09.

N.J.A. Harvey, T. Király, L.C. Lau, On disjoint common bases in two matroids, SIAM Journal on Discrete Mathematics 25 (2011), 1792-1803. (Preliminary version: EGRES Technical Report no. 2010-10.)

T. Király, L.C. Lau, Degree bounded forest covering, Proceedings of 15th International Conference IPCO 2011, LNCS 6655 (2011), 315-323. (Preliminary version: EGRES Technical Report no. 2010-08.)

T. Király, J. Pap, Ideal set functions, 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Kyoto (2011), 332-340.

T. Király, A. Bernáth, L. Végh, L. Bajzik, E. Kovács, K. Bérczi, A. Jüttner, T. Jordán, Worst case bin packing for OTN electrical layer networks dimensioning, 13th International Conference on Transparent Optical Networks (2011), journal link.

T. Király, J. Pap, A note on kernels and Sperner's Lemma, Discrete Applied Mathematics, Volume 157, Issue 15 (2009), 3327-3331.

A. Bernáth, T. Király, Covering skew-supermodular functions by hypergraphs of minimum total size, Operations Research Letters, Volume 37, Issue 5 (2009), 345-350.

T. Király, J. Pap, Kernels, stable matchings, and Scarf's Lemma, RIMS Kôkyuroku Bessatsu B23 (2010), 131-145. (Preliminary version: EGRES Technical Report no. 2008-13)

A. Frank, T. Király, A survey on covering supermodular functions, in: Research Trends in Combinatorial Optimization, W.J. Cook, L. Lovász, J. Vygen, eds., Springer (2009), pp. 87-126.

T. Király, J. Szabó, A note on parity constrained orientations, Combinatorica Volume 29, Number 5 (2009), 619-628. (Preliminary version: EGRES Technical Report no. 2003-11.)

T. Király, L.C. Lau, Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs, Journal of Combinatorial Theory B 98 (2008), 1233-1252.

A. Bernáth, S. Iwata, T. Király, Z. Király, Z. Szigeti, Recent results on well-balanced orientations, Discrete Optimization 5 (2008), 663-676. (Preliminary version: EGRES Technical Report no. 2006-11)

T. Király, J. Pap, Total dual integrality of Rothblum's description of the stable marriage polyhedron, Mathematics of Operations Research 33(2) (2008), 283-290. (Preliminary version: EGRES Technical Report no. 2005-01)

T. Király, L.C. Lau, Tight Approximate Min-Max Relations for Steiner Rooted-Orientations of Graphs and Hypergraphs, Proceedings of 47th IEEE FOCS, 283-292. (Preliminary version: EGRES Technical Report no. 2006-13)

T. Király, M. Makai, On polyhedra related to even factors, Proc. IPCO X, LNCS 3064: 416-430, 2004. (Preliminary version: EGRES Technical Report no. 2003-09)

T. Király, Covering symmetric supermodular functions by uniform hypergraphs, Journal of Combinatorial Theory Series B 91 (2004), 185-200. (Preliminary version: EGRES Technical Report no. 2002-02)

A. Frank, T. Király, Combined connectivity augmentation and orientation problems, Discrete Applied Mathematics 131 (2003), 401-419. (Preliminary version: EGRES Technical Report no. 2001-07)

A. Frank, T. Király, Z. Király, On the orientation of graphs and hypergraphs, Discrete Applied Mathematics 131 (2003), 385-400. (Preliminary version: EGRES Technical Report no. 2001-06)

A. Frank, T. Király, M. Kriesell, On decomposing a hypergraph into k connected sub-hypergraphs, Discrete Applied Mathematics 131 (2003), 373-383. (Preliminary version: EGRES Technical Report no. 2001-02)

Technical reports and Quick proofs

T. Király, Zs. Mészáros-Karkus, Finding strongly popular matchings in certain bipartite preference systems, EGRES Technical Report no. 2016-16.

T. Király, J. Pap, Finding equilibria in linear service-providing games, EGRES Technical Report no. 2016-15.

K. Bérczi, T. Király, Y. Kobayashi, Algorithmic aspects of covering supermodular functions under matroid constraints, EGRES Technical Report no. 2015-05.

A. Bernáth, T. Király, L. Végh, Special skew-supermodular functions and a generalization of Mader's splitting-off theorem, EGRES Technical Report no. 2011-10.

T. Király, J. Pap, On the list colouring of two matroids, EGRES Quick Proof no. 2010-01.

T. Király, Computing the minimum cut in hypergraphic matroids, EGRES Quick Proof no. 2009-05.

T. Király, A result on crossing families of odd sets, EGRES Technical Report no. 2007-10.

T. Király, L.C. Lau, Degree constrained submodular flows, EGRES Technical Report no. 2007-09.

T. Király, Applications of Eulerian splitting-off, EGRES Technical Report no. 2007-01.

T. Király, Oriented matroids from set-pairs, EGRES Quick Proof no. 2006-02.

T. Király, Minimal feedback sets in binary oriented matroids, EGRES Quick Proof no. 2006-01.

T. Király, Merging hyperedges to meet edge-connectivity requirements, EGRES Technical Report no. 2005-08.

T. Király, M. Makai, A note on hypergraph connectivity augmentation, EGRES Technical Report no. 2002-11.


Theses

T. Király, Edge-connectivity of undirected and directed hypergraphs, Ph.D. dissertation (2004). PDF, ps.GZ, Errata.

T. Király, A leemelési művelet és alkalmazásai , M.Sc. thesis (1999, in Hungarian). Gzipped Postscript.


Papers in Hungarian

T. Király, Élösszefüggőség-növelés hiperélek összevonásával, Matematikai Lapok 13 (2007), 28-31. (in Hungarian)

T. Király, M. Makai, Irányított hipergráfok élösszefüggőség-növelése, Matematikai Lapok 13 (2007), 32-39. (in Hungarian)

T. Király, J. Szabó, Szupermoduláris függvényt fedő adott befok-paritású irányítások, Matematikai Lapok 13 (2007), 40-48. (in Hungarian)