11. |
12. |
13. |
14. |
15. |
16. |
17. Uporaba simetrijskih grafov pri konveksnih poliedrihJurij Kovič, 2013, doktorska disertacija Opis: Grafe praporov in simetrijske grafe, ki so jih odkrili okrog leta 1980, so doslej uporabljali predvsem za klasifikacijo zemljevidov - to je grafov, celično vloženih v kompaktne ploskve. Namen te disertacije je prikazati nekaj razširitev njihove uporabe. V prvem delu disertacije uporabimo simetrijske grafe pri klasifikaciji poliedrov z regularnimi poligonskimi ali zvezdastimi lici. Podamo tudi karakterizacijo teh poliedrov z minimalnim številom parametrov. V drugem delu disertacije na podoben način klasificiramo molekule,sestavljene iz pravilnih šestkotniških gradnikov, pri čemer upoštevamo tudi njihove točkovne grupe. V tretjem delu disertacije pojem simetrijskih grafov razširimo na hiperzemljevide in geometrijske konfiguracije, nazadnje pa tudi na sferne poliedre in sferne molekule.
Ključne besede: polieder, graf praporov, simetrijski graf, simetrijska grupa
Objavljeno v RUP: 15.10.2013; Ogledov: 2928; Prenosov: 56
 Povezava na celotno besedilo |
18. The exact weighted independent set problem in perfect graphs and related classesMartin Milanič, Jérôme Monnot, 2009, objavljeni znanstveni prispevek na konferenci Opis: The exact weighted independent set (EWIS) problem consists in determining whether a given vertex-weighted graph contains an independent set of given weight. This problem is a generalization of two well-known problems, the NP-complete subset sum problem and the strongly NP-hard maximum weight independent set (MWIS) problem. Since the MWIS problem is polynomially solvable for some special graph classes, it is interesting to determine the complexity of this more general EWIS problem for such graph classes. We focus on the class of perfect graphs, which is one of the most general graph classes where the MWIS problem can be solved in polynomial time. It turns out that for certain subclasses of perfect graphs, the EWIS problem is solvable in pseudopolynomial time, while on some others it remains strongly NP-complete.In particular, we show that the EWIS problem is strongly NP-complete for bipartite graphs of maximum degree three, but solvable in pseudo-polynomial time for cographs, interval graphs and chordal graphs, as well as for some other related graph classes.
Ključne besede: graf, neodvisna množica, popolni graf, dvodelni graf
Objavljeno v RUP: 15.10.2013; Ogledov: 2887; Prenosov: 116
Povezava na celotno besedilo |
19. Characterization of edge-transitive 4-valent bicirculantsIstván Kovács, Boštjan Kuzman, Aleksander Malnič, Steve Wilson, 2012, izvirni znanstveni članek Opis: Bicirkulant je graf, ki dopušča avtomorfizem z natanko dvema orbitama vozlišč enake velikosti. V članku so karakterizirani vsi neizomorfni 4-valentni povezavno tranzitivni bicirkulanti. Posledično je izpeljana karakterizacija 4-valentnih ločno tranzitivnih dihedrantov.
Ključne besede: matematika, teorija grafov, štirivalenten graf, bicirkulantni graf, Cayleyev graf, povezavno tranzitiven graf, ločno tranzitiven graf, dihedrant, rose window graf, grupa avtomorfizmov
Objavljeno v RUP: 15.10.2013; Ogledov: 3910; Prenosov: 146
Povezava na celotno besedilo |
20. |
