F.A. Sharifov.
Application of greedy algorithms in combinatorial optimization

The paper considers well-known combinatorial optimization problems such as the maximum cut problem, the stable set problem (finding the maximum independent set of graph vertices), the clique problem, the minimum vertex cover problem, and the Hamiltonian cycle problem. The aim is to construct a mathematical model of these problems in terms of thetheory of polymatroids, to study the functional relationship between their feasible solutions, as well as to describe the solution algorithms.

Keywords: Maximum cut, Stable set, Vertex cover, Clique, Hamiltonian cycles
Copyright © 1997- Institute of Control Systems of Azerbaijan National Academy of Sciences. e-Mail: [email protected]