Računanje notranjega obsega ravninskih grafov : delo diplomskega seminarja

Pirc, Klementina (author), 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.

• Language: Slovenian
• Keywords: notranji obseg, ravninski grafi, algoritem
• Work type: Bachelor thesis/paper
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2021
• PID: 20.500.12556/RUL-124526
• UDC: 519.17
• COBISS.SI-ID: 58400259
• Publication date in RUL: 29.01.2021

Secondary language

• Language: English
• Title: Computing the girth of a planar graph

Abstract

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.

• Keywords: girth, planar graphs, algorithm