Publication list

Zoltán Király

REFEREED PAPERS:

D.A. Ferhat, Z. Király, A. Sebő, G. Stauffer: ,,How many matchings cover the nodes of a graph?”, Mathematical Programming, 203, (2024) pp. 271-284. doi: 10.1007/s10107-022-01804-9

Z. Füredi, A. Gyárfás, Z. Király: ,,Problems and results on 1-cross-intersecting set pair systems”, Combinatorics, Probability and Computing, 32(4), (2023) pp. 691-702. doi:10.1017/S0963548323000044

E. Csóka, Z.L. Blázsik, Z. Király, D. Lenger: ,,Upper bounds for the necklace folding problems”, Journal of Combinatorial Theory, Series B, 157, (2022) pp. 123-143. doi: 10.1016/j.jctb.2022.05.012

A. Pašić, J. Tapolcai, P. Babarczi, E.R. Bérczi-Kovács, Z. Király, L. Rónyai: ,,Minimum Cost Survivable Routing Algorithms for Generalized Diversity Coding”, IEEE/ACM Transactions on Networking, 28(1), (2020) pp. 289-300. doi: 10.1109/TNET.2019.2963574

Z. Király: ,,Spanning tree with lower bound on the degrees”, Discrete Applied Mathematics, 242 (2018) pp. 82-88. doi: 10.1016/j.dam.2017.12.005

Z. Király, L. Tóthmérész: ,,On Ryser’s Conjecture for t-Intersecting and Degree-Bounded Hypergraphs”, Electronic Journal of Combinatorics, 24(4), art. no. #P4.40 (2017).

E. R. Bérczi-Kovács, Z. Király: ,,Optimal and heuristic network coding algorithms for multi-layered video broadcast”, Networks, online (2017). doi: 10.1002/net.21788

Prelimiary version: Z. Király, E. R. Kovács: ,,A Network Coding Algorithm for Multi-Layered Video Streaming”, International Symposium on Network Coding, NETCOD 2011 - Proceedings. (2011), pp. 1-7. doi: 10.1109/ISNETCOD.2011.5978943

 http://ieeexplore.ieee.org/xpl/freeabs all.jsp?arnumber=5978943&
 abstractAccess=no&userType=inst

A. Gyárfás, Z. Király: ,,Covering complete partite hypergraphs by monochromatic components”, Discrete Mathematics, 340 (2017) pp. 2753-2761. doi: 10.1016/j.disc.2017.08.014 A. Pašić, J. Tapolcai, P. Babarczi, E.R. Bérczi-Kovács, Z. Király, L. Rónyai:

,,Survivable Routing Meets Diversity Coding”, 14th International IFIP TC6 Networking Conference, Networking 2015, Toulouse, France, May 20-22 (2015),

http://dl.ifip.org/db/conf/networking/networking2015/1570066261.pdf

Z. Király, E. R. Kovács: ,,Randomized and Deterministic Algorithms for Network Coding Problems in Wireless Networks”, Information Processing Letters, 115 (2015), pp. 507-511. doi: 10.1016/j.ipl.2014.11.012

Prelimiary version: Z. Király, E. R. Kovács: ,,Deterministic network coding algorithms and applications for wireless networks”, International Symposium on Network Coding, NETCOD 2012 - Proceedings. (2012), pp. 103-107 doi: 10.1109/NETCOD.2012.6261892

 http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6261892

A. Bernáth, Z. Király: ,,On the tractability of some natural packing, covering and partitioning problems”, Discrete Applied Mathematics, 180 (2015), pp. 25-36. doi: 10.1016/j.dam.2014.07.028

Z. Király: ,,Shortest Paths in Nearly Conservative Digraphs”, Parameterized and Exact Computation – IPEC 2014 Wroclaw, LNCS 8894, (2014), pp. 234–245. doi: 10.1007/978-3-319-13524-3 20

Z. Király: ,,Monochromatic components in edge-colored complete uniform hypergraphs”, European Journal of Combinatorics 35 (2014), pp. 374-376 doi: 10.1016/j.ejc.2013.06.040

Prelimiary version: Z. Király: ,,Monochromatic components in edge-colored complete uniform hypergraphs”, Electronic Notes in Discrete Mathematics 38C (2011), pp. 517-521 doi: 10.1016/j.endm.2011.09.084

