Publications of Tamás Király

 

Published and submitted papers

T. Király, Y. Yokoi, Equitable Partitions into Matchings and Coverings in Mixed Graphs, 2018, arXiv link.

K. Bérczi, K. Chandrasekaran, T. Király, V. Madan, Improving the Integrality Gap for Multiway Cut, 2018, arXiv link.

K. Bérczi, K. Chandrasekaran, T. Király, E. Lee, C. Xu, Beating the 2-approximation factor for global bicut, Mathematical Programming, 2018, available online.

K. Bérczi, A. Bernáth, T. Király, Gy. Pap, Blocking optimal structures, Discrete Mathematics 341 (2018) 1864-1872. Technical report: EGRES Technical Report no. 2017-07.

K. Bérczi, K. Chandrasekaran, T. Király, V. Madan, A tight $\sqrt{2}$-approximation for Linear 3-Cut, Proc. SODA 2018, 1393-1406. Technical report: EGRES Technical Report no. 2017-10.

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

K. Bérczi, K. Chandrasekaran, T. Király, E. Lee, C. Xu, Global and fixed-terminal cuts in digraphs, arXiv link. Accepted to APPROX 2017 (extended abstract)

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, Journal of Combinatorial Optimization 36 (2018), 671-677, DOI link, 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, L. Lomoschitz, Profitability of the coin-hopping strategy, EGRES Quick Proof no. 2018-03.

T. Király, Zs. Mészáros-Karkus, Finding strongly popular matchings in certain bipartite preference systems, EGRES Technical Report no. 2016-16, 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications

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)