| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 10 / 66
First pagePrevious page1234567Next pageLast page
1.
2.
UPORABA HIBRIDNIH METAHEVRISTIK PRI REŠEVANJU OPTIMIZACIJSKIH PROBLEMOV
Igor Pesek, 2009, dissertation

Abstract: V doktorski disertaciji sta predstavljena dva algoritma za reševanje težkih kombinatoričnih problemov. Prvi problem se imenuje Problem razvrščanja poslov z omejitvami virov, za katerega smo razvili algoritem z združevanjem konstrukcijske hevristike RAR z algoritmom vzpenjanja na hrib. Drugi problem, ki ga v obravnavamo, je problem načrtovanja usmerjenih omrežij z minimalno ceno in enotnimi vsi-do-vseh komunikacijskimi zahtevami med vozlišči. Za drug algoritem smo razvili algoritem, ki združuje metahevristiko izbiranja s pragom, lokalno iskanje in metodo za obdelavo podatkov. Oba algoritma sta med najboljšimi v primerjalnih testih.
Keywords: hevristični algoritem, lokalno iskanje, metahevristike, optimizacijske metode, NP-težki problemi, razvrščanje poslov z omejitvami virov, načrtovanje usmerjenih omrežij
Published: 07.04.2009; Views: 3038; Downloads: 211
.pdf Full text (1,28 MB)

3.
PROBLEM KITAJSKEGA POŠTARJA S PRIORITETNIMI VOZLIŠČI
Tomaž Kramberger, 2010, dissertation

Abstract: V doktorski disertaciji z naslovom Problem kitajskega poštarja s prioritetnimi vozlišči je preučevana posplošitev problema kitajskega poštarja, v kateri je podmnožica vozlišč utežena in vrstni red obiska vozlišč vpliva na vrednost namenske funkcije. Preučevan problem je dokazano NP-težek. V disertaciji sta predstavljeni in preučevani dve konstrukcijski hevristiki. Za eno izmed njih je dokazano, da ob določenih pogojih vrne optimalne rešitve. Hevristiki sta implementirani in testirani na več razredih naključno tvorjenih instanc.
Keywords: problem kitajskega poštarja, problemi usmerjanja, Eulerjev graf, prioritetna vozlišča, modificiran algoritem Dijkstre, modificiran Kruskalov algoritem
Published: 27.05.2010; Views: 3108; Downloads: 317
.pdf Full text (10,28 MB)

4.
Povezavni, vozliščni in mešani okvarni premeri kartezičnih grafovskih produktov in svežnjev
Rija Erveš, 2011, dissertation

Abstract: V disertaciji raziskujemo povezanost in okvarne premere kartezičnih grafovskih svežnjev in kartezičnih produktov. Vpeljemo mešano povezanost in mešani okvarni premer grafa, ki posplošujeta povezanosti in okvarna premera definirana glede na eno vrsto okvarjenih elementov. Nekatere rezultate na kartezičnih grafovskih svežnjih in produktih glede na eno vrsto okvarjenih elementov posplošimo in v določenih primerih tudi izboljšamo.
Keywords: povezanost po vozliščih, povezanost po povezavah, mešana povezanost, okvarni premer, povezavni okvarni premer, mešani okvarni premer, kartezični grafovski sveženj, kartezični grafovski produkt, telekomunikacijska omrežja, okvarna toleranca
Published: 21.09.2011; Views: 3329; Downloads: 143
.pdf Full text (640,76 KB)

5.
Hamiltonskost kartezičnega in direktnega grafovskega svežnja
Irena Hrastnik Ladinek, 2012, dissertation

Abstract: Ciklična svežnjevska Hamiltonskost cbH(G) grafa G je najmanjši n, za katerega obstaja tak avtomorfizem grafa G, da je kartezični grafovski sveženj, katerega baza je cikel na n točkah in vlakno graf G, Hamiltonov graf. Podamo oceno za cbH(G) in to oceno dokažemo. Podamo potrebne in zadostne pogoje za povezanost direktnih grafovskih svežnjev katerih vlakna so cikli. Pokažemo tudi, da so vsi povezani direktni grafovski svežnji ciklov nad cikli Hamiltonovi grafi.
Keywords: kartezični produkt, direktni produkt, kartezični grafovski sveženj, direktni grafovski sveženj, povezanost, Hamiltonov graf, Hamiltonova dekompozicija.
Published: 01.03.2012; Views: 2475; Downloads: 86
.pdf Full text (19,55 MB)

6.
7.
2-local 3/4-competitive algorithm for multicoloring hexagonal graphs
Petra Šparl, Janez Žerovnik, 2005, original scientific article

Abstract: An important optimization problem in the design of cellular networks is to assign sets of frequencies to transmitters to avoid unacceptable interference.A cellular network is generally modeled as a subgraph of the infinite triangular lattice. Frequency assignment problem can be abstracted asa multicoloring problem on a weighted hexagonal graph, where the weights represent the number of calls to be assigned at vertices. In this paper we present a distributed algorithm for multicoloring hexagonal graphs using only the local clique numbers ▫$omega_1(v)$▫ and ▫$omega_2(v)$▫ at each vertex v of the given hexagonal graph, which can be computed from local information available at thevertex. We prove the algorithm uses no more than ▫$4omega(G)/3$▫ colors for any hexagonal graph G, without explicitly computing the global clique number ▫$omega(G)$▫. We also prove that our algorithm is 2-local, i.e., the computation at a vertex v ▫$in$▫ G uses only information about the demands of vertices whose graph distance from v is less than or equal to 2.
Keywords: mathematics, graph theory, graph colouring, 2-local distributed algorithm, cellular networks, frequency planning
Published: 01.06.2012; Views: 1374; Downloads: 65
URL Link to full text

8.
9.
Chinese postman problem with priorities (high cost of delays)
Tomaž Kramberger, Janez Žerovnik, 2008, published scientific conference contribution

Abstract: Several real-world problems, such as street sweeping, mail delivery, solid waste collection, salt gritting and snow plowing can be modeled as Chinese postman problems with some additional constraints. In the paper we present a formal definition of the special case of CPP problem where a subset of priority nodes are given that must be visited as soon as possible, i.e. the cost of delays is much bigger than the cost of additional edges traversed. A heuristical algorithm is proposed which gives near optimal feasible solutions.
Keywords: combinatorial optimization, discrete optimization
Published: 05.06.2012; Views: 916; Downloads: 33
URL Link to full text

10.
Search done in 0.17 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica