20.500.12556/RUL-188557 Izboljševanje zgornjih mej za problem največje klike z uporabo redukcijskih pravil magistrsko delo Improving upper bounds for the maximum clique problem using reduction rules V tem delu preučujemo povezavo med redukcijskimi pravili in funkcijami zgornje meje za problem največje klike. Pokažemo, kako lahko funkcije zgornje meje okrepijo klasični redukciji z jedri in paličji, če lokalne pogoje o velikosti nadomestimo z izračuni zgornje meje. Tako dobimo $(k,\omega^u)$-jedro in $(k,\omega^u)$-paličje, uvedemo pa tudi splošnejšo različico, imenovano $(k,d,\omega^u)$-paličje, pri kateri parameter $d$ določa razmerje med močnejšimi redukcijami in dodatnim računskim časom. Za vse te pojme dokažemo lastnosti ohranjanja klik, pravilnost pripadajočih algoritmov in njihovo časovno zahtevnost. Na podlagi teh redukcij uvedemo splošno ogrodje za izboljševanje zgornjih mej pri problemu največje klike. Predstavimo dve konkretni izvedbi ogrodja: prva uporablja združeni redukciji s paličji in jedri, druga pa ju dopolni s ponavljajočo se uporabo strukcije. Računski poskusi na 73 testnih grafih pokažejo, da lahko predlagane redukcije bistveno izboljšajo več standardnih funkcij zgornje meje in da je združevanje različnih redukcijskih metod v praksi koristno. Kombinacija strukcije ter redukcij s paličji in jedri je ob uporabi meje na podlagi algoritma DSatur pogosto dosegla vrednosti na ravni semidefinitnega programiranja hitreje kot neposredni izračun semidefinitne meje; pri testiranih grafih z gostoto povezav pod 0,7 je bila hitrejša v vsakem primeru. Z uporabo redukcije s paličji in jedri ter Lovászeve funkcije theta izboljšamo tudi doslej najboljše certificirane celoštevilske zgornje meje za tri zahtevne primere DIMACS, katerih natančna klična števila niso znana: za graf C500.9 s 83 na 73, za graf C1000.9 s 122 na 115 in za graf C2000.9 s 177 na 168. In this work we study the interaction between reduction rules and upper-bound functions for the Maximum Clique Problem (MCP). We show how MCP upper-bound functions can strengthen classical core and truss reductions by replacing local size conditions with upper-bound tests. This leads to the $(k,\omega^u)$-core and the $(k,\omega^u)$-truss; we also define the more general $(k,d,\omega^u)$-truss, where the parameter $d$ controls the trade-off between stronger reductions and additional computational cost. For each of these notions, we prove clique-preservation properties, correctness of the corresponding peeling algorithm, and running-time bounds. Based on these reductions, we introduce a general framework for improving upper-bound values for MCP. We give two concrete instantiations of the framework: one that uses only the combined truss and core reductions, and one that combines the truss and core reductions with repeated applications of structions. Computational experiments on 73 benchmark graphs show that the proposed reductions can substantially improve several standard upper-bound functions and that combining multiple reduction methods can be beneficial in practice. In particular, the combination of structions, truss and core reductions with a DSatur-based bound often reached SDP-level upper-bound values faster than direct SDP computation; on the tested graphs with edge density below 0.7, it did so in every case. Using the truss and core reduction with the Lovász theta upper-bound function, we also improve the previously best certified integer upper-bound values for three difficult DIMACS instances whose exact clique numbers are not known. In particular, we improve upper-bound values for graph C500.9 from 83 to 73, for graph C1000.9 from 122 to 115, and for graph C2000.9 from 177 to 168. problem največje klike zgornje meje redukcije razcep na jedra razcep na paličja strukcija testni primeri DIMACS maximum clique problem upper bounds reductions core decomposition truss decomposition struction DIMACS benchmarks true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2026-09-24 08:15:32 2026-09-24 08:15:37 2026-09-25 04:28:17 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.1 165297 292011267 24502.pdf 24502.pdf 1 14963409DC88DBCC5036B05253D9BB28 538e5a7cd3dbf54b236211a77f0e58e7466d17a03dc7e9291754bfc80392098d 49c7c0a1-b7df-11f1-8bc5-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=248805 Fakulteta za matematiko in fiziko 0 0 0