20.500.12556/RUL-188447 Truncated metric dimension of graphs master's thesis Prirezana metrična dimenzija grafov The $k$-truncated metric dimension is a variant of the metric dimension in which distances greater than $k$ are treated as equal. In this thesis, we study the $k$-truncated metric dimension of several graph classes. We determine its exact value for tadpole graphs, subdivided stars, and multi-tailed tadpole graphs whose pendant paths have order at least $k+1$ after applying the reduction. We also consider generalised tadpole graphs, in which pendant paths satisfying the same condition may be attached to arbitrary vertices of a cycle. For this class, we develop a greedy algorithm for constructing a $k$-truncated resolving set. We prove the correctness of the algorithm, show that it runs in polynomial time for fixed $k$, and establish an approximation ratio of $4/3$. $k$-Prirezana metrična dimenzija je različica metrične dimenzije, pri kateri se vse razdalje, večje od $k$, obravnavajo kot enake. V magistrskem delu preučujemo $k$-prirezano metrično dimenzijo več razredov grafov. Določimo njeno natančno vrednost za cikle s pripetimi potmi in subdividirane zvezde ter za cikle z več pripetimi potmi, pri katerih imajo vse pripete poti po uporabi redukcije red vsaj $k+1$. Obravnavamo tudi posplošene cikle s pripetimi potmi, pri katerih pripete poti zadostujejo enakim pogojem in so lahko pripete na poljubna vozlišča cikla. Za ta razred razvijemo algoritem za konstrukcijo $k$-prirezane razločevalne množice. Dokažemo pravilnost algoritma, pokažemo, da za fiksen $k$ deluje v polinomskem času, ter določimo njegovo aproksimacijsko razmerje $4/3$. k-truncated metric dimension resolving set tadpole graph subdivided star multi-tailed tadpole graph generalised tadpole graph approximation algorithm k-prirezana metrična dimenzija razločevalna množica cikel s pripeto potjo subdividirana zvezda cikel z več pripetimi potmi posplošeni cikel s pripetimi potmi aproksimacijski algoritem true false false Angleški jezik Slovenski jezik Magistrsko delo/naloga 2026-09-23 08:15:13 2026-09-23 08:15:15 2026-09-25 10:28:27 0000-00-00 00:00:00 2026 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 165172 291804675 24014.pdf 24014.pdf 1 73CDC8E591B7B98943FC1D2BCA092EE0 de56ea3b115f69ace2c69fe3f7c9c9649d8ca66e18b5aab028822cf03733d776 135775f2-b716-11f1-8bc5-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=248623 Fakulteta za matematiko in fiziko 0 0 0