Z. Király: ,,Linear Time Local Approximation Algorithm for Maximum Stable Marriage”, Algorithms, 6(3) (2013), pp. 471-484. doi: 10.3390/a6030471

Prelimiary version: Z. Király: ,,Linear time local approximation algorithm for maximum stable marriage”, MATCH-UP 2012: the Second International Workshop on Matching Under Preferences, Budapest (2012), pp. 99-110.

 econ.core.hu/file/download/proceedings.pdf

P. L. Erdős, Z. Király, I. Miklós: ,,On the swap-distances of different realizations of a graphical degree sequence”, Combinatorics, Probability and Computing, 22, 03 (2013), pp. 366-383.

Z. Király, Z. L. Nagy, D. Pálvölgyi, M. Visontai: ,,On families of weakly cross-intersecting set-pairs”, Fundamenta Informaticae, 117 (2012), pp. 189-198 doi: 10.3233/FI-2012-695

Z. Király, P. Kovács: ,,Efficient implementations of minimum-cost flow algorithms”, Acta Universitatis Sapientiae, Informatica, 4, 1 (2012), pp. 67-118

http://www.acta.sapientia.ro/acta-info/informatica-main.htm

Z. Király, J. Szabó: ,,Induced graph packing problems”, Graphs and Combinatorics, 26 Issue 2 (2010), pp. 243-257 doi: 10.1007/s00373-010-0906-0

Z. Király, B. Cosh, B. Jackson: ,,Local connectivity augmentation in hypergraphs is NP-complete”, Discrete Applied Mathematics, 158 (2010), pp. 723-727. doi: 10.1016/j.dam.2009.12.011

Z. Király: ,,Better and Simpler Approximation Algorithms for the Stable Marriage Problem”, Algorithmica, 60 (1), doi: 10.1007/s00453-009-9371-7, (2009 (online), 2011), pp. 3-20

Prelimiary version: Z. Király: ,,Better and Simpler Approximation Algorithms for the Stable Marriage Problem”, ESA 2008, Lecture Notes in Computer Science 5193, (2008), pp. 623-634

A. Bernáth, S. Iwata, T. Király, Z. Király, Z. Szigeti: ,,Recent results on well-balanced orientations”, Discrete Optimization 5, (2008), pp. 663-676 doi: 10.1016/j.disopt.2008.03.001

A. Frank, Z. Király, B. Kotnyek: ,,An Algorithm for Node-Capacitated Ring Routing”, Operations Research Letters, 35, Issue 3, (2007), pp. 385-391

Prelimiary version: A. Frank, Z. Király, B. Kotnyek: ,,An Algorithm for Node-Capacitated Ring Routing”, Lecture Notes in Computer Science 3669, (2005), Algorithms – ESA 2005, eds: G. S. Brodal, S. Leonardi, (2005), pp. 249-258

Z. Király, Z. Szigeti: ,,Simultaneous well-balanced orientations of graphs”,

JCT B 96 Issue 5, (2006), pp. 684-692 V. Grolmusz, Z. Király: ,,Generalized Secure Routerless Routing”, Lecture

Notes in Computer Science 3421, Networking - ICN 2005, part II, eds: P. Lorenz, P. Dini, (2005), pp. 454-462

M. Kano, G. Y. Katona, Z. Király: ,,Packing paths of length at least two”,

Discrete Mathematics 283 (2004), pp. 129-135. V. Grolmusz, Z. Király: ,,Secure Routerless Routing”, Proceedings of ACM

SIGCOMM 2004 Workshops (2004), pp. 21-27 A. Frank, T. Király, Z. Király: ,,On the orientation of graphs and hyper-

graphs”, Discrete Applied Mathematics 131 (2003), pp. 385-400 A. Frank, Z. Király: ,,Graph Orientations with Edge-connection and Parity

Contstraints”, Combinatorica 22 (2002), pp. 47-70

Prelimiary version: A. Frank, Z. Király: ,,Parity constrained k-edge-connected orientations”, Integer Programming and Combinatorial Optimization, eds: G. Cornuéjols, R. Burkard, G. J. Woeginger, LNCS 1610 (1999), pp. 191-201.

Gy. Elekes, Z. Király: ,,On the Combinatorics of Projective Mappings”, Jour-

