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.
1976
Istituto di Scienza e Tecnologie dell'Informazione "Alessandro Faedo" - ISTI
Maximum cut problem
Maximal flow problem
Graphs
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/20.500.14243/382621
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact