Istituto di Scienza e Tecnologie dell'Informazione     
Alia G. Reduction of the maximum cut problem to a maximal flow problem for a class of graphs. Internal note IEI-B76-15, 1976.
Finding a maximum cut of an arbitrary graph is a problem contained in a list of 21 NP-complete problems (Karp-Cook list). It is unknow wheter or not any these problems can be solved by a polynomial bounded algorithm. Hadlock has found a polynomial bounded algorithm for finding a maximum cut in planar graphs. In this paper it is shown that the maximum cut problem can be solved in polynomial time when there exists at least one node x in the planar or non planar graph under consideration such that each odd elementary cycle of the graph contains two edges incident to x. The overall computation of the proposed translation process is O(n3) in lenght.

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional