D.Priefer, P.Kneisel, W.Rost, D.Strüber, G.Taentzer
Applying MDD in the Content Management System Domain: Scenarios and Empirical Assessment
IEEE / ACM 22nd International Conference on Model Driven Engineering Languages and Systems (MODELS), 2019, Munich, Germany, in press.
In this paper, we present a mixed-method empirical investigation of applying MDD in the CMS domain, based on an interview suite, a controlled experiment, and a field experiment. We consider three scenarios of developing new (both independent and dependent) CMS extensions and of migrating existing ones to a new major platform version. The experienced developers in our interviews acknowledge the relevance of these scenarios and report on experiences that render them suitable candidates for a successful application of MDD. We found a particularly high relevance of the migration scenario. Our experiments largely confirm the potentials and limits of MDD as identified for other domains. In particular, we found a productivity increase up to factor 17 during the development of CMS extensions. Furthermore, our observations highlight the importance of good tooling that seamlessly integrates with already used tool environments and processes.
Frank Kammer, Johannes Meintrup, Andrej Sajenko
Space-Efficient Vertex Separator for Treewidth
Practical applications that use treewidth algorithms have graphs with treewidth k = O(n1/3). Given such n-vertex graphs we present a word-RAM algorithm to compute vertex separators using only O(n) bits of working memory. As an application of our algorithm, we show an O(1)-approximation algorithm for tree decomposition. Our algorithm computes a tree decomposition in ck n(log* n) log log n time using O(n) bits for some constant c.
We finally show that our tree-decomposition algorithm can be used to solve several monadic second-order problems using O(n) bits as long as the treewidth of the graph is smaller than c' log n for some constant 0 < c' < 1.
Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, Jakob T. Spooner
Two Moves per Time Step Make a Difference
A temporal graph is a graph whose edge set can change over time. We only require that the edge set in each time step forms a connected graph. The temporal exploration problem asks for a temporal walk that starts at a given vertex, moves over at most one edge in each time step, visits all vertices, and reaches the last unvisited vertex as early as possible. We show in this paper that every temporal graph with n vertices can be explored in O(n1.75) time steps provided that either the degree of the graph is bounded in each step or the temporal walk is allowed to make two moves per step. This result is interesting because it breaks the lower bound of Ω(n2) steps that holds for the worst-case exploration time if only one move per time step is allowed and the graph in each step can have arbitrary degree. We complement this main result by a logarithmic inapproximability result and a proof that for sparse temporal graphs (i.e., temporal graphs with O(n) edges in the underlying graph) making O(1) moves per time step can improve the worst-case exploration time at most by a constant factor.