Finding a Maximum Cut of a Planar Graph in Polynomial Time 论文
1975SIAM Journal on Computing引用 395
Advanced Graph Theory ResearchComplexity and Algorithms in GraphsOptimization and Search Problems
详细信息
- 发表期刊/会议
- SIAM Journal on Computing
- 发表日期
- 1975-09-01
- 发表年份
- 1975
关键词
Advanced Graph Theory ResearchComplexity and Algorithms in GraphsOptimization and Search Problems
摘要
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.