ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

17. Control Theory and Optimization

1991 MS Classification: 5, 49, 90 Tambieva, Jannet, Karachai-Cherkes Technological Institute, Russia Research of 4-cliques Problem A solution of problem is such sceleton subgraph x = (V, E_{x}) of the given graph G = (V, E) in which every connected component is 4-vertex complete graph, | V |= n = 4k, k = 1, 2, ..., X = {x}, is a set of admisible solutions (SAS); ℜ = (n, R, N) = G, is set of all n-vertexes graph G, in which edges e ∈ E are weighted by weights ω_{ν}(e) ∈ \{1, 2, ..., R\}, ν = \overline{1, N}. The vector objective function (VOF) F (x) = {F_{1}(x), F_{2}(x), ..., F_{N}(x)}, F_{ν}(x) = ∑_{e∈E_{x}} →

min, ν = \overline{1, N} determines Pareto set X ⊆ X. Required solution of vector problem is complete set of alternative (CSA) X^{0}, where the subset has minimal cardinality satisfies to equality F (x^{0}) = F (x) = {F (x) : x ∈ X}. If N ≥ 2 then this problem is hart solvable. Author proposes the polynomial algorithm α. If R^{2N} ≤ n/2(ln n + ln ln n) then algorithm α finds CSA for almost all graphs G ∈ ℜ(n, R, N).