Random Discrete Structures
Random discrete structures have been extensively studied during the last few decades and have become one of the central themes of contemporary mathematics. The most important and popular example of random discrete structures is random graphs. Since the seminal work of Erdős and Rényi on the standard random graph, various random graph models are introduced and studied. The intense study of random graphs and random graph processes has brought together different fields such as discrete mathematics, probability theory, theoretical computer science and statistical physics. Our research is centered around phase transitions in random graphs and random graph processes with constraints.
- Keywords: random graphs, random graph processes, random graphs with constraints, probabilistic graph theory, phase transitions
- Institute's members working on this area: Mihyun Kang, Christoph Koch, Tamas Makai, Angélica Pachón, Philipp Sprüssel
Discrete and Combinatorial Optimization
In discrete and combinatorial optimization one aims at selecting an optimal solution from a set of feasible solutions. The working group on combinatorial optimization at the TU Graz has paid particular attention to the following areas during the last years: (1) Investigation of efficiently solvable special cases of NP-hard optimization problems, e.g. of location problems, non-linear assignment problems, travelling salesman problems, scheduling problems and packing problems. (2) Investigation of complex real-world optimization problems, such as a combined location-transportation problem, production planning problems from chemical industry and cutting problems from paper industry. Apart from the topics mentioned above many other problem classes from combinatorial optimization have been investigated by the discrete optimization group during recent years.
- Keywords: NP-hard problems, approximation algorithms, assignment problems, complex real-world problems, efficiently solvable special cases
- Institute's members working on this area: Rainer Burkard, Ante Ćustić, Eranda Dragoti-Çela, Bettina Klinz, Johannes Hatzl
Structural, Enumerative and Algorithmic Aspects of Graphs
Classes of graphs that have attracted much attention during recent years are graphs with constraints, such as the class of graphs on surfaces, minor-closed classes and the class of graphs with forbidden subgraphs. The members of the institute investigate enumerative, algorithmic and structural aspects of such graph classes. In view of recent results on asymptotic enumeration (and random generation) of graphs with contraints, an essential step is constructive decompositions of graphs into smaller building-blocks. Such decompositions can be interpreted as functional operations of generating functions which encode the enumerative information of graphs. Singularity analysis can then be applied to extract asymptotic behaviour of the number of graphs. Another successful approach for the asymptotic enumeration of maps and graphs on surfaces is the Gaussian matrix integral method from theoretical physics.
- Keywords: graphs on surfaces, minor-closed classes, singularity analysis, structural graph theory, matrix integral methods
- Institute's members working on this area: Mihyun Kang, Christoph Koch, Philipp Sprüssel
Asymptotic and Probabilistic Analysis of Algorithms
The aim of “Analysis of Algorithms”, a term coined by Donald Knuth, is to precisely analyse various algorithms in an asymptotic and probabilistic sense. Apart from the average behaviour for large values of the parameter, limiting distributions of quantities describing the algorithms are also of interest. Specifically, we focus on the design and the analysis of algorithms (1) for efficient computations in Abelian groups, e.g. in public key cryptography and (2) for efficient generation of combinatorial structures, e.g. Boltzmann Sampler.
- Keywords: analysis of algorithms, digital expansions, public-key cryptography, elliptic curve cryptosystems, Boltzmann sampler
- Institute's members working on this area: Clemens Heuberger, Mihyun Kang, Daniel Krenn