Measure & Conquer (M&C) is the prominent technique for analyzing exact algorithms for computationally hard problems. It tries to balance worse and better situations within the algorithm analysis. Several obstacles prevent the application of this technique in parameterized algorithmics, making it rarely applied in this area. However, these difficulties can be handled in some situations. We will exemplify this with two problems related to VERTEX COVER, namely CONNECTED VERTEX COVER and EDGE DOMINATING SET. For both problems, several parameterized algorithms have been published, all based on the idea of first enumerating minimal vertex covers and then producing sohitions to the requested problem. Using M&C in this context will improve on the hitherto published running times, offering some unifying view. In contrast to some of the earlier suggested algorithms, ours will use polynomial space.
展开▼
