# Department of Combinatorial Models and Algorithms

The Department of Combinatorial Models and Algorithms was founded in 1983. The research is concentrated mainly on combinatorial optimization and computational geometry. The department is headed by Ph.D. Vladimir Sarvanov.

## Staff

## Main Research Fields

- Optimization problems on permutations and graphs with emphasis on the linear and quadratic assignment problems, the traveling salesman problem, graph and hypergraph layout problems. Elaboration of approximate, heuristic and exact methods for solving these problems, investigation of polyhedral aspects and determination of efficiently solvable cases
- Enumerative and algebraic combinatorics for graphs and objects of topological and algebraic nature. In particular, enumeration of non-isomorphic maps on surfaces, coverings of topological surfaces and Seifert 3-manifolds, non-conjugate subgroups of finitely generated groups, circulant graphs and finite automata. Investigation of combinatorial sequences and combinatorial identities
- Research in combinatorial computational geometry. Problems on restricted-orientation convex sets including problems of recognition, separability, numerical characteristics, comparison of various types of restricted-orientation convexity, extremal points and optimization. Elaboration of methods for constructing triangulated surfaces with given properties in two-dimensional simplicial complex
- Research in graph theory: stability and hamiltonicity in regular graphs, noncrossing subgraph problems in topological and geometric graphs, realizations of hypergraphs by graphs with prescribed properties
- Metric theory of transcendental numbers: theory of extremal manifolds over the real, complex and p-adic fields, application of the Hausdorff dimension in the theory of Diophantine approximation, estimates for small denominators in incorrect problems of mathematical physics
- Number-theoretical algorithms (including prime-testing, factorization, discrete logarithm) and the applications to cryptology

## Applications

- computer-aided design of VLSI circuits
- image processing
- computer graphics