| | 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


1 - 3 / 3
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Characterizing posets for which their natural transit functions coincide
Boštjan Brešar, Manoj Changat, Sandi Klavžar, Joseph Mathews, Antony Mathews, Prasanth G. Narasimha-Shenoi, 2009, izvirni znanstveni članek

Opis: Standardna tranzitna funkcija delno urejene množice ▫$P$▫ je funkcija ▫$T_P$▫, ki vsakemu paru primerljivih elementov priredi interval med njima, za neprimerljiva elementa ▫$x,y$▫ pa je ▫$T_P(x,y) = {x,y}$▫. Na tri načine, tudi s prepovedanimi delno urejenimi podmnožicami, okarakteriziramo tiste delno urejene množice, v katerih standardna tranzitna funkcija sovpada s tranzitno funkcijo najkrajših poti njenega grafa pokritij-neprimerljivosti.
Ključne besede: matematika, teorija grafov, tranzitna funkcija, rangirana delno urejena množica, temeljni graf, geodetski interval, interval induciranih poti, mathematics, graph theory, transit function, ranked poset, underlying graph, geodesic interval, induced-path interval
Objavljeno: 10.07.2015; Ogledov: 497; Prenosov: 58
URL Povezava na celotno besedilo

2.
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: 301; Prenosov: 54
URL Povezava na celotno besedilo

3.
Cover-incomparability graphs and chordal graphs
Boštjan Brešar, Manoj Changat, Tanja Gologranc, Joseph Mathews, Antony Mathews, 2010, izvirni znanstveni članek

Opis: Problem prepoznavanja grafov pokritij-neprimerljivosti (to je grafov, ki jih dobimo iz delno urejenih množic kot povezavno unijo njihovega grafa pokritij in grafa neprimerljivosti) je NP-poln v splošnem, kot so dokazali v [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], medtem ko je na primer očitno polinomski v razredu dreves. V tem članku se osredotočimo na razrede tetivnih grafov in dokažemo, da je vsak graf pokritij-neprimerljivosti, ki je tetiven graf, kar graf intervalov. Okarakteriziramo tiste delno urejene množice, ki imajo za graf pokritij-neprimerljivosti bločni graf, oziroma razcepljeni graf in tudi okarakteriziramo grafe pokritij-neprimerljivosti med bločnimi, oziroma razcepljenimi grafi. Slednji karakterizaciji dasta tudi linearen algoritem za prepoznavanje bločnih, oziroma razcepljenih grafov, ki so grafi pokritij-neprimerljivosti.
Ključne besede: matematika, teorija grafov, delno urejena množica, temeljni graf, tetiven graf, razcepljen graf, bločni graf, mathematics, graph theory, poset, underlying graph, chordal graph, split graf, block graph
Objavljeno: 10.07.2015; Ogledov: 444; Prenosov: 49
URL Povezava na celotno besedilo

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