id: 06057349
dt: a
an: 06057349
au: Zhang, Peng
ti: Partial degree bounded edge packing problem.
so: Snoeyink, Jack (ed.) et al., Frontiers in algorithmics and algorithmic
    aspects in information and management. Joint international conference,
    FAW-AAIM 2012, Beijing, China, May 14‒16, 2012. Proceedings. Berlin:
    Springer (ISBN 978-3-642-29699-4/pbk). Lecture Notes in Computer
    Science 7285, 359-367 (2012).
py: 2012
pu: Berlin: Springer
la: EN
cc: 
ut: 
ci: 
li: doi:10.1007/978-3-642-29700-7_33
ab: Summary: In [1], whether a target binary string $s$ can be represented from
    a boolean formula with operands chosen from a set of binary strings $W$
    was studied. In this paper, we first examine selecting a maximum subset
    $X$ from $W$, so that for any string $t$ in $X$, $t$ is not
    representable by $X \setminus {t}$. We rephrase this problem as graph,
    and surprisingly find it give rise to a broad model of edge packing
    problem, which itself falls into the model of forbidden subgraph
    problem. Specifically, given a graph $G(V,E)$ and a constant $c$, the
    problem asks to choose as many as edges to form a subgraph
    $G^{\prime}$. So that in $G^{\prime}$, for each edge, at least one of
    its endpoints has degree no more than $c$. We call such $G^{\prime}$
    partial $c$ degree bounded. This edge packing problem model also has a
    direct interpretation in resource allocation. There are $n$ types of
    resources and $m$ jobs. Each job needs two types of resources. A job
    can be accomplished if either one of its necessary resources is shared
    by no more than $c$ other jobs. The problem then asks to finish as many
    jobs as possible. For edge packing problem, when $c = 1$, it turns out
    to be the complement of dominating set and able to be 2-approximated.
    When $c = 2$, it can be 32/11-approximated. We also prove it is
    NP-complete for any constant $c$ on graphs and is $O(|V|^{2})$ solvable
    on trees. We believe this partial bounded graph problem is intrinsic
    and merits more attention.
rv: