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...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | article |
| منشور في: |
2007
|
| الوصول للمادة أونلاين: | 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 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| الملخص: | 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. |
|---|