A note on small cuts for a terminal
classification
💻 cs.DS
keywords
smallterminalansweringarxivaskedcontainscutsedges
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.