| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


21 - 30 / 72
Na začetekNa prejšnjo stran12345678Na naslednjo stranNa konec
21.
Adaptive identification in torii in triangular grids
Matjaž Kovše, Peter Stanet, 2012, izvirni znanstveni članek

Opis: Pri adaptivni identifikaciji postavljamo vprašanja, eno za drugim, pri čemer je dovoljeno postaviti vprašanje, glede na do tistega trenutka prejete odgovore na predhodna vprašanja. Cilj je odkriti (potencialno) okvarjeno vozlišče v grafu. Na adaptivno identifikacijo lahko gledamo tudi kot na igro, kjer prvi igralec skrivoma izbere vozlišče, ki bo okvarjeno, ali ne izbere nobenega vozlišča, drugi igralec pa postavlja vprašanja kot "ali se nahaja okvarjeno vozlišče v krogli $B(v)$ s središčem v vozlišču $v$?" za vozlišča grafa $G$. Cilj prvega igralca je maksimizirati število potrebnih vprašanj. Cilj drugega igralca je minimizirati to število. V članku obravnavamo adaptivno identifikacijo v torusih na trikotniški mreži.
Ključne besede: identifikacijske kode, adaptivna identifikacija, trikotniške mreže, identifying codes, adaptive identification, triangular grids
Objavljeno: 10.07.2015; Ogledov: 762; Prenosov: 10
URL Povezava na celotno besedilo

22.
Extremal graphs for the identifying code problem
Florent Foucaud, Eleonora Guerrini, Matjaž Kovše, Reza Naserasr, Aline Parreau, Petru Valicov, 2011, izvirni znanstveni članek

Opis: Identifikacijska koda grafa ▫$G$▫ je dominacijska množica ▫$C$▫ za katero velja, da se vsako vozlišče ▫$x$▫ iz grafa ▫$G$▫ razlikuje od preostalih vozlišč grafa pomnožici vozlišč iz ▫$C$▫, ki so na razdalji kvečjemu 1 od vozlišča ▫$x$▫. Problem iskanja identifikacijske kode minimalne velikosti se je izkazal za velik izziv. Avtorji N. Bertrand, I. Charon, O. Hudry in A. Lobstein so pokazali, da v primeru grafa na ▫$n$▫ vozliščih in z vsaj eno povezavo, ki premore identifikacijsko kodo, velja, da je velikost minimalne identifikacijske kode kvečjemu ▫$n-1$▫. Podali so tudi razrede grafov, katerih velikost minimalne kode je natanko ▫$n-1$▫. Postavljenih je bilo nekaj domnev v zvezi s karakterizacijo razredov grafov, katerih velikost minimalne kode je natanko ▫$n-1$▫. V članku so ovržene domneve in podana je karakterizacija vseh končnih grafov, ki potrebuje vsa razen enega vozlišča v identifikacijski kodi. Podana je karakterizacija vseh neskončnih grafov, ki potrebuje celotno množico vozlišč za poljubno identifikacijsko kodo. Podane so tudi nove zgornje meje za minimalne identifikacijske kode, ki so izražene z številom vozlišč grafa in maksimalno stopnjo vozlišč v grafu.
Ključne besede: teorija grafov, neskončni grafi, dominacijska množica, identifikacijske kode, graph theory, infinite graphs, domination set, identifying codes
Objavljeno: 10.07.2015; Ogledov: 638; Prenosov: 71
URL Povezava na celotno besedilo

23.
Retracts of products of chordal graphs
Boštjan Brešar, Jérémie Chalopin, Victor Chepoi, Matjaž Kovše, Arnaud Labourel, Yann Vaxès, 2010

Opis: We characterize the graphs ▫$G$▫ that are retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain ▫$K_{2;3}$▫, ▫$k$▫-wheels ▫$W_k$▫, and ▫$k$▫-wheels minus one spoke T$W_k^- ; (k ge 4)$T as induced subgraphs. We also show that these graphs ▫$G$▫ are exactly the cage-amalgamation graphs introduced by Brešar and Tepeh Horvat (2009); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of $G$ by products of "solid" simplices, we obtain a polyhedral cell complex which, endowed with an intrinsic Euclidean metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1-skeletons of CAT(0) cubical complexes.
Ključne besede: teorija grafov, graf, retrakt, zastražena amalgamacija, tetiven graf, kartezični produkt grafov, medianski graf, graph theory, graph, retract, gated amalgamation, chordal graph, Cartesian product of graphs, median graph
Objavljeno: 10.07.2015; Ogledov: 525; Prenosov: 80
URL Povezava na celotno besedilo

