delo diplomskega seminarja
Klementina Pirc (Author), Sergio Cabello (Mentor)

Abstract

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.

Keywords

teorija grafov;notranji obseg;ravninski grafi;algoritmi;

Data

Language: Slovenian
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UL FMF - Faculty of Mathematics and Physics
Publisher: [K. Pirc]
UDC: 519.17
COBISS: 58400259 Link will open in a new window
Views: 822
Downloads: 80
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Computing the girth of a planar graph
Secondary 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.
Secondary keywords: graph theory;girth;planar graphs;algorithms;
Type (COBISS): Final seminar paper
Study programme: 0
Embargo end date (OpenAIRE): 1970-01-01
Thesis comment: Univ. v Ljubljani, Fak. za matematiko in fiziko, Oddelek za matematiko, Matematika - 1. stopnja
Pages: 29 str.
ID: 12512664
Recommended works:
, delo diplomskega seminarja
, no subtitle data available
, diplomsko delo
, magistrsko delo
, diplomsko delo