This article is cited in 1 paper

Solving the weighted $k$-separator problem in graphs with specific modules

V. V. Lepin

Institute of Mathematics of the National Academy of Sciences of Belarus

Abstract: Given a graph $G$ with a vertex weight function $\omega_V:~V(G)\to\mathbb{R}^+$ and a positive integer $k,$ we consider the $k$-separator problem: it consists in finding a minimum-weight subset of vertices whose removal leads to a graph where the size of each connected component is less than or equal to $k.$ Using the notion of modular decomposition we extend the class of graphs on which this problem can be solved in polynomial time. For a graph $G$ that is modular decomposable into $\pi(G)\subseteq\{P_4,\ldots,P_m\}\cup\{C_5,\ldots,C_m\}$ we give an $O(n^2)$ algorithm for finding the minimum weight of $k$-separators. The algorithm solves this problem for cographs in time $O(n).$ Moreover, we give an $O(n)$ time algorithm solving this problem for the series-parallel graphs.

UDC: 519.1

Received: 10.01.2016