Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 519.8
F.A. Sharifov1

FINDING MAXIMUM CUT BY THE GREEDY ALGORITHM

Abstract. The paper considers the problem of finding the maximum cut on graphs. A new model of the problem is given in terms of the base of polymatroid. It is shown that the problem solution can be found by the greedy algorithm after the optimal linear ordering of the vertices has been determined.

Keywords: maximum cut, bipartite subgraph, linear ordering.



FULL TEXT


1 V. M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

fasharifov@gmail.com

© 2018 Kibernetika.org. All rights reserved.