論文

本文へのリンクあり
2019年8月9日

Parameterized Algorithms for Maximum Cut with Connectivity Constraints

CoRR
  • Hiroshi Eto
  • ,
  • Tesshu Hanaka
  • ,
  • Yasuaki Kobayashi
  • ,
  • Yusuke Kobayashi

abs/1908.03389
開始ページ
13
終了ページ
15
記述言語
掲載種別
研究論文(国際会議プロシーディングス)
DOI
10.4230/LIPIcs.IPEC.2019.13

We study two variants of \textsc{Maximum Cut}, which we call
\textsc{Connected Maximum Cut} and \textsc{Maximum Minimal Cut}, in this paper.
In these problems, given an unweighted graph, the goal is to compute a maximum
cut satisfying some connectivity requirements. Both problems are known to be
NP-complete even on planar graphs whereas \textsc{Maximum Cut} on planar graphs
is solvable in polynomial time. We first show that these problems are
NP-complete even on planar bipartite graphs and split graphs. Then we give
parameterized algorithms using graph parameters such as clique-width,
tree-width, and twin-cover number. Finally, we obtain FPT algorithms with
respect to the solution size.

リンク情報
DOI
https://doi.org/10.4230/LIPIcs.IPEC.2019.13
DBLP
https://dblp.uni-trier.de/rec/journals/corr/abs-1908-03389
arXiv
http://arxiv.org/abs/arXiv:1908.03389
URL
http://arxiv.org/abs/1908.03389v1
URL
http://arxiv.org/pdf/1908.03389v1 本文へのリンクあり
ID情報
  • DOI : 10.4230/LIPIcs.IPEC.2019.13
  • DBLP ID : journals/corr/abs-1908-03389
  • arXiv ID : arXiv:1908.03389

エクスポート
BibTeX RIS