nal of Algebraic Combinatorics 14 (2001), pp. 183-197 B. G. Józsa, Z. Király, G. Magyar, Á. Szentesi: ,,An Efficient Algorithm for Global Path Optimization in MPLS Networks”, Optimization and Engineering 2 (2001), pp. 321-347

A. Benczúr, J. Förster, Z. Király: ,,Dilworth’s theorem and its application for path systems of a cycle—implementation and analysis.”, Algorithms— ESA ’99, ed: Jaroslav Nešetřil, LNCS 1643 (1999), pp. 498-509

B. Guiduli, Z. Király: ,,On intersecting hypergraphs”, Discrete Mathematics

182 (1998), pp. 139-151 A. Gyárfás, Z. Király, J. Lehel: ,,On-line 3- chromatic graphs. I. Triangle–

free graphs.”, SIAM J. Discr. Math. 12 (1999), pp. 385-411 A. Gyárfás, Z. Király, J. Lehel: ,,On-line 3- chromatic graphs. II. Critical

graphs.”, Discrete Mathematics 177 (1997), pp. 99-122

Prelimiary version: A. Gyárfás, Z. Király, J. Lehel: ,,On-line graph coloring and finite basis problems”, Combinatorics, Paul Erdős is Eighty, Volume 1, (1993), pp. 207-214

Book Chapter:

Z. Király: ,,Simpler Approximation for Stable Marriage”, In Kao M-Y (Ed) Encyclopedia of Algorithms, pp. 1986–1988, Springer New York (2016) doi: 10.1007/978-3-642-27848-8 676-1

PATENT:

Á. Szentesi, G. Magyar, Z. Király: ,,Network topologies”, patent no: US2004017783

Selected Technical Reports:

Z. Király: ,,Spanning tree with lower bound on the degrees”, Egres Tech. Reports, TR-2015-04 (2015),

http://www.cs.elte.hu/egres/www/tr-15-05.html

Z. Király, S. Kisfaludi-Bak: ,,A succinct tree coding for greedy navigation”, Egres Tech. Reports, TR-2015-02 (2015),

http://www.cs.elte.hu/egres/www/tr-15-02.html

Z. Király, S. Kisfaludi-Bak: ,,Dual-Critical Graphs – Notes on parity constrained acyclic orientations”, Egres Tech. Reports, TR-2012-07 (2012),

http://www.cs.elte.hu/egres/www/tr-12-07.html

Z. Király: ,,Recognizing graphic degree sequences and generating all realizations”, Egres Tech. Reports, TR-2011-11 (2012),

http://www.cs.elte.hu/egres/www/tr-11-11.html

Z. Király: ,,Restricted t-matchings in Bipartite Graphs”, Egres Quick Proofs, QP-2009-04 (2001, 2009),

http://www.cs.elte.hu/egres/www/qp-09-04.html

Z. Király: ,,Maximum Number of Cycles and Hamiltonian Cycles in Sparse Graphs”, Egres Tech. Reports, TR-2009-03 (2009),

http://www.cs.elte.hu/egres/www/tr-09-03.html

Z. Király: ,,λ-supermodular functions and dual packing theory”, Egres Tech. Reports, TR-2007-02 (2007),

http://www.cs.elte.hu/egres/www/tr-07-02.html

Z. Király, Z. Szigeti: ,,Reliable Orientations of Eulerian Graphs”, Egres Tech. Reports, TR-2006-01 (2006),

http://www.cs.elte.hu/egres/www/tr-06-01.html

Z. Király: ,,An O(n^{2}) algorithm for ring routing”, Egres Tech. Reports, TR-2005-

10 (2005), http://www.cs.elte.hu/egres/www/tr-05-10.html

Z. Király: ,,C_{4}-free 2-factors in bipartite graphs”, Egres Tech. Reports, TR-2001-

13 (2001), http://www.cs.elte.hu/egres/www/tr-01-13.html

Z. Király: ,,The Calculus of Barriers”, ELTE-Math, TR-9801-2 (1998),

http://www.cs.elte.hu/tr97/

A. Gyárfás, Z. Király, J. Lehel: ,,On-line Competitive Coloring Algorithms”,

ELTE-Math, TR-9703-1 (1997), http://www.cs.elte.hu/tr97/