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.
Reduction of the maximum cut problem to a maximal flow problem for a class of graphs
1976
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
prod_422482-doc_150234.pdf
accesso aperto
Descrizione: Reduction of the maximum cut problem to a maximal flow problem for a class of graphs
Dimensione
2.1 MB
Formato
Adobe PDF
|
2.1 MB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.