20.500.12556/RUL-176722 Metode barvnega označevanja za iskanje izomorfnih podgrafov magistrsko delo Color-coding methods for finding subgraph isomorphisms Magistrsko delo obravnava metodo barvnega označevanja, algoritemsko tehniko za reševanje problema izomorfizma podgrafov. Ta problem, ki je NP-poln, se pojavlja v računalniškem vidu, bioinformatiki, kemoinformatiki in podatkovnem rudarjenju. Delo se uvodoma osredotoča na teoretične osnove problema izomorfizma podgrafov in njegovo parametrizirano kompleksnost, nato pa podrobno predstavi metodo barvnega označevanja, ki so jo leta 1994 razvili Noga Alon, Raphael Yuster in Uri Zwick. V osrednjem delu so analizirane različne tehnike znotraj barvnega označevanja: metoda naključnih orientacij, metoda naključnih barvanj in derandomizacija omenjenih algoritmov. Posebna pozornost je namenjena iskanju vozlišč barvitih poti s konceptom prič v množenju matrik. Delo raziskuje tudi razširitev metode na iskanje dreves in kompleksnejših podgrafov z omejeno drevesno širino. Predstavljena je povezava med barvnim označevanjem in degeneriranostjo grafov s poudarkom na minorsko zaprtih družinah grafov, kjer je predstavljena metoda za iskanje ciklov. V zaključku so predstavljene napredne strategije za izboljšanje metode, vključno z barvanjem po intervalih, metodo razvrščanja in premikanja, tehniko reprezentativnih množic in metodo deli in barvaj. Delo vključuje tudi eksperimentalno analizo, kjer so rezultati meritev različnih algoritmov barvnega označevanja in drugih pristopov za iskanje izomorfnih podgrafov prikazani na praktičnih primerih. Magistrsko delo združuje teoretične dokaze in algoritme z uporabnimi vpogledi v praktično vrednost metode barvnega označevanja pri reševanju zahtevnih problemov na različnih grafih. This master's thesis explores the color-coding method, an algorithmic technique for solving the subgraph isomorphism problem. This NP-complete problem appears in computer vision, bioinformatics, cheminformatics, and data mining. The thesis begins with an introduction to the theoretical foundations of the subgraph isomorphism problem and its parameterized complexity, followed by a detailed presentation of the color-coding method developed by Noga Alon, Raphael Yuster, and Uri Zwick in 1994. The core of the thesis analyzes various techniques within color-coding: the method of random orientations, the method of random colorings, and the derandomization of these algorithms. Special attention is given to finding vertices of colorful paths using the concept of witnesses in matrix multiplication. The thesis also investigates the extension of the method to finding trees and more complex subgraphs with bounded treewidth. It presents the connection between color-coding and graph degeneracy, with emphasis on minor-closed graph families, where a method for finding cycles is introduced. The conclusion presents advanced strategies for improving the method, including interval-based coloring, the order-and-shift method, the technique of representative sets, and the divide-and-color method. The thesis also includes experimental analysis, where the results of measurements of various color-coding algorithms and other approaches for finding isomorphic subgraphs are presented on practical examples. The master's thesis combines theoretical proofs and algorithms with practical insights into the utility of the color-coding method for solving challenging problems on large graphs. barvno označevanje izomorfizem podgrafov algoritmi na grafih color-coding subgraph isomorphism graph algorithms true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2025-12-10 08:15:06 2025-12-10 08:15:13 2025-12-24 03:56:54 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 156783 260443139 21084.pdf 21084.pdf 1 D3EFDDE7C2E9CAE92246B82A92FA8DC1 2966be38bd30460f5e74f945057bbdbd7ce09320f4cc0f45cd7ad17a244d6836 8de09016-d597-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=223248 Fakulteta za matematiko in fiziko 0 0 0