Science-advisor
REGISTER info/FAQ
Login
username
password
     
forgot password?
register here
 
Research articles
  search articles
  reviews guidelines
  reviews
  articles index
My Pages
my alerts
  my messages
  my reviews
  my favorites
 
 
Stat
Members: 3643
Articles: 2'487'895
Articles rated: 2609

29 March 2024
 
  » arxiv » 1411.6915

 Article overview


Kernelization Algorithms for Packing Problems Allowing Overlaps
Henning Fernau ; Alejandro López-Ortiz ; Jazmín Romero ;
Date 25 Nov 2014
AbstractWe consider the problem of discovering overlapping communities in networks which we model as generalizations of the Set and Graph Packing problems with overlap.
As usual for Set Packing problems we seek a collection $mathcal{S}$ consisting of at least $k$ sets subject to certain disjointness restrictions. In a Set Packing with $t$-Membership, each element of $mathcal{U}$ belongs to at most $t$ sets while in a Set Packing with $t$-Overlap each pair of sets overlaps in at most $t$ elements. For both problems, each set of $mathcal{S}$ has at most $r$ elements, and $t$ and $r$ are constants.
Similarly, both of our graph packing problems seek a collection of at least $k$ subgraphs in a graph $G$ each isomorphic to a graph $H in mathcal{H}$. In an $mathcal{H}$-Packing with $t$-Membership, each vertex of $G$ belongs to at most $t$ subgraphs while in an $mathcal{H}$-Packing with $t$-Overlap each pair of subgraphs overlaps in at most $t$ vertices. For both problems, each member of $mathcal{H}$ has at most $r$ vertices, and $t$ and $r$ are constants.
We provide NP-Completeness results for all of our packing problems. Given that, we reduce the Set Packing with $t$-Overlap to an $O(r^r k^{r-t-1})$ problem kernel while we achieve an $O(r^r k^{r-1})$ problem kernel for the Set Packing with $t$-Membership. In addition, we reduce the $mathcal{H}$-Packing with $t$-Membership and its induced version to an $O(r^r k^{r-1})$ kernel. Moreover, we give an $O(r^{2r^2} k^{{r^2}-1})$ kernel for its edge version. On the other hand, we achieve an $O(r^r k^{r-t-1})$ kernel for the $mathcal{H}$-Packing with $t$-Overlap and its induced version while we provide an $O(r^{2r^2} k^{r^2-t-1})$ kernel for its edge version. Our kernel results match the best kernel for Set and Graph Packing.
Source arXiv, 1411.6915
Services Forum | Review | PDF | Favorites   
 
Visitor rating: did you like this article? no 1   2   3   4   5   yes

No review found.
 Did you like this article?

This article or document is ...
important:
of broad interest:
readable:
new:
correct:
Global appreciation:

  Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.

browser claudebot






ScienXe.org
» my Online CV
» Free


News, job offers and information for researchers and scientists:
home  |  contact  |  terms of use  |  sitemap
Copyright © 2005-2024 - Scimetrica