Oznaka poročila: ARRS-RPROG-ZP-2015/66 H^^lll ШМ ZAKLJUČNO POROČILO O REZULTATIH RAZISKOVALNEGA PROGRAMA (za obdobje 1. 1. 2009 - 31. 12. 2014) A. PODATKI O RAZISKOVALNEM PROGRAMU 1.Osnovni podatki o raziskovalnem programu Šifra programa P1-0297 Naslov programa Teorija grafov Graph Theory Vodja programa 5949 Sandi Klavžar Obseg raziskovalnih ur (vključno s povečanjem financiranja v letu 2014) 22622 Cenovni razred B Trajanje programa 01.2009 - 12.2014 Izvajalci raziskovalnega programa (javne raziskovalne organizacije - JRO in/ali RO s koncesijo) 101 Inštitut za matematiko, fiziko in mehaniko Raziskovalno področje po šifrantu ARRS 1 NARAVOSLOVJE 1.01 Matematika Družbenoekonomski cilj Naravoslovne vede - RiR financiran iz drugih virov (ne iz SUF) Raziskovalno področje po šifrantu FOS 1 Naravoslovne vede 1.01 Matematika B. REZULTATI IN DOSEŽKI RAZISKOVALNEGA PROGRAMA 2.Povzetek raziskovalnega programa1 slo Razvijali smo osrednja področja teorije grafov ter še bolj utrdili vlogo slovenske teorije grafov. Področja, ki smo jih posebej razvijali, so topološka teorija grafov, metrična teorija grafov, grafovski produkti, barvanja grafov ter aplikacije naštetih področij. Na vseh navedenih področjih smo dosegli pomembne, na nekaterih tudi prebojne rezultate. Poleg tega smo tudi na nekaterih drugih področjih teorije grafov in tudi njenih aplikacij dosegli pomembne rezultate. Skupno smo v letih 2009-2014 objavili okoli 300 izvirnih znanstvenih člankov ter dve monografiji pri založbah Birkhauser/Springer in CRC Press. Na področju topološke teorije grafov smo raziskovali predvsem klasične probleme, na primer problem prekrižnega števila. Posebno pozornost smo namenili algoritmičnim problemom, ki zadevajo prekrižno število, grafe vložljive na ploskve nizkega roda in grafe, ki so skoraj ravninski. Na področju metrične teorije grafov smo posebno pozornost namenjali izometričnim vložitvam, metrično definiranim razredom grafov ter uporabam metrične teorije grafov. Nadaljevali smo z raziskavami posplošitev medianskih grafov v povezavi z družinami kompleksov kock in prizem ter geometrijsko teorijo grup. V članku, ki je izšel v prestižni matematični reviji Advances in Mathematics, smo posplošili prej znane rezultate o teh dveh družinah kompleksov in jih povezali z geometrijsko teorijo grup. Produkte grafov smo raziskovali iz številnih vidikov. Najpomembnejši dosežek o produktih grafov je monografija »Handbook of Product Graphs«. Ta knjiga iz leta 2011 na 518 straneh ima v bazi MathSciNet že 61 citatov. Na področju barvanja grafov smo raziskovali klasične in nove probleme barvanja grafov s posebnim poudarkom na ravninskih grafih. V teoriji iger na grafih smo vpeljali in raziskovali nov koncept, ki smo ga poimenovali igra dominacije na grafih. Na področju algoritmične teorije grafov smo raziskovali strukturo družin grafov ter njihove lastnosti, in dobili novo karakterizacijo Lucasovih kock, vključno z linearnim algoritmom za prepoznavanje le-teh ter algoritem za vložitev Fibonaccijevih kock. Najpomebnejše področje, kjer uporabljamo naše razultate, je matematična kemija. Prispevali smo tudi matematični del raziskav v biotehnološki raziskavi, ki je bila objavljena v reviji Nature Chemical Biology, razširjeni matematični model pa v reviji MATCH. Naše znanje smo uporabili tudi v aplikativnih rešitvah. Na področju operacijskih raziskav smo razvijali uporabo znanj pri razvoju odločitvenih procesov. Sodelovali smo na več aplikativnih projektih, npr. pri optimiranju parametriziranja baznih postaj mobilne telefonije četrte generacije ter pri uporabi naših rešitev na področju tehnologij pametnih elektroenergetskih omrežij. ang_ We have developed central areas of graph theory and in this way further promoted the role of the Slovenian school of graph theory. Among the areas that we have especially planned to develop were topological graph theory, metric graph theory, graph products, graph colorings, and applications of these areas. In all of these areas we have achieved important, and in some cases also breakthrough achievements. Apart from that we have also obtained important results in several other areas of graph theory and its applications. In the period 2009-2014 we have published around 300 papers and two monographs with the Birkhauser/Springer and with the CRC Press. In topological graph theory we have studied classical problems such as crossing number problems. Special emphasis was given to algorithmic questions concerning crossing numbers, graphs embeddable on surfaces of low genus, and graphs that are almost planar. In the area of metric graph theory our focus lied in isometric embeddings, metrically defined classes of graphs, and applications of metric graph theory. We have continued our work on generalizations of median graphs in connection with cube and prism complexes, and with geometric group theory. In the paper, published in the prestigious journal Advances in Mathematics, we have generalized older results on two families of complexes and connected these with geometric group theory. We have studied graph products from various viewpoints. Our biggest achievement in graph products is the monograph Handbook of Product Graphs. The book from 2011 on 518 pages has already achieved 61 citations in MathSciNet. In the area of graph colorings we have continued with research dealing with various classical and contemporary graph coloring problems with focus on planar graphs. In game theory we have started to work on a new concept called the domination game on graphs. In the field of algorithmic graph theory we have established a new characterization of Lucas cubes, a linear-time algorithm for their recognition and an algorithm for embedding of Fibonacci cubes. The main area where we apply our results is mathematical chemistry. We have also contributed the mathematical part of a biotech research work that was published in Nature Chemical Biology, an extended mathematical model was published in MATCH. We have used our work also in concrete applications: in the field of operations research we have investigated the use of knowledge in evaluation of decision models. We have taken part in several applied research projects, e.g. optimizing parameters of 4th generation mobile network base stations and applications in the technology of smart electrical networks. 3.Poročilo o realizaciji predloženega programa dela na raziskovalnem programu, (vključno s predloženim dopolnjenim programom dela v primeru povečanja financiranja raziskovalnega programa v letu 2014)2 slo V raziskovalnem programu smo razvijali osrednja področja teorije grafov ter še bolj utrdili vlogo slovenske teorije grafov kot enega vodilnih svetovnih centrov tega področja. Področja, ki smo jih posebej razvijati, so topološka teorija grafov, metrična teorija grafov, grafovski produkti, barvanja grafov ter aplikacije naštetih področij. Na vseh navedenih področjih smo dosegli pomembne, na nekaterih tudi prebojne rezultate. Poleg tega smo tudi na nekaterih drugih področjih teorije grafov in tudi njenih aplikacij dosegli pomembne rezultate. Skupno smo v letih 2009-2014 objavili okoli 300 izvirnih znanstvenih člankov ter dve monografiji pri založbah Birkhauser/Springer in CRC Press. Naj samo na kratko navedemo nekaj glavnih naših dosežkov. TOPOLOŠKA TEORIJA GRAFOV. Na področju topološke teorije grafov smo raziskovali predvsem klasične probleme, na primer problem prekrižnega števila. Posebno pozornost smo namenili algoritmičnim problemom, ki zadevajo prekrižno število, grafe vložljive na ploskve nizkega roda in grafe, ki so skoraj ravninski. Tako smo posplošili tri Leightonove spodnje meje za prekrižno število grafov (prekrižna lema, metoda z bisekcijo, metoda z vložitvami) na minorsko prekrižno število. Naredili smo preboj na področju algoritmičnih problemov v zvezi s prekrižnim številom. Pokazali smo, da je problem aproksimacije prekrižnega števila s konstantno napako računsko težak problem, tudi če se omejimo zgolj na razred kubičnih grafov in da ostaja računanje prekrižnega števila računsko zahteven problem tudi za razred skoraj ravninskih grafov. Razrešili smo tudi problem aditivnosti prekrižnega števila pri rezih v grafih: prekrižno število je aditivno pri rezih velikosti do 3, pri večjih rezih pa smo našli protiprimere. METRIČNA TEORIJA GRAFOV. Na področju metrične teorije grafov smo posebno pozornost namenjali izometričnim vložitvam, metrično definiranim razredom grafov ter uporabam metrične teorije grafov. Nadaljevali smo z raziskavami geodetskega števila; pregled najpomembnejših znanih rezultatov smo objavili kot posebno poglavje monografije "Structural Analysis of Complex Networks". Nadaljevali smo z raziskavami posplošitev medianskih grafov v povezavi z družinami kompleksov kock in prizem ter geometrijsko teorijo grup. V članku, ki je izšel v prestižni matematični reviji Advances in Mathematics, smo posplošili prej znane rezultate o teh dveh družinah kompleksov in jih povezali z geometrijsko teorijo grup. PRODUKTI GRAFOV. Produkte grafov smo raziskovali iz številnih vidikov. Pri delu z invariantami na grafovskih produktih smo se ukvarjali s konveksnim številom v kartezičnem in leksikografskem produktu in s t.i. Thuejevimi problemi. Nadalje smo študirali t.i. vozliščna pokritja poti in dokazali različne spodnje in zgornje meje za produkte. Proučevali smo tudi particijsko dimenzijo kartezičnega in krepkega produkta. Najpomembnejši dosežek o produktih grafov je monografija »Handbook of Product Graphs«. Ta knjiga iz leta 2011 je nastala na osnovi knjige Product Graphs, ki je leta 2000 izšla pri Wiley Interscience. Slednja je postala klasično delo o produktih grafov in predstavlja enega najbolj citiranih del slovenske matematike. V bazi MathSciNet ima že 387 citatov. Nova knjiga je bistveno obsežnejša (518 str. proti 358 str.), napisana je popolnoma na novo in ima v isti bazi že 61 citatov. BARVANJA GRAFOV. Na področju barvanja grafov raziskujemo klasične in nove probleme barvanja grafov s posebnim poudarkom na ravninskih grafih. Med drugim smo izboljšati spodnje meje za kromatično število, ki temeljijo Lovaszovi Theta funkciji. Ugotovili smo, da so spodnje meje, ki uporabljajo Psi operator, definiran leta 2008 (Laurant, Gvozdenovic), opazno boljše kot običajne, na Theta funkciji temelječe meje. UPORABE TEORIJE GRAFOV. Najpomebnejše področje, kjer uporabljamo naše razultate, je matematična kemija. Med drugim smo preučevali različne povezave med resonantnimi množicami benzenoidnega grafa in podgrafi resonančnega grafa, ki je definiran preko 1-faktorjev. Prispevali smo tudi matematični del raziskav v biotehnološki raziskavi, ki je predstavila novo strategijo za konstrukcijo samosestavljivih polipeptidnih nanostrukturnih poliedrov, ki temelji na modularizaciji in uporabi ortogonalnih odsekov, ki paroma tvorijo dimere. Raziskava je bila objavljena v reviji Nature Chemical Biology, razširjeni matematični model pa v reviji MATCH. Naše znanje smo uporabili tudi v aplikativnih rešitvah. Na področju operacijskih raziskav smo razvijali uporabo znanj pri razvoju odločitvenih procesov. Sodelovali smo na več aplikativnih projektih, na katerih so raziskovali uporabo grafovskih modelov pri razvoju tehnoloških rešitev, npr. pri optimiranju parametriziranja baznih postaj mobilne telefonije četrte generacije ter pri uporabi naših rešitev na področju tehnologij pametnih elektroenergetskih omrežij. NADALJNJE TEME. V teoriji iger na grafih smo vpeljali in raziskovali nov koncept, ki smo ga poimenovali igra dominacije na grafih. Ideja je vzbudila zanimanje v več raziskovalnih skupinah po svetu in je trenutno predmet intenzivnega raziskovanja (v ZDA, Franciji, na Madžarskem, v Indiji, ...). Člani naše skupine smo do sedaj objavili že šest člankov o dominacijski igri, še več člankov pa je v pripravi ali v recenzijskem postopku v uveljavljenih znanstvenih revijah. Proučevali smo teme v preseku med teorijo grafov in evklidsko geometrijo. Posebno zanimiv koncept tvorijo geometrijski grafi: to so grafi, ki jih predstavimo v ravnini z ravnimi povezavami in ki vsebujejo dodatno informacijo o razporeditvi daljic, ki ustrezajo povezavam grafa. Opravili smo raziskave, ki povezujejo grafe in delno urejene množice in sicer smo v novem članku na to temo obravnavali tiste delno urejene množice, katerih grafi pokritij neprimerljivosti so tetivni. Na področju algoritmične teorije grafov smo raziskovali strukturo družin grafov ter njihove lastnosti, in dobili novo karakterizacijo Lucasovih kock, vključno z linearnim algoritmom za prepoznavanje le-teh ter algoritem za vložitev Fibonaccijevih kock. 4.Ocena stopnje realizacije programa dela na raziskovalnem programu in zastavljenih raziskovalnih ciljev3 slo_ Rezultati raziskovalnega programa so v celoti izpolnili zastavljene raziskovalne cilje in jih na nekaterih področjih tudi presegli. Dosegli smo pomemben napredek na vseh osrednjih področjih teorije grafov, ki smo si jih zastavili kot cilj: v topološki teoriji grafov, algoritmični teoriji grafov, metrični teoriji grafov, na grafovskih produktih, barvanju grafov in aplikacijah teorije grafov. Razen tega smo raziskovalno delali tudi na nekaterih novih področjih. Med drugim smo v teorijo grafov vpeljali nekatere povsem nove ideje in koncepte, posebej naj poudarimo igro dominacije, ki smo jo kot prvi predstavili leta 2011 v članku v reviji SIAM Journal on Discrete Mathamatics in je trenutno predmet raziskav v več raziskovalnih skupinah širom sveta. Naj izpostavimo najpomembnejše in najprodornejše rezultate po področjih. Topološka teorija grafov: članka o algoritmičnih vidikih prekrižnega števila v revijah Discrete Comp. Geometry in SIAM J. Comput. ter članek o dokončni razrešitvi problema superaditivnosti prekrižnega števila in minorskega prekrižnega števila na prerezih grafov v reviji European J. Combin. Metrična teorija grafov: članek o bukoličnih kompleksih v prestižni matematični reviji Advances in Mathematics. Produkti grafov: monografija Handbook of product graphs, CRC Press; 2011; XVIII, 518 str. Uporaba teorije grafov v biotehnologiji: matematični model predstavljen v članku objavljenem v Nature Chemical Biology in nadgradnja modela v članku v reviji MATCH Commun. Math. Chem. Comp. O svojem delu smo poročali na vabljenih in plenarnih predavanjih. Člani programske skupine smo uredniki in člani uredniških odborov nekaterih najpomembnejših revij s področja teorije grafov. Zato verjamemo, da še naprej uspešno krepimo vlogo, prepoznavnost in vpliv slovenske teorije grafov kot enega izmed svetovnih centrov te teorije. 5.Utemeljitev morebitnih sprememb programa raziskovalnega programa oziroma sprememb, povečanja ali zmanjšanja sestave programske skupine v letu 20144 slo V programsko skupino smo za leto 2014 vključili dr. Jožeta Dediča, ki je sodeloval pri aplikativnih projektih, na katerih smo uporabljali grafovske modele pri razvoju tehnoloških rešitev. Konec leta 2014 smo v programsko skupino vključiti novega mladega raziskovalca Tilna Marca. V letu 2014 v programu nista bila več vključena dr. Gašper Mekiš, ki je dobil zaposlitev v tehnološkem podjetju v tujini in dr. Aleksandra Tepeh, ki se je vključila v delo druge programske skupine. 6.Najpomembnejši znanstveni rezultati programske skupine5 Znanstveni dosežek 1. COBISS ID 16633177 Vir: COBISS.SI Naslov slo Bukolični kompleksi ang Bucolic complexes Opis slo Vpeljemo in obravnavamo bukolične kompleksne, skupno posplošitev sistoličnih in CAT(0) kubnih kompleksov. Definirani so kot enostavno povezani kompleksi prizem, ki zadoščajo določenim lokalnim kombinatornim pogojem. Raziskujemo različne pristope k bukoličnim kompleksom: gledamo jih iz vidika teorije grafov in topološkega vidika kot tudi iz perspektive geometrijske teorije grup. Tako med drugim okarakteriziramo bukolične komplekse preko nekih lastnosti njihovih 2-skeletov in 1-skeletov (ki jim pravimo bukolični grafi), s čimer posplošimo več prej znanih rezultatov. Prav tako dokažemo, da so lokalno končni bukolični kompleksi kontraktibilni in da zadoščajo nekim lastnostim tipa nepozitivnih ukrivljenosti. ang We introduce and investigate bucolic complexes, a common generalization of systolic complexes and CAT(0) cubical complexes. They are defined as simply connected prism complexes satisfying some local combinatorial conditions. We study various approaches to bucolic complexes: from graph-theoretic and topological perspectives, as well as from the point of view of geometric group theory. In particular, we characterize bucolic complexes by some properties of their 2-skeleta and 1-skeleta (that we call bucolic graphs), by which several known results are generalized. We also show that locally-finite bucolic complexes are contractible, and satisfy some nonpositive-curvature-like properties. Objavljeno v Academic Press; Advances in mathematics; 2013; Vol. 243; str. 127-167; Impact Factor: 1.353;Srednja vrednost revije / Medium Category Impact Factor: 0.674; A': 1; WoS: PQ; Avtorji / Authors: Brešar Boštjan, Chalopin Jeremie, Chepoi Victor, Gologranc Tanja, Osajda Damian Tipologija 1.01 Izvirni znanstveni članek 2. COBISS ID 16083801 Vir: COBISS.SI Naslov slo Vizingova domneva: pregled in nedavni rezultati ang Vizing's conjecture: a survey and recent results Opis slo Vizingova domneva iz leta 1968 trdi, da je dominacijsko število kartezičnega produkta dveh grafov vsaj tako veliko, kot je produkt dominacijskih števil faktorjev. V članku naredimo pregled različnih pristopov k tej osrednji domnevi iz teorije grafovske dominacije. Ob tem dokažemo tudi nekaj novih rezultatov. Tako so na primer pokazane nove lastnosti minimalnega protiprimera, dokazana je tudi nova spodnja meja za produkte grafov brez induciranega K_{1,3} s poljubnimi grafi. Skozi celoten članek so obravnavani pripadajoči odprti problemi, vprašanja in sorodne domneve. Vizing's conjecture from 1968 asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers. In this paper we survey the approaches to this central conjecture from domination theory and give some new results along ang the way. For instance, several new properties of a minimal counterexample to the conjecture are obtained and a lower bound for the domination number is proved for products of claw-free graphs with arbitrary graphs. Open problems, questions and related conjectures are discussed throughout the paper. Objavljeno v J. Wiley & Sons; Journal of graph theory; 2012; Vol. 69, iss. 1; str. 46-76; Impact Factor: 0.626;Srednja vrednost revije / Medium Category Impact Factor: 0.673; WoS: PQ; Avtorji / Authors: Brešar Boštjan, Dorbec Paul, Goddard Wayne, Hartnell Bert L., Henning Michael A., Klavžar Sandi, Rall Douglas F. Tipologija 1.02 Pregledni znanstveni članek 3. COBISS ID 15916121 Vir: COBISS.SI Naslov slo Priročnik o produktih grafov ang Handbook of product graphs Opis slo Knjiga je nastala na osnovi knjige Product Graphs, ki je leta 2000 izšla pri WileyInterscience. Slednja je postala klasično delo o produktih grafov in predstavlja enega najbolj citiranih del slovenske matematike. V bazi MathSciNet ima že preko 250 citatov. Nova knjiga je bistveno obsežnejša (518 str. proti 358 str.) in je napisana povsem na novo ter ima povsem novo strukturo. Knjiga Priročnik o produktih grafov obravnava dihotomijo med strukturo produktov grafov in njihovimi podgrafi. Poudarja tudi načrtovanje učinkovitih algoritmov, ki prepoznavajo produkte in njihove podgrafe ter raziskuje povezave med grafovskimi parametri produktov in njihovih faktorjev. Občutno razširjena in popravljena knjiga prinaša popolne dokaze mnogih pomembnih rezultatov in tudi najnovejše rezultate in domneve. Rezultati in algoritmi, ki so novi v tej knjigi obsegajo (1) Izreke o krajšanju, (2) kvadratični prepoznavni algoritem za delne kocke, (3) rezultate o krepki izometrični dimenziji, (4) izračun Wienerjevega indeksa preko kanonične izometrične vložitve, (5) rezultate o povezanosti, (6) deljeno inačico Hedetniemijeve domneve, (7) rezultate o neodvisnostnem številu kartezičnih potenc po vozliščih tranzitivnih grafov, (8) dokaz Vizingove domneve za tetivne grafe, (9) rezultate o minimalnih bazah ciklov in (10) številne izbrane rezultate, kot na primer rezultate o polnih minorjih in nikjer ničelnih pretokih. ang Handbook of product graphs, second edition examines the dichotomy between the structure of products and their subgraphs. It also features the design of efficient algorithms that recognize products and their subgraphs and explores the relationship between graph parameters of the product and factors. Extensively revised and expanded, the handbook presents full proofs of many important results as well as up-to-date research and conjectures. Results and algorithms new to the second edition: (1) Cancellation results, (2) A quadratic recognition algorithm for partial cubes, (3) Results on the strong isometric dimension, (4) Computing the Wiener index via canonical isometric embedding, (5) Connectivity results, (6) A fractional version of Hedetniemi's conjecture, (7) Results on the independence number of Cartesian powers of vertex-transitive graphs, (8) Verification of Vizing's conjecture for chordal graphs, (9) Results on minimum cycle bases and (10) Numerous selected recent results, such as complete minors and nowhere-zero flows. The second edition of this classic handbook provides a thorough introduction to the subject and an extensive survey of the field. The first three parts of the book cover graph products in detail. The authors discuss algebraic properties, such as factorization and cancellation, and explore interesting and important classes of subgraphs. The fourth part presents algorithms for the recognition of products and related classes of graphs. The final two parts focus on graph invariants and infinite, directed, and product-like graphs. Sample implementations of selected algorithms and other information are available on the book's website, which can be reached via the authors' home pages. Objavljeno v CRC Press; 2011; XVIII, 518 str.; A'': 1;A': 1; Avtorji / Authors: Hammack Richard H., Imrich Wilfried, Klavžar Sandi Tipologija 2.01 Znanstvena monografija 4. COBISS ID 15802457 Vir: COBISS.SI Naslov slo Aproksimacijski algoritmi preko skrčitvene dekompozicije ang Approximation algorithms via contraction decomposition Opis slo V delu je dokazano, da je mogoče povezave vsakega grafa omejenega roda razbiti na vnaprej predpisano število delov (k), tako da ima kontrakcija kateregakoli od teh delov omejeno drevesno širino, kjer je meja odvisna le od števila k. Podoben, a precej enostavnejši rezultat, je znan za operacijo odstranjevanja povezav namesto kontrakcije (Baker 1994, Eppstein 2000 in drugi). Dobljeno dekompozicijo uporabimo za razvoj zelo splošnih (meta) algoritmov. Med drugim dobimo polinomske aproksimacijske sheme (PTAS) za poljubne probleme, ki so monotoni za kontrakcijo povezav. Vsi taki problemi, ki izpolnjujejo še nekaj dodatnih pogojev, imajo PTAS za vse grafe omejenega roda. Tako dobimo na primer PTAS za uteženo obliko problema potujočega trgovca in za minimalni uteženi c-povezavno-povezani podmultigraf v grafih omejenega roda, kar hkrati posploši večje število znanih algoritmov. ang We prove that the edges of every graph of bounded (Euler) genus can be partitioned into any prescribed number k of pieces such that contracting any piece results in a graph of bounded treewidth (where the bound depends on k). This decomposition result parallels an analogous, simpler result for edge deletions instead of contractions, obtained by Baker, Eppstein, and others, and it generalizes a similar result for "compression" (a variant of contraction) in planar graphs (Klein). Our decomposition result is a powerful tool for obtaining PTASs for contraction-closed problems (whose optimal solution only improves under contraction), a much more general class than minor-closed problems. We prove that any contraction-closed problem satisfying just a few simple conditions has a PTAS in bounded-genus graphs. In particular, our framework yields PTASs for the weighted Traveling Salesman Problem and for minimum-weight c-edge-connected submultigraph on bounded-genus graphs, improving and generalizing many previous algorithms. We also highlight the only main difficulty in extending our results to general $H$-minor-free graphs. Objavljeno v Akademia Kiado;Springer; Combinatorica; 2010; Vol. 30, no. 5; str. 533552; Impact Factor: 0.910;Srednja vrednost revije / Medium Category Impact Factor: 0.716; A': 1; WoS: PQ; Avtorji / Authors: Demaine Erik D., Hajiaghayi MohammadTaghi, Mohar Bojan Tipologija 1.01 Izvirni znanstveni članek 5. COBISS ID 15160409 Vir: COBISS.SI Naslov slo Algoritmi za grafe z omejeno drevesno širino preko ortogonalnega območnega iskanja ang Algorithms for graphs of bounded treewidth via orthogonal range searching Opis slo Dokazano je, da lahko za vsako fiksno konstanto k vsoto razdalj med vsemi pari vozlišč abstraktnega grafa z n vozlišči in drevesno širino kvečjemu k izračunamo v času O(n log^k1}n). Dokazano je tudi, da lahko za vsako fiksno konstanto k raztezanje geometrijskega grafa z n vozlišči in drevesno širino kvečjemu k izračunamo v pričakovanem času O(n log^k+1} n). ang We show that, for any fixed constant k >= 3, the sum of the distances between all pairs of vertices of an abstract graphs with n vertices and treewidth at most k can be computed in O(n \log^k-1}n) time. We also show that, for any fixed constant k >= 2, the dilation of a geometric graph (i.e., a graph drawn in the plane with straight-line segments) with n vertices and treewidth at most k can be computed in O(n \log^k+1} n) expected time. Recall that the dilation (or stretch-factor) of a geometric graph is the largest ratio, taken over all pairs of vertices, between the distance measured along the graph and the Euclidean distance. The algorithms for both problems are based on the same principle: data structures for orthogonal range searching in bounded dimension provide a compact representation of distances in abstract graphs of bounded treewidth. Objavljeno v Elsevier; Computational geometry; 2009; Vol. 42, iss. 9; str. 815-824; Impact Factor: 1.459;Srednja vrednost revije / Medium Category Impact Factor: 0.761; A': 1; WoS: PN, PQ; Avtorji / Authors: Cabello Sergio, Knauer Christian Tipologija 1.01 Izvirni znanstveni članek 7.Najpomembnejši družbeno-ekonomski rezultati programske skupine6 Družbeno-ekonomski dosežek 1. COBISS ID 26388736 Vir: vpis v poročilo Naslov slo Uredništvo mednarodne znanstvene revije ang Editor of international journals Opis slo Sandi Klavžar in Bojan Mohar sta bila v obdobju 2009-2014 urednika in člana uredniških odborov večine osrednjih revij, ki pokrivajo teorijo grafov. Trenutno je Bojan Mohar urednik v revijah SIAM Journal on Discrete Mathematics (Associate Editor), Discrete Mathematics (Associate Editor), Electronic Journal of Combinatorics (Editor-in-Chief) in član uredniških odborov drugih revij, vključno Journal of Graph Theory, Discrete & Computational Geometry, Ars Mathematica Contemporanea, Journal of Combinatorial Theory Series B, MATCH Communications in Mathematical and in Computer Chemistry. Sandi Klavžar je trenutno urednik za reviji Discrete Applied Mathematics (Associate Editor) in Discussiones Mathematicae Graph Theory (Advisory Editor) ter član uredniških odborov drugih revij, vključno Ars Mathematica Contemporanea, AsianEuropean Journal of Mathematics, European Journal of Combinatorics, MATCH Communications in Mathematical and in Computer Chemistry. ang During the period 2009-2014, Sandi Klavžar and Bojan Mohar served as editors and members of editorial boards of most of the central journals that cover graph theory. At the present, Bojan Mohar is an editor of SIAM Journal on Discrete Mathematics (Associate Editor), Discrete Mathematics (Associate Editor), Electronic Journal of Combinatorics (Editor-in-Chief) and member of editorial boards of other journals including Journal of Graph Theory, Discrete & Computational Geometry, Ars Mathematica Contemporanea, Journal of Combinatorial Theory Series B, MATCH Communications in Mathematical and in Computer Chemistry. Sandi Klavžar is currently an editor of Discrete Applied Mathematics (Associate Editor) and Discussiones Mathematicae Graph Theory (Advisory Editor) and is a member of editorial boards of other journals including Ars Mathematica Contemporanea, AsianEuropean Journal of Mathematics, European Journal of Combinatorics, MATCH Communications in Mathematical and in Computer Chemistry. Šifra C.04 Uredništvo mednarodne revije Objavljeno v ni objava Tipologija 4.00 Sekundarno avtorstvo 2. COBISS ID 16430681 Vir: COBISS.SI Naslov slo Fibonaccijeve kocke, posplošene Fibonaccijeve kocke in slabe besede ang Fibonacci cubes, generalized Fibonacci cubes, and bad words Opis slo V obdobju 2009-2014 smo imeli člani programa številna vabljena predavanja na najpomembnejših mednarodnih konferencah iz teorije grafov, kombinatorike in diskretne matematike. Na primer, predavanje "Fibonaccijeve kocke, posplošene Fibonaccijeve kocke in slabe besede" Sandija Klavžarja je bilo plenarno na na eni osrednjih kombinatoričnih konferenc; izmed več desetih plenarnih predavanj je bil Bojan Mohar vabljeni predavatelj na Kyoto Prize Satellite Workshop in Tokyo, 2010; Boštjan Brešar je bil vabljeni predavatelj na 22nd Workshop on Cycles and Colourings, 2013, v Visokih Tatrah na Slovaškem. ang During 2009-2014 the members of the program delivered numerous invited lectures on central intermational conferences on graph theory, combinatorics, and discrete mathematics. For instance, the lecture "Fibonacci cubes, generalized Fibonacci cubes, and bad words" was an invited plenary lecture at one of the central conferences in combinatorics; among several dozens of invited lectures Bojan Mohar delivered a lecture at the Kyoto Prize Satellite Workshop in Tokyo, 2010; Boštjan Brešar was an invited speaker at 22nd Workshop on Cycles and Colourings, 2013, in High Tatras, Slovakia. Šifra B.04 Vabljeno predavanje Objavljeno v Universita degli Studi di Perugia Avtorji / Authors: Klavžar Sandi ; Combinatorics 2012; 2012; Str. 41; Tipologija 1.10 Objavljeni povzetek znanstvenega prispevka na konferenci (vabljeno predavanje) 3. COBISS ID 19790856 Vir: COBISS.SI Naslov slo Direktni produkti polnih grafov ang Direct products of complete graphs Opis slo Člani programa smo imeli 9 mentorstev doktorandom: MEKIŠ, Gašper; GOLOGRANC, Tanja; ERMAN, Rok; JAKOVAC, Marko; KRANER ŠUMENJAK, Tadeja; TEPEH, Aleksandra; LUŽAR Borut; BERLIČ Martina; ANDOVA Vesna. ang We have supervised 9 Ph.D. students: MEKIŠ, Gašper; GOLOGRANC, Tanja; ERMAN, Rok; JAKOVAC, Marko; KRANER ŠUMENJAK, Tadeja; TEPEH, Aleksandra; LUŽAR Borut; BERLIČ Martina; ANDOVA Vesna. Šifra D.09 Mentorstvo doktorandom Objavljeno v G. Mekiš]; 2013; VII, 74 str.; Avtorji / Authors: Mekiš Gašper Tipologija 2.08 Doktorska disertacija 4. COBISS ID Vir: vpis v poročilo Naslov slo Sedma slovenska mednarodna konferenca o teoriji grafov ang 7th Slovenian International Conference on Graph Theory Sandi Klavžar in Bojan Mohar sta bila člana znanstvenega odbora konference 7th Slovenian International Conference on Graph Theory (Bled, 2011). Boštjan Brešar in Drago Bokal sta bila vabljena predavatelja in sta Opis slo organizirala minisimpozija z naslovoma "Metric graph theory" in "Crossing numbers" v okviru iste konference. S. Cabello je bil član programskega odbora naslednjih mednarodnih konferenc: ACMSIAM Symp. on Discrete Algorithm (SODA) 2014, Graph Drawing 2011, ACM Symposium on Computational Geometry (SoCG) 2011, Mathematical Foundations of Computer Science (MFCS) 2010, European Symposium on Algorithms (ESA) 2010. Drago Bokal je soorganiziral Workshop on Theory and Algorithmic Aspects of Graph Crossing Number, Brno, Czech Republic, 21-22 August 2010, a satellite workshop to MFCS & CSL 2010. ang Sandi Klavžar and Bojan Mohar were members of the scientific committee at the 7th Slovenian International Conference on Graph Theory (Bled, 2011). Boštjan Brešar and Drago Bokal were invited speakers and organizers of minisymposiums "Metric graph theory" and "Crossing numbers" in the frame of the same conference. Sergio Cabello has been in the Program Committee of the following international conferences: ACMSIAM Symp. on Discrete Algorithm (SODA) 2014, Graph Drawing 2011, ACM Symposium on Computational Geometry (SoCG) 2011, Mathematical Foundations of Computer Science (MFCS) 2010, European Symposium on Algorithms (ESA) 2010. Drago Bokal co-organized Workshop on Theory and Algorithmic Aspects of Graph Crossing Number, Brno, Czech Republic, 21-22 August 2010, a satellite workshop to MFCS & CSL 2010. Šifra B.01 Organizator znanstvenega srečanja Objavljeno v ni objava Tipologija 4.00 Sekundarno avtorstvo 5. COBISS ID 16629081 Vir: COBISS.SI Naslov slo Pametni materiali: prebojno odkritje slovenskih znanstvenikov ang Smart materials: a breakthrough discovery of Slovenian scientists Opis slo Pametni materiali: prebojno odkritje slovenskih znanstvenikov : oddaja v sklopu "Glasovi svetov" na Radio Ars 3 ang Smart materials: a breakthrough discovery of Slovenian scientists : radio broadcast in the series "Glasovi svetov" on Radio Ars 3 Šifra F.35 Drugo Objavljeno v RTV Slovenija; MMC RTV SLO; 2013; Avtorji / Authors: Jerala Roman, Gradišar Helena, Božič Abram Sabina, Doles Tibor, Klavžar Sandi Tipologija 1.22 Intervju 8.Drugi pomembni rezultati programske skupine7 Bojan Mohar je bil v letih 2008 in 2009 podpredsednik SIAM AG-DM (sekcija za diskretno matematiko pri SIAM, Society for Industrial and Applied Mathematics, ZDA). Sergio Cabello je bil član programskih odborov naslednjih konferenc: 27th ACM Annual Symposium on Computational Geometry (SoCG 2011), 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010), 18th Annual European Symposium on Algorithms (ESA 2010). B. Mohar je bil član programskega odbora konference ACM-SIAM Symposium on Discrete Algorithms (SODA'12, Kyoto, Japan), in član programskega odbora konference European Conference on Combinatorics, Graph Theory and Applications (Eurocomb 2011). Sandi Klavžar in Bojan Mohar sta bila člana znanstvenega odbora konference 7th Slovenian International Conference on Graph Theory (Bled, 2011). Janez Povh in Riste Škrekovski sta 1.1.2013 postala del nove programske skupine Kompleksna omrežja, ki poteka na Fakulteti za informacijske študije v Novem mestu. To je za Novo mesto zagotovo pomemben družbeno ekonomski dosežek, ki je tudi rezultat znanja, ki sta ga pridobila v naši programski skupini. Programska skupina je v zadnjih letih aktivno sodelovala pri razvoju programskega paketa Sage Math, je trenutno vodilna rešitev za matematična in znanstvena računanja. Dodali smo različne algoritme, pomagali pri pohitritvi implementacije različnih drugih algoritmov, ter odpravi razne pomankljivosti v trenutni implementaciji. V okviru sodelovanja s partnerskimi podjetji smo soavtorji večjega števila inovativnih rešitev. Patentno je zaščitena naslednja inovacija: D. Golob, M. Pleško, B. Vrtič, M. Lozej, D. Bokal, K. Žagar: Sistem za merjenje tlaka na jadru, oblike jadra in metoda za določanje potisne sile : patent SI23913 A Patentna prijava P-201100414, 2012-01-17. Naši člani so intenzivno razvijali modele k podjetništvu in inovativnosti orientiranega poučevanja matematičnega modeliranja, operacijskih raziskav in kombinatorične optimizacije. 9.Pomen raziskovalnih rezultatov programske skupine8 9.1.Pomen za razvoj znanosti9 slo_ Projekt spada med temeljne raziskave s področja matematike. Problemi, ki si jih zastavljamo, so mednarodno pomembni, kar med drugim dokazuje naša bibliografija iz zadnjega obdobja in odmevnost rezultatov. Obravnavani problemi so osrednji v teoriji grafov, hkrati pa imajo aplikacije v drugih znanostih. Tako na primer rezultati o ogljikovih nanoocevkah lahko pripomorejo pri sintezi nanomolekul in pospešijo razvoju nanomaterialov. Razdalja med grafi se uporablja na različnih znanstvenih področjih, kjer se proučujejo podobnosti med objekti. Nov pogled na te probleme s stališča razdalje med grafi pripomore k nadaljnjemu razvoju in novemu pogledu na obstoječe probleme, predvsem s področja biologije, računalništva, kemije, socioloških znanosti in lingvistike. Študija grafovskih invariant obravnava nekatere pomembne realne probleme. Tako na primer pri problemu dodeljevanja frekvenc iščemo optimalno dodelitev frekvenc za oddajnike v brezžičnem omrežju. V radijskem omrežju je vsakemu oddajniku dodeljen frekvenčni kanal. Dva oddajnika se lahko motita, če sta postavljena preblizu. Tudi če oddajnika uporabljata različne frekvence, se še vedno lahko pojavljajo motnje, če se nahajata blizu drug drugega. Frekvenčni spekter je zaradi vedno večjega povpraševanja vedno bolj dragocen. Naloga dodeljevanja frekvenc je tako čim bolj zmanjšati število frekvenc in se pri tem izogniti motnjam. Rezultati raziskovalnega programa so bili objavljeni v vodilnih mednarodnih revijah s področja diskretne matematike in predstavijeni na mednarodnih znanstvenih konferencah. Imeli smo večje število vabljenih plenarnih predavanj. S tem bomo še okrepili dosedanji zavidljiv mednarodni ugled slovenske šole teorije grafov. ang_ The project belongs to basic research in the area of mathematics. Problems on which we have been working on on are internationally important, which can in particular be justified by 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 and at the same time have applications in other scientific fields. For instance, our results on carbon nanotubes can accelerate the synthesis of carbon nanomolecules and therefore help the improvement of nanomaterials. Distances between graphs are used in those areas of science where similarities of objects are studied. New insights concerning distances between graphs further develop existing areas and give a fresh look at existing problems, specifically in areas like biology, computer science, chemistry, social sciences and linguistics. The study of graph invariants addresses some important real-life problems. In particular, the frequency assignment problem asks for assigning frequencies to transmitters in a wireless network. In a broadcasting network, each transmitter is assigned a frequency channel for its transmissions. Two transmissions can interfere if their channels are too close. This means that even if two transmitters use different channels, there still may be interference if the two transmitters are located close to each other. The spectrum of frequencies gets more and more scarce, because of increasing demands. Thus the task is to minimize the span of frequencies while avoiding interference. The obtained results were published in leading journals from the area of discrete mathematics and were presented at international scientific conferences. We were invited plenary speakers at numerous important international conferences. In this way we have further increased the international role of the Slovenian graph theory school. 9.2.Pomen za razvoj Slovenije10 slo_ Raziskovalni program je naravnan tako, da omogoča vključevanje najsposobnejših mladih raziskovalcev in s tem omogoča dolgoročno ohranjanje kvalitetnega raziskovalnega dela s področja matematike, kar ima pozitiven vpliv na kvaliteto univerzitetnih programov matematike in drugih znanosti. V obdobju 2009-2014 smo bili v naši skupini mentorji 9 doktorantom. Naši doktoranti se po koncu usposabljanja zaposlujejo tudi v gospodarstvu, kar ima pozitiven vpliv na gospodarstvo. Ker je matematika prisotna na mnogih drugih področjih, kvalitetno raziskovanje matematike posredno vpliva tudi na razvoj vrste drugih disciplin. Znotraj matematike pa program predvsem razvija teorijo grafov in s tem ohranja in krepi njen svetovni nivo. Pričakovani rezultati so predvsem teoretični. Kljub temu pa imajo veliko potencialno uporabo v praksi, kar se posebej nanaša na naša algoritmična in optimizacijska raziskovanja. To dobro potrjujejo dosedanje raziskave, ki so pripeljale do sodelovanja s slovensko industrijo s področja tehnološkega razvoja, predvsem v informacijskih in telekomunikacijskih tehnologijah. V juniju 2015 načrtujemo izvedbo konference "8th Slovenian International Conference on Graph Theory" na kateri pričakujemo 200-300 udeležencev. Gre za eno izmed največjih svetovnih konferenc s področja teorije grafov. Naša programska skupina bo vodila organizacijo dogodka, je vodja programa glavni organizator konference. ang_ The research programme is oriented to encourage the integration of the most promising young researchers. In this way it enables a long-term continuation of the research quality in mathematics, which in turn has a positive influence on the quality of the university programs in mathematics and other sciences. In the period 2009-2014 we have supervised 9 Ph.D. students. After finishing their Ph.D., our students are getting employed also in industry, hence our programme has a positive impact on the national economy. Since mathematics is used in many other areas, the quality of research in mathematics has an indirect but important influence on the development of other disciplines as well. Inside mathematics the programme mostly develops graph theory and keeps and strengthens its world reputation. The expected results are mostly theoretical. Nevertheless, they have a big potential for applications, especially our research in algorithmic and optimization aspects of graph theory. This can be well justified with our previous research that has led to a cooperation with the Slovenian industry focused on technological development, mostly in the information and telecommunication technology. In June 2015 we will organize the "8th Slovenian International Conference on Graph Theory", where we expect about 200-300 participants. This is one of the largest conferences in the world on graph theory. Our programme group will lead the organization, in particular, the programme leader is the main organizer of the event. lO.Zaključena mentorstva članov programske skupine pri vzgoji kadrov v obdobju 1.1.2009-31.12.201411 10.1. Diplome12 vrsta usposabljanja število diplom bolonjski program -1. stopnja 143 bolonjski program - II. stopnja 6 univerzitetni (stari) program 21 10.2. Magisterij znanosti in doktorat znanosti13 Šifra raziskovalca Ime in priimek Mag. Dr. MR 23904 Aleksandra Tepeh O ® □ 29919 Marko Jakovac o 0 □ 30823 Gašper Mekiš o 0 □ 32028 Tanja Gologranc o 0 □ 0 Martina Berlič o 0 □ 31670 Borut Lužar o 0 □ 36412 Vesna Andova o 0 □ 0 Ksenija Smogavec 0 O □ 22648 Tadeja Kraner Šumenjak o 0 □ Legenda: Mag. - Znanstveni magisterij Dr. - Doktorat znanosti MR - mladi raziskovalec ll.Pretok mladih raziskovalcev - zaposlitev po zaključenem usposabljanju14 Šifra raziskovalca Ime in priimek Mag. Dr. Zaposlitev 30823 Gašper Mekiš o 0 1 E - Tujina v 32028 Tanja Gologranc o 0 1 C - Gospodarstvo v 29585 Rok Erman o 0 1 C - Gospodarstvo v Legenda zaposlitev: A - visokošolski in javni raziskovalni zavodi B - gospodarstvo C - javna uprava D - družbene dejavnosti E - tujina F - drugo 12.Vključenost raziskovalcev iz podjetij in gostovanje raziskovalcev, podoktorandov ter študentov iz tujine, daljše od enega meseca, v obdobju 1.1.2009-31.12.2014 Šifra raziskovalca Ime in priimek Sodelovanje v programski skupini Število mesecev 0 Ismael Gonzalez Yero B - uveljavljeni raziskovalec v 3 0 Dorota Kuziak C - študent - doktorand v 3 16013 Ciril Petr A - raziskovalec/strokovnjak v 48 22402 Drago Bokal A - raziskovalec/strokovnjak v 24 0 Yaser Alizadeh C - študent - doktorand v 4 0 Yoomi Rho B - uveljavljeni raziskovalec v 12 0 Douglas Rall B - uveljavljeni raziskovalec v 6 23411 Jože Dedič A - raziskovalec/strokovnjak v 12 36905 Andreas Hinz B - uveljavljeni raziskovalec v 6 Legenda sodelovanja v programski skupini: A - raziskovalec/strokovnjak iz podjetja B - uveljavljeni raziskovalec iz tujine C - študent - doktorand iz tujine D - podoktorand iz tujine 13.Vključevanje v raziskovalne programe Evropske unije in v druge mednarodne raziskovalne in razvojne programe ter drugo mednarodno sodelovanje v obdobju 1.1.2009-31.12.201415 SLO_ • Projekt »Naravoslovni izobraževalni center za trajnostni razvoj« v izvedbi Fakultete za naravoslovje in matematiko Univerze v Mariboru in ob financiranju Norveškega finančnega mehanizma (Norway Grants), http://nic.fnm.unimb.si/ (eden izmed koordinatorjev Drago Bokal). • V okviru projekta GReGAS smo sodelovali z individualnim projektom Isometric Embeddings into Product-Like Graphs. GReGAS je eden izmed štirih projektov v okviru Collaborative Research Project EuroGIGA (vodja IP projekta Sandi Klavžar). • Slovensko-francosko-italijanski projekt "OLEDCHIP, Diagnostic chip based on organic light emitting diode", financiran skozi MNTERA II podporni mehanizem (soorganizator Drago Bokal). Člani programa smo bili nosilci bilateralnih projekov: • Grafi v brezžičnih senzorskih omrežjih (slovensko-slovaški projekt, vodja Boštjan Brešar) • Aktualne grafovske invariante (slovensko-ameriški projekt, vodja Sandi Klavžar) • Algoritmični problemi na topoloških grafih (slovensko-francoski projekt, vodja SergioCabello Justo) • Grafovske particije in njihova uporaba (slovensko-češki projekt, vodja Riste Škrekovski) • Grafovsko teoretični indikatorji fulerenske stabilnosti (slovensko-hrvaški projekt, vodja Riste Škrekovski) • Particije in strukture grafov (slovensko-poljski projekt, vodja Riste Škrekovski) • Razvoj novega "razveji in omeji" algoritma za izračun kromatičnega števila grafa • (slovensko-srbski projekt, vodja Janez Povh) • Presečni grafi geometrijskih objektov (slovensko-flamski projekt, vodja Sergio Cabello) • Metrična teorija grafov in grafovski produkti (slovensko-indijski projekt, vodja SandiKlavžar) • Vložitve grafov (slovensko-ameriški projekt, vodja Sandi Klavžar) • Razdalje, struktura in kartezični produkti grafov (slovensko-francoski pojekt, vodja • Boštjan Brešar) • Kemijska teorija grafov (slovensko-slovaški projekt, vodja Riste Škrekovski) • Grafovske invariante (slovensko-kitajski projekt, vodja Sandi Klavžar) • Grafovski modeli in njihove aplikacije (slovensko-francoski projekt, vodja Riste Škrekovski) • Fibonaccijeve kocke, Lucasove kocke in posplošitve (slovensko-francoski projekt, vodja Sandi Klavžar) • Kombinatorika na Fibonaccijevih in sorodnih besedah - uporabe na razredih grafov Fibonaccijevega tipa (slovensko-korejski projekt, vodja Sandi Klavžar) • Grafovska dominacija (slovensko-francoski pojekt, vodja Boštjan Brešar) • Grafovski operatorji in produkti (slovensko-argentinski projekt, vodja Boštjan Brešar) 14.Vključenost v projekte za uporabnike, ki so v obdobju trajanja raziskovalnega programa (1.1.2009-31.12.2014) potekali izven financiranja ARRS16 slo_ Na področju gospodarstva smo sodelovali s podjetjema Cosylab d.d. in Iskratel d.d.Sodelovali pri naslednjih projektih, ki niso bili financirani v okviru ARRS, pri vseh je bil koordinator Drago Bokal: • mOIDom mobilna okoljska izkaznica doma • Sintesis eStoritev in mobilna aplikacija za klasifikacijo, vrednotenje, integracijo, migracijo in varovanje SaaS aplikacij • PoMSE podatkovna mreža za sončno energijo • GenelO - Generic workflow manager software for qPCR laboratories. 15.Ocena tehnološke zrelosti rezultatov raziskovalnega programa in možnosti za njihovo implementacijo v praksi (točka ni namenjena raziskovalnim programom s področij humanističnih ved)17 slo Programska raziskovalna skupina primarno prispeva k širitvi znanja na fundamentalnih bazičnih raziskavah (stopnja tehnološke zrelosti TRL1), ki pripomorejo k razumevanju konceptov in nimajo neposredne tržne uporabnosti. Abstrakcija tega znanja, tj. metodologija in nekateri koncepti, pa so uporabni pri modeliranju algoritmičnih in optimizacijskih problemov na področjih IKT, sintezne biologije in kemije. V teh področjih smo več naših rezultatov pripeljali do stopnje tehnološke zrelosti TRL3 (eksperimentalna validacija konceptov), ki jo predstavljajo algoritmi, pognani na eksperimentalnih podatkih oz. TRL4 (potrditev tehnološke rešitve v laboratorijskem okolju), ki jo predstavljajo v laboratoriju sintetizirani polipeptidi oz. algoritmi, implementirani v eksperimentalni odprtokodni programski opremi. V okviru zaposlitev v partnerskih podjetjih so raziskovalci sodelovali tudi pri konceptualiziranju novih produktov in plasiranju na trg, tako da je programska skupina kot celota v obdobju 20092014 pridobila izkušnje s celotnega spektra tehnoloških zrelosti od TRL1 do TRL9, s poudarkom na začetku tega spektra. Prav tako smo se intenzivno povezovali s potencialnimi uporabniki naših znanj, tako da imamo identificiranih več tržnih niš, na katerih lahko z našimi ekspertizami gospodarstvu pomagamo pri razvoju novih produktov in storitev, pri čemer se bomo osredotočili na marketpull pristop, saj je naše znanje preveč specifično in prekompleksno, da bi bilo zanimivo za finančno intenziven technologypush pristop. 16.Ocenite, ali bi doseženi rezultati v okviru programa lahko vodili do ustanovitve spin-off podjetja, kolikšen finančni vložek bi zahteval ta korak ter kakšno infrastrukturo in opremo bi potrebovali možnost ustanovitve spin-off podjetja DA NE potrebni finančni vložek 520.000 EUR ocena potrebne infrastrukture in opreme!8 Rezultati programa imajo potencial za ustanavljanje spinoff podjetij na področju IKT ob ustreznem povezovanju s partnerji specifičnih tehnoloških kompetenc. Ti partnerji bi k projektu prispevali vmesnik med tehnološkim problemom in njegovo abstrakcijo v matematičnem modelu, naša programska skupina bi prispevala strukturna in algoritmičn a potrebna znanja, da matematični model problema uporabimo za njegovo rešitev. Potrebna oprema je odvisna od specifičnega problema. Več rešitev bi lahko implementirali s pomočjo virtualizacije v računalniškem oblaku, kjer bi bil strošek opreme najem infrastrukture in strojne in programske opreme cca. 20.000 EUR. Pomembnejši strošek bi bil strošek dela za razvoj poslovnega modela in aktivno pridobivanje strank cca. 250.000 EUR ter strošek namenskega razvoja izdelka cca. 250.000 EUR. Za natančnejšo oceno bi bilo potrebno pripraviti podrobno študijo pregleda potencialnega trga, načrt iskanja strank in ocena stroškov tega dela; cca. 25.000 do 50.000 EUR. 17.Izjemni dosežek v letu 201419 17.1. Izjemni znanstveni dosežek V letu 2014 sta bila člana programske skupine Teorija grafov Sandi Klavžar in Bojan Mohar v uredniških odborih dvanajstih revij indeksiranih na ISI Science Citation Index Expanded, med njimi so osrednje znanstvene revije za področje teorije grafov in širše kombinatorike. Oba sta člana uredniških odborov revij Ars Mathematica Contemporanea in MATCH Communications in Mathematical and in Computer Chemistry. Sandi Klavžar je tudi urednik v revijah Discrete Applied Mathematics (Associate Editor) in Discussiones Mathematicae Graph Theory (Advisory editor) ter član uredniškega odbora revije European Journal of Combinatorics. Bojan Mohar je tudi urednik v revijah The Electronic Journal of Combinatorics (Editor-in-Chief), Discrete Mathematics (Associate Editor), SIAM Journal on Discrete Mathematics (Associate Editor), in član uredniških odborov revij Journal of Graph Theory, Journal of Combinatorial Theory Series B, Discrete and Computational Geometry ter Linear and Multilinear Algebra. 17.2. Izjemni družbeno-ekonomski dosežek Bojan Mohar je bil glavni organizator (chair) konference "SIAM Conference on Discrete Mathematics, June 16-19, 2014, Minneapolis, USA". Sergio Cabello je bil gostujoči profesor na prestižnih institucijah Ecole Normale Superieure, Paris, Francija, in na IST Austria, Klosteneurburg. C. IZJAVE Podpisani izjavljam/o, da: • so vsi podatki, ki jih navajamo v poročilu, resnični in točni; • se strinjamo z obdelavo podatkov v skladu z zakonodajo o varstvu osebnih podatkov za potrebe ocenjevanja in obdelavo teh podatkov za evidence ARRS; • so vsi podatki v obrazcu v elektronski obliki identični podatkom v obrazcu v papirnati obliki; • so z vsebino poročila seznanjeni in se strinjajo vsi izvajalci raziskovalnega programa. Podpisi: zastopnik oz. pooblaščena oseba matične RO (JRO in/ali RO s koncesijo): vodja raziskovalnega programa: in Inštitut za matematiko, fiziko in mehaniko Sandi Klavžar ZIG Kraj in datum: Ljubljana 6.3.2015 Oznaka poročila: ARRS-RPROG-ZP-2015/66 1 Napišite povzetek raziskovalnega programa v slovenskem jeziku (največ 3.000 znakov vključno s presledki - približno pol strani, velikost pisave 11) in angleškem jeziku (največ 3.000 znakov vključno s presledki - približno pol strani, velikost pisave 11). Nazaj 2 Napišite kratko vsebinsko poročilo, v katerem predstavite raziskovalno hipotezo in opis raziskovanja. Navedite ključne ugotovitve, znanstvena spoznanja, rezultate in učinke raziskovalnega programa in njihovo uporabo ter sodelovanje s tujimi partnerji. V primeru odobrenega povečanja obsega financiranja raziskovalnega programa v letu 2014 mora poročilo o realizaciji programa dela zajemati predložen program dela ob prijavi in predložen dopolnjen program dela v letu 2014. Največ 12.000 znakov vključno s presledki (približno dve strani, velikosti pisave 11). Nazaj 3 Realizacija raziskovalne hipoteze. Največ 3.000 znakov vključno s presledki (približno pol strani, velikosti pisave 11). Nazaj 4 V primeru bistvenih odstopanj in sprememb od predvidenega programa dela raziskovalnega programa, kot je bil zapisan v predlogu raziskovalnega programa oziroma v primeru sprememb, povečanja ali zmanjšanja sestave programske skupine v zadnjem letu izvajanja raziskovalnega programa, napišite obrazložitev. V primeru, da sprememb ni bilo, navedite: "Ni bilo sprememb.". Največ 6.000 znakov vključno s presledki (približno ena stran, velikosti pisave 11). Nazaj 5 Navedite znanstvene dosežke (največ pet), ki so nastali v okviru izvajanja raziskovalnega programa. Raziskovalni dosežek iz obdobja izvajanja programa vpišete tako, da izpolnite COBISS kodo dosežka - sistem nato sam izpolni naslov objave, naziv, IF in srednjo vrednost revije, naziv FOS področja ter podatek, ali je dosežek uvrščen v A'' ali A'. Nazaj 6 Navedite družbeno-ekonomske dosežke (največ pet), ki so nastali v okviru izvajanja raziskovalnega programa. Družbeno-ekonomski dosežek iz obdobja izvajanja programa vpišete tako, da izpolnite COBISS kodo dosežka - sistem nato sam izpolni naslov objave, naziv, IF in srednjo vrednost revije, naziv FOS področja ter podatek, ali je dosežek uvrščen v A'' ali A'. Družbeno-ekonomski dosežek je po svoji strukturi drugačen kot znanstveni dosežek. Povzetek znanstvenega dosežka je praviloma povzetek bibliografske enote (članka, knjige), v kateri je dosežek objavljen. Povzetek družbeno-ekonomskega dosežka praviloma ni povzetek bibliografske enote, ki ta dosežek dokumentira, ker je dosežek sklop več rezultatov raziskovanja, ki je lahko dokumentiran v različnih bibliografskih enotah. COBISS ID zato ni enoznačen, izjemoma pa ga lahko tudi ni (npr. prehod mlajših sodelavcev v gospodarstvo na pomembnih raziskovalnih nalogah, ali ustanovitev podjetja kot rezultat programa ... - v obeh primerih ni COBISS ID). Nazaj 7 Navedite rezultate raziskovalnega programa iz obdobja izvajanja programa v primeru, da katerega od rezultatov ni mogoče navesti v točkah 6 in 7 (npr. ker se ga v sistemu COBISS ne vodi). Največ 2.000 znakov vključno s presledki (približno 1/3 strani, velikost pisave 11). Nazaj 8 Pomen raziskovalnih rezultatov za razvoj znanosti in za razvoj Slovenije bo objavljen na spletni strani: http://www.sicris.si/ za posamezen program, ki je predmet poročanja. Nazaj 9 Največ 4.000 znakov vključno s presledki (približno 2/3 strani, velikost pisave 11). Nazaj 10 Največ 4.000 znakov vključno s presledki (približno 2/3 strani, velikost pisave 11). Nazaj 11 Upoštevajo se le tiste diplome, magisteriji znanosti in doktorati znanosti (zaključene/i v obdobju 1.1.2009-31.12.2014), pri katerih so kot mentorji sodelovali člani programske skupine. Nazaj 12 Vpišite število opravljenih diplom v času izvajanja raziskovalnega programa glede na vrsto usposabljanja. Nazaj 13 Vpišite šifro raziskovalca in/ali ime in priimek osebe, ki je v času izvajanja raziskovalnega programa pridobila naziv magister znanosti in/ali doktor znanosti ter označite doseženo izobrazbo. V primeru, da se je oseba usposabljala po programu Mladi raziskovalci, označite "MR". Nazaj 14 Za mlade raziskovalce, ki ste jih navedli v tabeli 11.2. točke (usposabljanje so uspešno zaključili v obdobju od 1.1.2009 do 31.12.2014), izberite oz. označite, kje so se zaposlili po zaključenem usposabljanju. Nazaj 15 Navedite naslove projektov in ime člana programske skupine, ki je bil vodja/koordinator navedenega projekta. Največ 6.000 znakov vključno s presledki (približno ena stran, velikosti pisave 11). Nazaj 16 Navedite naslove projektov, ki ne sodijo v okvir financiranja ARRS (npr: industrijski projekti, projekti za druge naročnike, državno upravo, občine idr.) in ime člana programske skupine, ki je bil vodja/koordinator navedenega projekta. Največ 6.000 znakov vključno s presledki (približno ena stran, velikosti pisave 11). Nazaj 17 Opišite možnosti za uporabo rezultatov v praksi. Opišite izdelke oziroma tehnologijo in potencialne trge oziroma tržne niše, v katere sodijo. Ocenite dodano vrednost izdelkov, katerih osnova je znanje, razvito v okviru programa oziroma dodano vrednost na zaposlenega, če jo je mogoče oceniti (npr. v primerih, ko je rezultat izboljšava obstoječih tehnologij oziroma izdelkov). Največ 3.000 znakov vključno s presledki (približno pol strani, velikosti pisave 11). Nazaj 18 Največ 1.000 znakov vključno s presledki (približno 1/6 strani, velikost pisave 11) Nazaj 19 Navedite en izjemni znanstveni dosežek in/ali en izjemni družbeno-ekonomski dosežek raziskovalnega programa v letu 2014 (največ 1000 znakov, vključno s presledki, velikost pisave 11). Za dosežek pripravite diapozitiv, ki vsebuje sliko ali drugo slikovno gradivo v zvezi z izjemnim dosežkom (velikost pisave najmanj 16, približno pol strani) in opis izjemnega dosežka (velikost pisave 12, približno pol strani). Diapozitiv/-a priložite kot priponko/-i k temu poročilu. Vzorec diapozitiva je objavljen na spletni strani ARRS http://www.arrs.gov.si/sl/gradivo/, predstavitve dosežkov za pretekla leta pa so objavljena na spletni strani http://www.arrs.gov.si/sl/analize/dosez/. Nazaj Obrazec: ARRS-RPROG-ZP/2015 v1.00b 59-74-57-F2-FE-7C-CA-6B-33-E0-B8-C7-8C-A5-34-1B-C8-31-6C-60 Priloga 1 Uiscussiunes Malliemattcac