24.
Geodetic sets in graphs
Boštjan Brešar, Matjaž Kovše, Aleksandra Tepeh, 2011, samostojni znanstveni sestavek ali poglavje v monografski publikaciji

Opis: Na kratko so povzeti rezultati o geodetskih množicah v grafih. Po pregledu rezultatov iz prejšnjih raziskav se posvetimo geodetskemu številu in sorodnim invariantam v grafih. Podrobno so obravnavane geodetske množice kartezičnih produktov grafov in geodetske množice v medianskih grafih. Predstavljen je tudi algoritmični vidik in povezava z nekaterimi ostalimi koncepti iz teorije konveksnih in intervalskih struktur v grafih.
Ključne besede: matematika, teorija grafov, geodetsko število, geodetska množica, kartezični produkt, medianski graf, mejna množica, mathematics, graph theory, geodetic number, geodetic set, Cartesian product, median graph, boundary set
Objavljeno: 10.07.2015; Ogledov: 342; Prenosov: 21
URL Povezava na celotno besedilo

25.
Simultaneous embeddings of graphs as median and antimedian subgraphs
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2010, izvirni znanstveni članek

Opis: Razdalja ▫$D_G(v)$▫ vozlišča ▫$v$▫ v grafu ▫$G$▫ je vsota razdalj med ▫$v$▫ in vsemi drugimi vozlišči grafa ▫$G$▫. Množica vozlišč grafa ▫$G$▫ z maksimalno (minimalno) razdaljo je antimedianska (medianska) množica grafa ▫$G$▫. Dokazano je, da za poljubna grafa ▫$G$▫ in ▫$J$▫ ter za poljubno naravno število ▫$r ge 2$▫ obstaja povezani graf ▫$H$▫, tako da je ▫$G$▫ antimedianski in ▫$J$▫ medianski podgraf grafa ▫$H$▫ ter da pri tem velja ▫$d_H(G,J) = r$▫. V primeru, ko sta oba ▫$G$▫ in ▫$J$▫ povezana, lahko dodatno naredimo, da sta ▫$G$▫ in ▫$J$▫ konveksna podgrafa v ▫$H$▫.
Ključne besede: matematika, teorija grafov, problemi razmeščanja, medianske množice, antimedianske množice, konveksni podgrafi, mathematics, graph theory, facility location problems, median sets, antimedian sets, convex subgraphs
Objavljeno: 10.07.2015; Ogledov: 568; Prenosov: 78
URL Povezava na celotno besedilo

26.
On the remoteness function in median graphs
Kannan Balakrishnan, Boštjan Brešar, Manoj Changat, Wilfried Imrich, Sandi Klavžar, Matjaž Kovše, Ajitha R. Subhamathi, 2009, izvirni znanstveni članek

Opis: Profil grafa ▫$G$▫ je poljubna neprazna multimnožica vozlišč iz ▫$G$▫. Pripadajoča funkcija oddaljenosti priredi vsakemu vozlišču iz ▫$V(G)$▫ vsoto razdalj do vozlišč iz profila. Najprej so dobljene nekatere uporabne lastnosti funkcije oddaljenosti na hiperkockah, nato pa je funkcija oddaljenosti obravnavana na poljubnih medianskih grafih glede na njihove izometrične vložitve v hiperkocke. V posebnem je najdena povezava med vozlišči medianskega grafa ▫$G$▫, katerega funkcija oddaljenosti je največja (antimedianska množica v ▫$G$▫), z antimediansko množico pripadajoče hiperkocke. Medtem ko je za lihe profile antimedianska množica neodvisna množica, ki leži na strogem robu medianskega grafa, obstajajo medianski grafi, v katerih določeni sodi profili porajajo konstantno funkcijo oddaljenosti. Take medianske grafe karakteriziramo na dva načina: kot grafe, katerih periferna transverzala je 2, in kot grafe z geodetskim številom 2. Nazadnje predstavimo algoritem, ki za dani graf ▫$G$▫ z ▫$n$▫ vozlišči in ▫$m$▫ povezavami v času ▫$O(m log n)$▫ odloči, ali je ▫$G$▫ medianski graf z geodetskim številom 2.
Ključne besede: hiperkocka, medianski graf, medianska množica, funkcija oddaljenosti, geodetsko število, periferna transverzala, median graph, median set, remoteness function, geodetic number, periphery transverzal, hypercube
Objavljeno: 10.07.2015; Ogledov: 617; Prenosov: 83
URL Povezava na celotno besedilo

27.
Lattice embeddings of trees
Wilfried Imrich, Matjaž Kovše, 2009, izvirni znanstveni članek

