Projects / Programmes
Selected Topics in Theoretical Computer Science and Combinatorial Optimization
January 1, 2004
- December 31, 2008
| Code |
Science |
Field |
Subfield |
| 1.07.00 |
Natural sciences and mathematics |
Computer intensive methods and applications |
|
| 1.01.00 |
Natural sciences and mathematics |
Mathematics |
|
| Code |
Science |
Field |
| P170 |
Natural sciences and mathematics |
Computer science, numerical analysis, systems, control |
combinatorial optimization, algorithms on graphs, mathematical chemistry, data structures, analysis of networks, symbolic computation.
Researchers (29)
Organisations (1)
Abstract
Computationally intensive methods and applications can be found not only in natural sciences (biology, chemistry, physics), engineering (mechanical, civil, electrical), and economics (finance), but also in social sciences (sociology, anthropology), humanities (linguistics, history, genealogy, heraldics) and arts (film, music, painting, sculpture, architecture). All these areas share the need for computational power and efficient information processing methods. Our research includes design and development of methods and techniques for distributed computing based on efficient algorithms and robust data structures which are at the heart of a transparent environment for writing applications. Graph theory and group theory are used to help achieve the desired efficiency and robustness.
In the area of graphs and incidence structures we study problems related to combinatorial and geometric configurations, regular maps, forbidden minors for embedding graphs on the torus, graph drawings, and various types of eulerian walks.
In the area of numerical methods we study the space of splines over triangulations, geometric interpolation by parametric polynomial curves and surfaces, and methods for solving polynomial and multiparametric eigenvalue problems.
In the area of combinatorial optimization we are interested in applications to various disciplines ranging from mathematics and computer science to natural sciences such as chemistry, and humanities such as computational genealogy and heraldics.
With successful synthesis of larger molecules similar to geometric solids such as fullerenes, discrete mathematics and theoretical computer science have gained a new role of importance in theoretical chemistry. Over the years, our group has developed cooperation with leading chemists and physicists in this area, both at home and abroad. Our program system Vega (a software tool for synthesis and analysis of discrete mathematical objects, as well as for distributed management and development of projects over the internet) already contains about 2500 functions. Currently we are building a new version of Vega and adding new algorithms and new data structures such as configurations and oriented matroids.
In the area of clustering and network analysis we pay special attention to very large datasets (containing tens of thousands of units) and fast (subquadratic) algorithms for their analysis. In order to offer tools for informative and insightful presentation of data we are developing appropriate forms of 3D-visualization based on VRML (Virtual Reality Modeling Language). For certain problems such as block modeling in large networks, layered visualization of acyclic networks, and vertex colorings in graphs, no exact efficient algorithms are known. To cope with such problems, we are working on very fast approximate algorithms based on various heuristics.
When analyzing very large datasets and networks it is often convenient to break them down into several smaller, easier-to-manage parts. We are studying problems of dividing networks into subnetworks belonging to certain special families of graphs such as paths, trees, planar graphs, cubic graphs, etc. Based on such divisions, we expect to develop several efficient algorithms.
In the operationalization of various approaches to the analysis of datasets and networks, measures of dissimilarity play an important role. We continue our former investigations of how to use appropriate transformations to improve the quality of certain measures of dissimilarity, in particular dissimilarity measures on compositions.
In the area of symbolic computation we investigate algorithms for solving linear difference equations in several dimensions, and for evaluation of hypergeometric and related determinants in closed form.
Significance for science
Results of our work in the previous research period show a tight interconnection of our research group into the worldwide research. We publish our papers in the most influential scientific journals in many research areas, participate in the most important specialized international conferences, visit important foreign universities and scientific institutes, collaborate in international research and applicative projects. Many of our junior researchers have done at least part of their study at foreign universities of high quality. Our work is influential in the international research world and has plenty citations. We have an active collaboration with researchers from USA (Carnegie Mellon University, University of Pittsburgh, University of Pennsylvania, University of California Irvine, Temple University, Syracuse University, Colgate University, Drake University), Canada (University of Waterloo, Simon Fraser University), France (Universite de Marne-la-Vallee, INRIA Rocquencourt, INRIA Sophia-Antipoli, Universite Bordeaux I), Sweden (University of Technology, Lulea, Royal Institute of Technology, Stockholm), Austria (Montanuiversitaet Leoben, RISC Linz, University of Vienna, FAS research Vienna), Germany (FU Berlin, Universität Bielefeld, TU Darmstadt, Universität Lepzig), Russia (Moscow state university), Italy (University of Pisa, University of Udine), Norway (CMA, IFI, University of Oslo, University of Trondheim), Netherlands (University of Eindhoven), Croatia (Institute Rudjer Bošković, University of Zagreb, University of Split), United Kingdom (University of Edinburgh, University of Birmingham, University of Sheffield). We work on various interdisciplinary projects: with a group for analyzing social networks at FDV, Ljubljana, group for computer vision at FRI, Ljubljana, Institute of biophysics at MF, Ljubljana, Institute of chemistry, and Primorska institute for natural sciences and technology of Primorska University. Members of our research group collaborate in European research networks (e.g., PASCAL Network of excellence), in various bilateral research projects (with USA, Italy, Norway, Croatia) and in applicative projects such as Computer tools in the development of manufacturing programmes. Our work yields important results in applications of computationally intensive methods in theoretical computer science, analysis of large networks symbolic computations, problems in graph theory, numerical analysis and linear algebra, computer aided geometric design, combinatorial optimization, chemistry and bioinformatics. Many results have not only theoretical value, but can be applied in practice. We use this in transfer of knowledge from the scientific world into industry. For users outside scientific community the methodology of problem solving, mathematical modeling and design of computer algorithms and their implementation are of particular importance. We collaborate in technological developementwith some of the leading Slovenian companies (Gorenje, Mobitel, Iskratel). Also the human resources and their development are important. We enable our junior researchers connections with leading international researchers and teach them to become an important part of the scientific community. Our results can be easily empirically verified by the number of our papers and citations of our work.
Significance for the country
New algorithms and their implementations in symbolic computation and discrete and numerical mathematics enhance the efficiency and computing power of software tools in almost all areas of science and technology. The main impact of our research program on Slovenia can be divided into two groups: The development of the human potential: Our young researchers get the knowledge of the state-of-the-art in their respective fields. Some of them study abroad and work with the leading international authorities. All this will intensify international scientific cooperation and will help ensure a solid foundation and continued high standards of achievement in Slovenian science in the future. Applications and cooperation with potential users outside of the research community: Several members of our research programme collaborate in different applied projects in which they use in concrete situations the knowledge obtained in their fundamental research in the programme. Some of our researchers continue their careers outside of academia and transfer their acquired knowledge and skills (especially the problem-solving methodologies, but also their programming skills) to their working environment, thus intensifying the bonds between academia and the rest of society. Examples of our collaboration with different firms and institutions are Mobitel, Seaway - Elan, AMBIENT d.o.o., Ultra, XLab, RTV Slovenija, MZZ RS, MO RS and others. In spite of administrative difficulties, we try to include in our activity also top researchers from the industry. Group members have contributed new approaches to the analysis of large networks that can be directly employed in public administration and in other areas. Our aimed projects for the Ministry of Defense and Slovenian army deal mostly with logistic support and e-learning. Our projects in the area of e-learning will simplify the preparation of integral learning programs incorporating information-communication technologies and media and will thus contribute to their wider accessibility and also to improvement of computer literacy in general. In the project "Computer Tools in the Development of Manufacturing Programs - Part 2" (L1-7230), we design new generation CAD tools which will contribute to more effective and economical design of buildigs in modern urban development. In another project "L1-0696 - Digital archives for natural and cultural heritage" we will provide for clear cathegorisation of naural and cultural heritage, also increasing its accessibility to experts and general public. Finally, let us mention leading of the project "M6-0046 - Lieutenant colonel Jurij Vega - soldier and ballistics specialist", under which we have investigated and promoted the work of one of the Slovenia's most important early mathematicians. The know-how developed in our research programme is nowadays highly appreciated in global economy. Since the slovenian economy is involved in international activities it is extremely important that such knowledge is available to our companies, enhancing a faster and a more successful development.
Most important scientific results
Final report,
complete report on dLib.si
Most important socioeconomically and culturally relevant results
Final report,
complete report on dLib.si
