Discrete mathematics comprises various branches of mathematics where discrete (in contrast to continuous) questions are investigated. Optimization deals with finding minimal or maximal values of certain parameters with given constraints, e.g. finding shortest paths in a given road network. Among the topics covered by our working group are graph theory, convex and semidefinite optimization, asymptotic and probabilistic analysis of algorithms, applied abstract algebra and cryptography.

Discrete problems, e.g. in the context of combinatorial optimization or in theoretical chemistry can frequently be modelled by graphs consisting of vertices and edges. Specifically, we are working on the algorithmic treatment of large-scale NP-hard graph optimization problems and on characterizing extremal graphs with respect to various indices such as the Wiener index, Hosoya index or the Merrifield-Simmons index.

Convex optimization provides powerful tools to get approximations of discrete optimization problems. Semidefinite optimization as a generalization of Linear Programming has turned out to yield natural relaxations of many graph problems

where the objective is to partition the vertices in a specified way, so as to optimize over the edges joining distinct partition blocks. These relaxations can be tightened by combinatorial cutting planes. The resulting semidefinite programs may get rather large, so that standard algorithms cannot be applied any more. We focus on the development of algorithms also capable to handle large-scale instances.

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 for efficient computations in abelian groups, e.g. in public-key cryptography.

The purpose of Cryptography is to protect sensitive information, such as electronic funds transfers, credit card numbers etc., which is sent over an insecure channel, e.g. the internet, by encryption. This includes the case where a common secret key is known to both sender and recipient (symmetric cryptography) and the case where this is not the case (asymmetric cryptography), as in the context of e-commerce. Specifically, we focus on the development, security analysis and implementation of cryptographic algorithms based on finite structures, e.g. finite fields, finite residue class rings or elliptic curves.

© 2009 Alpen-Adria-Universität Klagenfurt | Publication details | Contact | Disclaimer

Responsibility for content: TEWI - Web Administrator

Requests to: TEWI - Web Editor

Responsibility for content: TEWI - Web Administrator

Requests to: TEWI - Web Editor