Computing multiway cut within the given excess over the largest minimum isolating cut

Details Computing multiway cut within the given excess over the largest minimum isolating cut Computing multiway cut within the given excess over the largest minimum isolating cut

2010-11-29

arxiv.org/abs/1011.6267v1

Computer Science

Data Structures and Algorithms

Scientific paper

Let $(G,T)$ be an instance of the (vertex) multiway cut problem where $G$ is a graph and $T$ is a set of terminals. For $t \in T$, a set of nonterminal vertices separating $t$ from $T \setminus \{T\}$ is called an \emph{isolating cut} of $t$. The largest among all the smallest isolating cuts is a natural lower bound for a multiway cut of $(G,T)$. Denote this lower bound by $m$ and let $k$ be an integer. In this paper we propose an $O(kn^{k+3})$ algorithm that computes a multiway cut of $(G,T)$ of size at most $m+k$ or reports that there is no such multiway cut. The core of the proposed algorithm is the following combinatorial result. Let $G$ be a graph and let $X,Y$ be two disjoint subsets of vertices of $G$. Let $m$ be the smallest size of a vertex $X-Y$ separator. Then, for the given integer $k$, the number of \emph{important} $X-Y$ separators \cite{MarxTCS} of size at most $m+k$ is at most $\sum_{i=0}^k{n \choose i}$.

Affiliated with

Also associated with

No associations

Rating

Computing multiway cut within the given excess over the largest minimum isolating cut does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Computing multiway cut within the given excess over the largest minimum isolating cut, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing multiway cut within the given excess over the largest minimum isolating cut will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-221267