Olga Runge
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Olga Runge has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Claudia Ermel
Technische Universität Berlin
2 shared publications - Hartmut Ehrig
Technische Universität Berlin
2 shared publications - Antonio Bucchiarone
University of L'Aquila, L'Aquila, Italy
1 shared publication - Falk Hüffner
Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany
1 shared publication - Patrizio Pelliccione
Department of Computer Science, Gran Sasso Science Institute, L’Aquila, Italy
1 shared publication - Rolf Niedermeier
Faculty IV Algorithmics and Computational Complexity TU Berlin Germany
1 shared publication
Latest Publications
- 1 January 2015
- Published by Springer Nature
- p. 582-601
Rule-Based Modeling and Static Analysis of Self-adaptive Systems by Graph Transformation
- 1 January 2015
- Published by Springer Nature
- p. 582-601
Rule-Based Modeling and Static Analysis of Self-adaptive Systems by Graph Transformation
- 1 February 2013
- Published by SAGE Publications in Computability
- Vol. 2 (1) , 31-49
Confluence in Data Reduction: Bridging Graph Transformation and Kernelization
Kernelization is a core tool of parameterized algorithmics for coping with computationally intractable problems. A kernelization 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 systematic 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 (EDGE) CLIQUE COVER and PARTIAL 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.
- 1 February 2013
- Published by SAGE Publications in Computability
- Vol. 2 (1) , 31-49
Confluence in Data Reduction: Bridging Graph Transformation and Kernelization
Kernelization is a core tool of parameterized algorithmics for coping with computationally intractable problems. A kernelization 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 systematic 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 (EDGE) CLIQUE COVER and PARTIAL 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.