Analysis of the combination of a greedy click search algorithm with partial enumeration of graph vertices

Good day.

In my free time I did a little research.

In graph theory, a greedy click number algorithm is known. Far from always, he gives the right result. Under the cut is an analysis of the results of the greedy algorithm when it is combined with partial enumeration of the sets of vertices on the graphs from the DIMACS benchmark set.

The column “Best known” of table 1 shows the sizes of the currently known maximum clicks of the indicated graphs. The “Greedy” column shows the maximum click sizes found by the greedy algorithm. The greedy algorithm gives the correct answer only in 3 cases out of 35.

Note - in the implemented program code, the greedy algorithm selects the vertex with the highest adjacency value. If several similar vertices are found, the first one found is selected. We will call the greedy algorithm procedure Greedy (A), where A is the number of the array (adjacency matrix) to which the algorithm is applied. Index the initial array as A0.

, : N , . m, m – . DelNotAdj(m).

Greedy(m). ( ) «1c-Greedy». , , 8 35.

. , DelNotAdj(m). 0, m. mx. Greedy(mx). ( ) «2-Greedy».

3- (3c-Greedy) C500.9 C1000.9 ω(C500.9)=57, ω(C1000.9)=66.

.

Pascal Greedy(A) O(n²), n – . n , 2- – $$$n!/(2!∙(n-2)!)=(n∙(n-1))/2≈n^2$.. $$$n!/(ω(G)!∙(n-ω(G))!)$, ω(G) – () . .

, , ? 1 , .

( 1). O(n), – ω 1 ω(G) – , ω_GR – , .

«Position» 1 . ꞷ(G) , . «» , .

«B» , 2- .

«*» , «», .. 2, 3 . ω. ω_GRCFG.

, , , , . .. , , , 2- .

«» , :

1. 0 «» . ω_GR.
2. «» m, m . m , . ωGR+1.
3. «» mn, m- n- 0. mn , n- m- . ω_GR+2.
4. 3-, 4-,…, y- ω_GR+3, ω_GR+4,…, ω_GR+y .
5. 0 — ω(G).

. «» «B» :

, , ω_GR. ω_GR+1 ω_GR, , K – .

«*» :

«» ω_GR, ω_GR+1, ω_GR+2,…, ω(G) . , , . , ω_GR.

: ω_GR, ω_GR+1, ω_GR+2,… , « » ( ω_GRCDE 1).

:

1. «» ω_GR+y,
ω_GR+y-1, , K – .

.

2. y- ω_GR+y, , .. ω_GR+y=ω_GR+y-1, , ω_GR+y ω(G) .

If the above repeats someone else’s work, I’m not out of spite, I will be glad to see the link. I will be even more glad if someone theoretically can prove or disprove the proposed hypotheses.