-
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.Type of material - dissertation ; adult, seriousPublication and manufacture - Ljubljana : [M. Juvan], 1995Language - slovenianCOBISS.SI-ID - 3968345
Author
Juvan, Martin
Other authors
Mohar, Bojan, 1956-
Topics
matematika |
topološka teorija grafov |
vložitev grafa v ploskev |
algoritmi |
projektivna ravnina |
torus |
linearni algoritmi |
celična širina |
prepovedani podgrafi |
minorji |
prepovedani minorji |
most podgrafa |
disertacije |
topological graph theory |
embeddings of graphs |
algorithm |
projective plane |
torus |
linear algorithms |
face-width |
forbidden subgraph |
minor |
forbidden minor |
bridge
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Call number – location, accession no. ... |
Copy status | Reservation |
---|---|---|
Skladišče II 0000055079 Skladišče II 55079 |
available - reading room
|
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
![loading ... loading ...](themes/default/img/ajax-loading.gif)
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Juvan, Martin | 11220 |
Mohar, Bojan, 1956- | 01931 |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.