Računanje notranjega obsega ravninskih grafov : delo diplomskega seminarja

Pirc, Klementina (avtor), Cabello, Sergio (mentor)

Seznanili se bomo s pojmom notranjega obsega ravninskega grafa in predstavili algoritem za njegov izračun s časovno zahtevnostjo O(nlog n) ter del algoritma z linearno zahtevnostjo. Podrobneje si bomo ogledali še povezavo med notranjim obsegom in najmanjšim prerezom ravninskih grafov.

• Jezik: Slovenski jezik
• Ključne besede: notranji obseg, ravninski grafi, algoritem
• Vrsta gradiva: Delo diplomskega seminarja/zaključno seminarsko delo/naloga
• Tipologija: 2.11 - Diplomsko delo
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Leto izida: 2021
• PID: 20.500.12556/RUL-124526
• UDK: 519.17
• COBISS.SI-ID: 58400259
• Datum objave v RUL: 29.01.2021

Sekundarni jezik

• Jezik: Angleški jezik
• Naslov: Computing the girth of a planar graph

Izvleček

After acquainting ourselves with the girth of a planar graph, we first examine an algorithm for computing it in time O(nlog n). Second, we take a look at another procedure that runs in linear time and finally, we examine the connection between the girth and the minimum cut in planar graphs.

• Ključne besede: girth, planar graphs, algorithm