-
Algoritmi in ovire za vlaganje grafov v torus : doktorska disertacijaJuvan, MartinDisertacija sodi na področje topološke teorije grafov, tesno pa je povezana tudi s teorijo algoritmov na grafih. V drugem poglavju so predstavljeni nekateri teoretični in algoritmični rezultati o ... izbranem računskem modelu, o povezanosti grafov, o (kombinatornem) opisu vložitev grafov v ploskve in o celični širini vloženih grafov. Tretje poglavje podaja definicije osnovnih pojmov, ki jih potrebujemo pri izbranem pristopu k vlaganju grafov v ploskve. Vpeljani so pojmi, kot so most grafa glede na podgraf, lokalni in globalni most, vložitvena shema, nabor vložitvenih shem, bistveni podgraf, itn. Izpeljane so tudi njihove osnovne lastnosti. V četrtem poglavju obravnavamo posebno vrst razširitvenih problemov; 2 -omejene enostavne celične razširitvene probleme. Opisan je linearni algoritem za reševanje takih razširitvenih problemov, opravljena pa je tudi natančna analiza možnih ovir. Rezultati iz tega poglavja predstavljajo osnovo za linearna algoritma za vlaganje grafov v projektivno ravnino in v torus, ki sta opisana v zadnjih dveh poglavjih. Iz dokazov pravilnosti obeh algoritmov sledi, da za projektivno ravnino in za torus obstaja le končno mnogo prepovedanih podgrafov. V petem poglavju je dokazana tudi zveza med celično širino vložitev v projektivno ravnino in orientabilnim rodom grafa, opisan pa je tudi algoritem, ki v času ▫${\cal O}(kn)$▫ odloči, ali ima v projektivno ravnino vloženi graf z ▫$n$▫ točkami celično širino manjšo od ▫$k$▫. Podan je tudi kratek pregled nekaterih lastnosti prepovedanih podgrafov za projektivno ravnino. V zadnjem poglavju so v opisu linearnega algoritma za iskanje vložitev grafov v torus združeni glavni rezultati iz prejšnjih poglavij. Dodatno so v zadnjem razdelku povzeti znani rezultati o prepovedanih podgrafih za torus in opisani vsi tisti prepovedani minorji za torus, ki imajo vložitev v projektivno ravnino. Ti minorji so bili poiskani s pomočjo računalnika.Vrsta gradiva - disertacija ; neleposlovje za odrasleZaložništvo in izdelava - Ljubljana : [M. Juvan], 1995Jezik - slovenskiCOBISS.SI-ID - 3968345
Avtor
Juvan, Martin
Drugi avtorji
Mohar, Bojan, 1956-
Teme
matematika |
topološka teorija grafov |
vložitev grafa v ploskev |
algoritem |
projektivna ravnina |
torus |
linearni algoritem |
celična širina |
prepovedani podgraf |
minor |
prepovedani minor |
most podgrafa |
topological graph theory |
embeddings of graphs |
algorithm |
projective plane |
torus |
linear algorithms |
face-width |
forbidden subgraph |
minor |
forbidden minor |
bridge
Signatura – lokacija, inventarna št. ... |
Status izvoda | Rezervacija |
---|---|---|
Univerzitetna knjižnica skladišče dis JUVAN MARTIN Algoritmi IN: 04000000310 Univerzitetna knjižnica skladišče dis JUVAN MARTIN Algoritmi IN: 04000000310 |
prosto - za čitalnico
|
Vnos na polico
Trajna povezava
- URL:
Faktor vpliva
Dostop do baze podatkov JCR je dovoljen samo uporabnikom iz Slovenije. Vaš trenutni IP-naslov ni na seznamu dovoljenih za dostop, zato je potrebna avtentikacija z ustreznim računom AAI.
Leto | Faktor vpliva | Izdaja | Kategorija | Razvrstitev | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Baze podatkov, v katerih je revija indeksirana
Ime baze podatkov | Področje | Leto |
---|
Povezave do osebnih bibliografij avtorjev | Povezave do podatkov o raziskovalcih v sistemu SICRIS |
---|---|
Juvan, Martin | 11220 |
Mohar, Bojan, 1956- | 01931 |
Izberite prevzemno mesto:
Prevzem gradiva po pošti
Obvestilo
Gesla v Splošnem geslovniku COBISS
Izbira mesta prevzema
Mesto prevzema | Status gradiva | Rezervacija |
---|
Prosimo, počakajte trenutek.