Automated Generation of Search Tree Algorithms for Hard GraphModification Problems |
| |
Authors: | Jens Gramm Jiong Guo Falk Hüffner Rolf Niedermeier |
| |
Affiliation: | (1) Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, Sand 13, D-72076 Tübingen, , Germany |
| |
Abstract: | We present a framework for an automated generation of exact search tree algorithms for NP-hard problems.The purpose of our approach is twofold—rapid development and improved upper bounds. Many search tree algorithms for various problemsin the literature are based on complicatedcase distinctions. Our approach may lead to a much simpler process of developing and analyzing these algorithms.Moreover, using the sheer computing power of machines it may also lead to improved upper bounds onsearch tree sizes (i.e., faster exact solving algorithms) in comparisonwith previously developed hand-made search trees.Among others, such an example is given with the NP-complete Cluster Editing problem (also known as CorrelationClustering on complete unweighted graphs), which asks for the minimumnumber of edge additions and deletions to create a graph which is adisjoint union of cliques. Thehand-made search treefor Cluster Editinghad worst-case size O(2.27k), which now is improved to O(1.92k) due to our new method.(Herein, k denotes the number of edge modifications allowed.) |
| |
Keywords: | NP-hard problems Graph modification Search tree algorithms Exact algorithms Automated development and analysis of algorithms Algorithm engineering |
本文献已被 SpringerLink 等数据库收录! |
|