Izbrane teme sodobne fizike in matematike
Problem največje neodvisne množice vozlišč je zanimiv problem iz teorije grafov, z izjemno uporabno vrednostjo pri določanju zaporedja v molekulah deoksiribonukleinskih kislin. V članku je za izhodišče vzeta formulacija problema v obliki celoštevilskega linearnega programa, ki je nato primerjan s svojo relaksacijo in algoritmom za lokalno iskanje na grafu. Primerjava je narejena na podlagi dobljenih množic vozlišč, ki jih algoritmi vračajo, in na podlagi časovne zahtevnosti posameznega algoritma. Analize so izvedene na naključnih grafih z do 100 vozlišči pri različnih verjetnostih povezave med dvema vozliščema. Za analizo časovne zahtevnosti je število vozlišč grafov povečevano do 2401. Na koncu je narejena še analiza na Petersenovem grafu in n-dimenzionalnih hiperkockah za 1 ≤ n ≤ 12. Na slednjih se za učinkovito izkaže tudi relaksacija celoštevilskega linearnega programa, kar omogoča ustrezno primerjavo časovne zahtevnosti vseh treh algoritmov.
Finding the maximum independent vertex set is an intriguing graph theoretical problem that is extremely useful in determining sequences in deoxyribonucleic acids. In this paper, the problem is defined as an integer linear program and contrasted to the relaxation of it. The assessments of the integer linear program, its relaxation, and the algorithm for local search in a graph are based on the output set’s cardinality and the run-time analyses. Experiments are performed on random graphs with up to 100 vertices, which have a different probability of an edge connecting two arbitrary vertices. For analysis of the algorithm’s run-time, the number of vertices is increased to 2401. Finally, tests are carried out on the Petersen graph and n-dimensional hypercubes for 1 ≤ n ≤ 12. On the latter, even the relaxation of the integer linear program successfully finds the maximum independent set, which enabled making insightful comparisons of run-time.