Loading...
Projects / Programmes source: ARIS

Selected Topics in Theoretical Computer Science and Combinatorial Optimization

Periods
Research activity

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 
Keywords
combinatorial optimization, algorithms on graphs, mathematical chemistry, data structures, analysis of networks, symbolic computation.
Evaluation (rules)
source: COBISS
Researchers (29)
no. Code Name and surname Research area Role Period No. of publicationsNo. of publications
1.  01467  PhD Vladimir Batagelj  Mathematics  Researcher  2004 - 2008  977 
2.  15854  PhD Andrej Bauer  Mathematics  Researcher  2004 - 2008  199 
3.  19284  PhD Marko Boben  Computer intensive methods and applications  Researcher  2004 - 2008  84 
4.  02017  PhD Matevž Bren  Mathematics  Researcher  2004 - 2008  291 
5.  04967  PhD Andrej Brodnik  Computer intensive methods and applications  Researcher  2004 - 2008  449 
6.  06895  PhD Izidor Hafner  Computer intensive methods and applications  Researcher  2007 - 2008  459 
7.  24421  PhD Boris Horvat  Computer intensive methods and applications  Junior researcher  2005 - 2008  143 
8.  20271  PhD Gašper Jaklič  Mathematics  Researcher  2004 - 2008  329 
9.  25380  PhD Stanislav Južnič  NCKS Research programme  Researcher  2005  625 
10.  23467  PhD Marjetka Knez  Mathematics  Junior researcher  2006 - 2008  193 
11.  12303  PhD Simona Korenjak Černe  Mathematics  Researcher  2004 - 2008  127 
12.  03425  PhD Jernej Kozak  Mathematics  Researcher  2006 - 2008  296 
13.  05952  MSc Matija Lokar  Mathematics  Technical associate  2008  416 
14.  26450  PhD Primož Lukšič  Computer intensive methods and applications  Junior researcher  2006 - 2008  96 
15.  28582  PhD Andrej Muhič  Mathematics  Junior researcher  2007 - 2008  32 
16.  09634  PhD Bojan Orel  Mathematics  Researcher  2007 - 2008  124 
17.  26533  PhD Igor Pesek  Educational studies  Junior researcher  2006 - 2008  212 
18.  01935  PhD Marko Petkovšek  Mathematics  Head  2004 - 2008  366 
19.  01941  PhD Tomaž Pisanski  Mathematics  Researcher  2004 - 2008  866 
20.  15136  PhD Bor Plestenjak  Mathematics  Researcher  2004 - 2008  163 
21.  28584  PhD Katja Prnaver  Computer intensive methods and applications  Junior researcher  2007 - 2008  50 
22.  03231  PhD Marko Razpet  Mathematics  Researcher  2007 - 2008  788 
23.  21773  PhD Helena Zakrajšek  Mathematics  Researcher  2005 - 2008  27 
24.  07081  PhD Aleš Založnik  Mathematics  Researcher  2006 - 2008  75 
25.  15137  PhD Matjaž Zaveršnik  Mathematics  Researcher  2005 - 2008  101 
26.  15571  PhD Blaž Zmazek  Mathematics  Researcher  2004 - 2008  253 
27.  19886  PhD Emil Žagar  Mathematics  Researcher  2006 - 2008  187 
28.  03430  PhD Janez Žerovnik  Mathematics  Researcher  2004 - 2006  805 
29.  14273  PhD Arjana Žitnik  Mathematics  Researcher  2004 - 2008  103 
Organisations (1)
no. Code Research organisation City Registration number No. of publicationsNo. of publications
1.  0101  Institute of Mathematics, Physics and Mechanics  Ljubljana  5055598000  20,258 
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
Views history
Favourite