From sorting to edit-clustering
Jérémy Barbay 8 Jun 201008/06/10 a las 18:26 hrs.2010-06-08 18:26:08
From sorting to edit-clustering, by Jeremy <2010-06-08 Tue 14:30-16:00>
1) Adaptivity and Compression
1. Adaptive Searching and Compressed Integers
- Doubling Search [Bentley and Yao]
- Gamma codes
- Experimental Design
- Succinct Data-Structures [Carlos]
2. Adaptive Sorting and Compressed Permutations
- Runs [STACS, Barbay Navarro]
- REM [In Progress, Francisca]
- Local Insertion and ShellSort [Francisca]
3. Binary Merging and Set Compression
- Systematic [Avila and Laber]
- Compressed Succinct Data Structures? [Carlos]
2) Parameterized Complexity and Graph Compression
Can we do the same thing with other, more difficult problems?
* *Vertex Cover*
- Crown reduction = Independent Sets.
- Problem: adding an edge does not change the final
result (nor the kernelisation), hence the signature of
the execution won't give a good encoding.
* *Edge Clique Cover*
- Cover the edges of the graph in a minimum of clique
- param k the size of the partition
- List of rules (to complete)
1. if (u,v)\in E s.t. N[u]=N[v], replace u,v in V by u
- Name K the size of the resulting graph
- Final: brute force if K<2^k, rejection if not.
* *Edge BiClique Cover*
- Cover the edges of the graph in a minimum of biclique
- param k the size of the partition
- List of rules (to complete)
1. if u,v\in V s.t. N[u]=N[v], replace u,v in V by u
- Name K the size of the resulting graph
- Final: brute force if K<2^k, rejection if not.
- 3^k-kernelization algorithm
- www.kr.tuwien.ac.at/ ... /papers/biclique.pdf
* *Edge Clique Partition* and *Edge BiClique Partition*
- same as Edge Clique Cover and Edge BiClique Cover, but the
cliques or bicliques must be disjoint.
- 2^(k+1) for BiClique Partition
crpit.com/confpapers/CRPITV77Mujuni.pdf
* *Cluster Editing*
- How many edges must be added or removed in order to yield a
set of clusters (i.e. a "union of disjoint cliques")
www.springerlink.com/ ... 6gt72h5/fulltext.pdf
* *Vertex Feedback Edge Set*
- Can we remove edges incident to at most k vertices from the
graph so that to reduce it to an acyclic graph?
- There is a kernel of size 4*k with the following rules:
1. Remove all degree-one vertices.
2. For any two neighboring degree-two vertices that do not
have a common neighbor, contract the edge between them.
- The reference is
Jiong Guo, Rolf Niedermeier, Sebastian Wernicke:
Fixed-Parameter Tractability Results for Full-Degree Spanning
Tree and Its Dual. IWPEC 2006: 203-214
www3.interscience.wiley.com/ ... ct?CRETRY=1&SRETRY=0
3) Discussion
- New measures of "compressability" for various data-structures
- Helping to Bridge practice and theory, from the theoretical side.
- better understanding of practical instances
- There are problems where this relation is less usefull:
All problems where the "certificate" is of little
interest. For instance:
- Convex Hull
- (...)
1) Adaptivity and Compression
1. Adaptive Searching and Compressed Integers
- Doubling Search [Bentley and Yao]
- Gamma codes
- Experimental Design
- Succinct Data-Structures [Carlos]
2. Adaptive Sorting and Compressed Permutations
- Runs [STACS, Barbay Navarro]
- REM [In Progress, Francisca]
- Local Insertion and ShellSort [Francisca]
3. Binary Merging and Set Compression
- Systematic [Avila and Laber]
- Compressed Succinct Data Structures? [Carlos]
2) Parameterized Complexity and Graph Compression
Can we do the same thing with other, more difficult problems?
* *Vertex Cover*
- Crown reduction = Independent Sets.
- Problem: adding an edge does not change the final
result (nor the kernelisation), hence the signature of
the execution won't give a good encoding.
* *Edge Clique Cover*
- Cover the edges of the graph in a minimum of clique
- param k the size of the partition
- List of rules (to complete)
1. if (u,v)\in E s.t. N[u]=N[v], replace u,v in V by u
- Name K the size of the resulting graph
- Final: brute force if K<2^k, rejection if not.
* *Edge BiClique Cover*
- Cover the edges of the graph in a minimum of biclique
- param k the size of the partition
- List of rules (to complete)
1. if u,v\in V s.t. N[u]=N[v], replace u,v in V by u
- Name K the size of the resulting graph
- Final: brute force if K<2^k, rejection if not.
- 3^k-kernelization algorithm
- www.kr.tuwien.ac.at/ ... /papers/biclique.pdf
* *Edge Clique Partition* and *Edge BiClique Partition*
- same as Edge Clique Cover and Edge BiClique Cover, but the
cliques or bicliques must be disjoint.
- 2^(k+1) for BiClique Partition
crpit.com/confpapers/CRPITV77Mujuni.pdf
* *Cluster Editing*
- How many edges must be added or removed in order to yield a
set of clusters (i.e. a "union of disjoint cliques")
www.springerlink.com/ ... 6gt72h5/fulltext.pdf
* *Vertex Feedback Edge Set*
- Can we remove edges incident to at most k vertices from the
graph so that to reduce it to an acyclic graph?
- There is a kernel of size 4*k with the following rules:
1. Remove all degree-one vertices.
2. For any two neighboring degree-two vertices that do not
have a common neighbor, contract the edge between them.
- The reference is
Jiong Guo, Rolf Niedermeier, Sebastian Wernicke:
Fixed-Parameter Tractability Results for Full-Degree Spanning
Tree and Its Dual. IWPEC 2006: 203-214
www3.interscience.wiley.com/ ... ct?CRETRY=1&SRETRY=0
3) Discussion
- New measures of "compressability" for various data-structures
- Helping to Bridge practice and theory, from the theoretical side.
- better understanding of practical instances
- There are problems where this relation is less usefull:
All problems where the "certificate" is of little
interest. For instance:
- Convex Hull
- (...)
| Última Modificación | 8 Jun 201008/06/10 a las 18:26 hrs.2010-06-08 18:26:08 |
|---|---|
| Vistas Únicas | 1 |
| Compartir |
