Discrete Mathematical Structures and Algorithms

Activity of the research laboratory

The members of the laboratory carry out theoretical research in several directions. Beside the structural and extremal study of discrete mathematical models—mostly graphs (networks) and hypergraphs—the algorithmic (time) complexity of combinatorial problems, approximability in discrete optimization, and competitive ratio of on-line scheduling are investigated.

Research results

Our research deals with various areas. Here we give some results as an appetizer; please see the web site of the laboratory for a more detailed description.
We have introduced a general model of hypergraph coloring and partitions of set systems. In a series of papers we work out the details of their theory. Along the way we have also solved some long-standing open problems on the subclass called C-coloring: we have determined the asymptotical minimum size of a k-uniform set system crossing all k-partitions (a problem that was unsolved since 1973) and characterized the structure of C-perfect hypertrees (solution of a conjecture from 1995, with surprising algorithmic consequences).
We have studied graph partitions from several aspects. We investigated edge-connectivity conditions on decompositions into K_{1,3} parts, and pointed out its close connection to questions on orientation and network flows (co-author: C. Thomassen). Further, we have proved complexity results concerning the existence of vertex partitions under degree constraints (co-authors: C. Bazgan and D. Vanderpooten).
Non-repetitive coloring of graphs was introduced as a generalization of Thue’s famous non-repetitive sequence. We proved that graphs of bounded treewidth can be colored with a bounded number of colors in this way (co-author: P. Varjú).
Solving a 20-year-old open problem, we have characterized the structure of networks in which every connected part has a “dominating” subnetwork with prescribed properties, from which all elements of the subnetwork can be reached.
We have designed on-line scheduling algorithms whose competitive ratio is better than that of previously known ones; moreover we have proved that, for several problems, suitably organized semi on-line algorithms are provably more efficient than what can be achieved by any purely on-line algorithm (co-authors: Y. He, resp. E. Angelelli and M. G. Speranza)


Introduction of the head

thumb tuzaZsolt Tuza is a mathematician (Master degree received at Eötvös Loránd University, Budapest, 1978; CSc [upper-equivalent to PhD] from the Hungarian Academy of Sciences, 1986), DSc (Hungar. Acad. Sci. 1992), Dr. Habil. In applied mathematics (Budapest Technical University, 1995), research professor (Computer and Automation Institute of the Hungarian Academy of Sciences, since 1993), full professor (University of Veszprém, resp. University of Pannonia, since 2001). He received First Prize at the International Mathematical Olympiad in 1972. He is the author of more than 300 publications, receiving more than 100 citations per year. He has many results in various fields, including extremal hypergraph theory, list coloring of graphs, structure of dominating subgraphs, color-bounded hypergraphs, semi on-line scheduling, and more. He is member of the editorial board of five international journals, regular invited speaker of international conferences on graph theory, member of the Board of Advisors of “Center of Excellence in Interdisciplinary Mathematics” (since 2008), president of Hereditarnia Club (2007—2008), and Patron of the Paul Erdős Talent Nurturing Program in Mathematics. Further information can be found at www.dcs.uni-pannon.hu/tuza/ 

the project is supported
hungarys renewal
szechenyi plan
Copyright © 2017 - University of Pannonia, Faculty of Information Technology

This site uses cookies. By continuing to browse the site, you are agreeing to our use of cookies. Find out more from cookie.