Finding a Maximum Cut of a Planar Graph in Polynomial Time
Author:
- F. HadlockFHF. Hadlock
- 1 September 1975
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 4 (3) , 221-225
Abstract
The problem of finding a maximum cut of an arbitrary graph is one of a list of 21 combinatorial problems (Karp–Cook list). It is unknown whether or not there exist algorithms operating in polynomial bounded time for any of these problems. It has been shown that existence for one implies existence for all. In this paper we deal with a special case of the maximum cut problem. By requiring the graph to be planar, it is shown the problem can be translated into a maximum weighted matching problem for which there exists a polynomial bounded algorithm.Keywords
This publication has 6 references indexed in Scilit:
- Eulerian Walks in GraphsSIAM Journal on Computing, 1973
- Approximation algorithms for combinatorial problems1973
- Reducibility among Combinatorial Problems1972
- GRAPH THEORY1969
- Maximum matching and a polyhedron with 0,1-verticesJournal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics, 1965
- Paths, Trees, and FlowersCanadian Journal of Mathematics, 1965