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: