Pseudo-Kernelization
Pseudo-kernelization is introduced in this paper as a new strategy for improving fixed-parameter algorithms. This new technique works for bounded search tree algorithms by identifying favorable branching conditions whose absence could be used to reduce the size of corresponding problem instances. Ps...
Saved in:
| Main Author: | |
|---|---|
| Format: | article |
| Published: |
2007
|
| Online Access: | http://hdl.handle.net/10725/2770 http://dx.doi.org/10.1007/s00224-007-1344-0 http://link.springer.com/article/10.1007/s00224-007-1344-0 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Pseudo-kernelization is introduced in this paper as a new strategy for improving fixed-parameter algorithms. This new technique works for bounded search tree algorithms by identifying favorable branching conditions whose absence could be used to reduce the size of corresponding problem instances. Pseudo-kernelization applies well to hitting set problems. It can be used either to improve the search tree size of a 3-Hitting-Set algorithm from O*(2.179k) to O*(2.05k), or to improve the kernel size from k3 to 27k. In this paper the parameterized 3-Hitting-Set and Face Cover problems are used as typical examples. |
|---|