id: 05544685
dt: j
an: 05544685
au: Ishii, Toshimasa
ti: Minimum augmentation of edge-connectivity with monotone requirements in
    undirected graphs.
so: Discrete Optim. 6, No. 1, 23-36 (2009).
py: 2009
pu: Elsevier B. V., Amsterdam
la: EN
cc: 
ut: undirected graph; connectivity augmentation problem; monotone requirement;
    polynomial time deterministic algorithm
ci: 
li: doi:10.1016/j.disopt.2008.08.002
ab: Summary: For a finite ground set $V$, we call a set-function $r:2^V\to\Bbb
    Z^+$ monotone, if $r(X’)\ge r(X)$ holds for each $X’\subseteq
    X\subseteq V$, where $\Bbb Z^+$ is the set of nonnegative integers.
    Given an undirected multigraph $G=(V,E)$ and a monotone requirement
    function $r:2^V\to\Bbb Z^+$, we consider the problem of augmenting $G$
    by a smallest number of new edges, so that the resulting graph $G’$
    satisfies $d_{G’}(X)\ge r(X)$ for each $\emptyset\ne X\subset V$,
    where $d_G(X)$ denotes the degree of a vertex set $X$ in $G$. This
    problem includes the edge-connectivity augmentation problem, and in
    general, it is NP-hard, even if a polynomial time oracle for $r$ is
    available. In this paper, we show that the problem can be solved in
    $O(n^4(m+n\log n+q))$ time, under the assumption that each
    $\emptyset\ne X\subset V$ satisfies $r(X)\ge2$ whenever $r(X)>0$, where
    $n=|V|$, $m=|\{\{u,v\}\mid (u,v)\in E\}|$, and $q$ is the time required
    to compute $r(X)$ for each $X\subseteq V$.
rv: