期刊
JOURNAL OF COMBINATORIAL OPTIMIZATION
卷 40, 期 4, 页码 869-875出版社
SPRINGER
DOI: 10.1007/s10878-020-00637-6
关键词
Max cut; Connected max cut; Polynomial algorithm; Min cut; Graphs without the excluded minor K-5\e; Hamilton cycle problem
Given a graph G = (V, E), a connected cut delta(U) is the set of edges of E linking all vertices of U to all vertices of V\U such that the induced subgraphs G[U] and G[V\U] are connected. Given a positive weight function w defined on E, the connected maximum cut problem (CMAX CUT) is to find a connected cut Omega such that w(Omega) is maximum among all connected cuts. CMAX CUT is NP-hard even for planar graphs, and thus for graph without the excluded minor K-5. In this paper, we prove that CMAX CUT is polynomial for the class of graphs without the excluded minor K-5\e, denoted by G(K-5\e). We deduce two quadratic time algorithms: one for the minimum cut problem in G( K-5\e) without computing the maximum flow, and another one for Hamilton cycle problem in the class of graphs without the two excluded minors the prism P-6 and K-3,K-3. This latter problem is NP-complete for maximal planar graphs.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据