Projects / Programmes
January 1, 2004
- December 31, 2008
Code |
Science |
Field |
Subfield |
1.01.00 |
Natural sciences and mathematics |
Mathematics |
|
1.07.00 |
Natural sciences and mathematics |
Computer intensive methods and applications |
|
2.07.00 |
Engineering sciences and technologies |
Computer science and informatics |
|
Code |
Science |
Field |
P110 |
Natural sciences and mathematics |
Mathematical logic, set theory, combinatories |
topological graph theory, graph coloring, graph products, metric graph theory, theory of algorithms, graph minor, connectivity, discrete geometry.
Researchers (19)
Organisations (1)
Abstract
The research of the program group covers a considerable part of graph theory and its applications in other parts of mathematics and in other fields of research. The majority of the research will be given in the following areas. Basic properties of graph embeddable in surfaces will be explored. We will try to characterize obstructions for the existence of embeddings and to develop efficient embedding algorithms. In the theory of graph minors we plan to research the crossing number, unavoidable structures in large graphs, and forbidden minors for some minor closed families. We will investigate spectral properties of (embedded) graphs, mostly with respect to the Laplacian graph operator. We will also consider graph colorings, above all list colorings, nonrepetitive colorings, circular chromatic numbers, flows in graphs, and similar. Graph products will also be considered, in particular their invariants and related problems. Median graphs will be studied with an emphasis on the recognition problem. We will also consider several natural classes of graphs that appear naturally in the theory of median graphs: isometric subgraphs of hypercubes, semi-median graphs, quasi-median graphs and isometric subgraphs of Hamming graphs. Metric graph theory will be applied in the chemical graph theory in order to compute different topological invariants of graphs. In the area of computer mathematics we especially plan to develop fast algorithms for recognition of important graph classes and to study problems related to generalizations of the classical Tower of Hanoi problem. In cooperation with the University of Auckland from New Zealand we will perform an extensive computer work on a network with more than 200 computers in order to examine some well-known conjectures.
Significance for science
The project belongs to basic research from the area of mathematics. Problems that we will work on are internationally important, which can in particular be justified with our bibliography from the last period as well as with the (citation) impact of our results. The problems are central in the area of graph theory. We expect that the newly obtained results will be published in established international journals and we will present them at international scientific conferences. For the next period we expect that we will be invited to deliver several invited plenary talks which will further emphasize the importance of ourresearch achievements. In this way we will further increase the role of the Slovenian graph theory school. The results are mainly theoretical with potential to be applicable in information technologies. Our previous contacts with industry include Hermes Softlab and Iskratel. The research programme is oriented such that it enables to integrate the most promising young researchers. In this way it enables a long-term continuation of the quality research in mathematics which has in turn a positive influence on the quality of the university programs in mathematics. Since mathematics is used in many other areas, the quality of research in mathematics has an indirect but imporatant influence on the development of other disciplines as well. Inside mathematics the programme mostly developes graph theory and keeps and strenthens its world level. There is a strong international cooperation through bilateral projects and many research visits. In the last years we had the following international projects: 1. Cooperation with ALCOM (Pierre Rosenstiehl, France). 2. Cooperation with Hungarian Academy of Sciences. 3. Cooperation within European network DIMANET for discrete mathematics. 4. SLO-USA projects on graph minors (Neil Robertson, John Maharry, Ohio State University, USA). 5. Several bilateral projects with Austria (University of Leoben). 6. Several PROTEUS projects with IMAG, Grenoble, France (Sylvain Gravier and Michel Mollard). 7. SLO-DE project with the Technical University Ilmenau, Germany (Thomas Bohme and Michael Stiebitz). Every four years we organize an important international conference in graph theory (Slovenian Graph Theory Conference) with 100-200 participants from all over the world.
Significance for the country
Reserach of this program group is basic but the methods can be applied to optimization, network designs, control of production processes. Our expertise has led to a cooperation with the Slovenian industry from the technological development, mostly in the information and telecommunication technology. In the last period we have successfully cooperated in the projects Models and algorithms for employee scheduling (project ordered by HIT d.d., Nova Gorica), Algorithms for developing a model of working process (project ordered by ICIT, d.o.o., Šempeter pri Gorici), Optimal distribution among fuel stations (project ordered be Ultra d.o.o., Zagorje ob Savi), The application of the Q factor (SAIDI and SAIFI) in the methodology of determining distribution charges for power transmission and distribution grid (the project is done in collaboration with the institute Milan Vidmar), Graphs and telecommunication networks (IMFM and ISKRATEL, telekomunikacijski sistemi, d.o.o.), Graph minors, graphs on surfaces and networks (IMFM and Hermes Softlab Programska Oprema).
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