Opis: Predstavljen je algoritem časovno linearne zahtevnosti, ki na izometričen način vloži dano drevo ▫$T$▫ v celoštevilsko mrežo najmanjše možne dimenzije in omogoča izračun mrežnih koordinat vozlišč drevesa ▫$T$▫ v optimalnem času.
Ključne besede: matematika, teorija grafov, drevo, izometrična vložitev, mrežna vložitev, delna kocka, mathematics, graph theory, lattice embedding, isometric embedding, partial cube, tree
Objavljeno: 10.07.2015; Ogledov: 479; Prenosov: 62
URL Povezava na celotno besedilo

28.
Cover-incomparability graphs of posets
Boštjan Brešar, Manoj Changat, Sandi Klavžar, Matjaž Kovše, Joseph Mathews, Antony Mathews, 2008, izvirni znanstveni članek

Opis: Vpeljemo graf pokritij-neprimerljivosti (ki mu na kratko rečemo CI-graf), katerega množica povezav je unija množic povezav grafa neprimerljivosti in grafa pokritja dane delno urejene množice. S pomočjo prepovedanih izometričnih delno urejenih podmnožic, okarakteriziramo tiste delno urejene množice, katerih CI-graf je tetiven (razdaljno-hereditaren, ptolemajski) in predlagamo splošen pristop k obravnavi CI-grafov. Predstavimo tudi več odprtih problemov.
Ključne besede: matematika, teorija grafov, delno urejena množica, temeljni graf, tranzitna funkcija, tetiven graf, razdaljno-hereditaren graf, mathematics, graph theory, poset, underlying graph, transit function, chordal graph, distance-hereditary graph, claw
Objavljeno: 10.07.2015; Ogledov: 562; Prenosov: 78
URL Povezava na celotno besedilo

29.
Game chromatic number of Cartesian product graphs
T. Bartnicki, Boštjan Brešar, J. Grytczuk, Matjaž Kovše, Z. Miechowicz, Iztok Peterin, 2008, izvirni znanstveni članek

Opis: Obravnavamo igralno kromatično število ▫$chi_g$▫ kartezičnega produkta ▫$G Box H$▫ dveh grafov ▫$G$▫ in ▫$H$▫. Določimo točne vrednosti za ▫$chi_g(K_2 Box H$▫, ko je ▫$H$▫ pot, cikel ali poln graf. S pomočjo novo vpeljane "igre kombinacij" pokažemo, da igralno kromatično število ni omejeno znotraj razreda kartezičnih produktov dveh polnih dvodelnih grafov. Iz tega rezultata sledi, da igralno kromatično število ▫$chi_g(G Box H$▫ ni navzgor omejeno s kako funkcijo igralnih kromatičnih števil grafov ▫$G$▫ in ▫$H$▫. Analogen rezultat je izpeljan za igralno barvno število kartezičnih produktov grafov.
Ključne besede: matematika, teorija grafov, kartezični produkt grafov, igralno kromatično število, mathematics, graph theory, Cartesian prodict, game chromatic number
Objavljeno: 10.07.2015; Ogledov: 596; Prenosov: 186
URL Povezava na celotno besedilo

30.
Partial cubes and their [tau]-graphs
Sandi Klavžar, Matjaž Kovše, 2007, izvirni znanstveni članek

Opis: Za delno kocko ▫$G$▫ ima ▫$tau$▫-graph ▫$G^tau$▫ ekvivalenčne razrede Djokovic-Winklerjeve relacije kot vozlišča, pri čemer sta razreda ▫$E$▫ in ▫$F$▫ sosednja, če neki povezavi ▫$e in E$▫ in ▫$f in F$▫ inducirata konveksno pot ▫$P_3$▫. Dokazano je, da za vsak graf $G$ obstaja medianski graf ▫$M$▫, tako da velja ▫$G = M^tau$▫, da je ▫$G^tau$▫ povezan natanko tedaj, ko je ▫$G$▫ pragraf glede na kartezični produkt grafov in da je ▫$tau$▫-graf medianskega grafa ▫$G$▫ brez ▫$K_n$▫ natanko tedaj, ko ▫$G$▫ ne vsebuje konveksnega ▫$K_{1,n}$▫.
Ključne besede: matematika, teorija grafov, delne kocke, medianski grafi, kartezični produkt grafov, mathematics, graf theory, partial cubes, median graphs, Cartesian product graphs
Objavljeno: 10.07.2015; Ogledov: 492; Prenosov: 22
URL Povezava na celotno besedilo

Iskanje izvedeno v 0.33 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici