pith. sign in

arxiv: 1306.2578 · v2 · pith:DUP3U635new · submitted 2013-06-11 · 💻 cs.DS

A note on small cuts for a terminal

classification 💻 cs.DS
keywords smallterminalansweringarxivaskedcontainscutsedges
0
0 comments X
read the original abstract

Given a graph $G = (V,E)$ and a terminal $s\in V$, a cut $X$ for $s$ is a vertex set that contains $s$. We look for a cut that is small in two senses, i.e., there are no more than $k$ vertices in $X$ and no more than $t$ edges leaving $X$. Answering a question asked by Fomin et al. (arXiv:1304.6189), we show the problem is fixed-parameter tractable parameterized by either $k$ or $t$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.