direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Publications Olga Runge

Confluence in Data Reduction: Bridging Graph Transformation and Kernelization
Zitatschlüssel EEH+12
Autor Hartmut Ehrig and Claudia Ermel and Falk Hüffner and Rolf Niedermeier and Olga Runge
Buchtitel Proc. of Int. Conf. on Computability in Europe (CiE'12)
Seiten 193-202
Jahr 2012
Jahrgang 7318
Herausgeber S. Barry Cooper and Anuj Dawar
Verlag Springer
Serie LNCS
Zusammenfassung Kernelization is a core tool of parameterized algorithmics for coping with computationally intractable problems. A \emphkernelization reduces in polynomial time an input instance to an equivalent instance whose size is bounded by a function only depending on some problem-specific parameter $k$; this new instance is called problem kernel. Typically, problem kernels are achieved by performing efficient data reduction rules. So far, there was little study in the literature concerning the mutual interaction of data reduction rules, in particular whether data reduction rules for a specific problem always lead to the same reduced instance, no matter in which order the rules are applied. This corresponds to the concept of confluence from the theory of rewriting systems. We argue that it is valuable to study whether a kernelization is confluent, using the NP-hard graph problems \textsc(Edge) Clique Cover and \textscPartial Clique Cover as running examples. We apply the concept of critical pair analysis from graph transformation theory, supported by the AGG software tool. These results support the main goal of our work, namely, to establish a fruitful link between (parameterized) algorithmics and graph transformation theory, two so far unrelated fields.
Download Bibtex Eintrag

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe