Institut für Wirtschaftsinformatik
Dauerhafte URI für die Sammlunghttps://irf.fhnw.ch/handle/11654/66
Listen
Publikation Combining Bipartite Graph Matching and Beam Search for Graph Edit Distance Approximation(Springer, 2014) Riesen, Kaspar; Fischer, Andreas; Bunke, Horst; El Gayar, Neamat; Schwenker, Friedhelm; Suen, ChengGraph edit distance (GED) is a powerful and flexible graph dissimilarity model. Yet, exact computation of GED is an instance of a quadratic assignment problem and can thus be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, the primary optimization process of this approximation framework is able to consider local edge structures only, and thus, the observed speed up is at the expense of approximative, rather than exact, distance values. In order to improve the overall approximation quality, the present paper combines the original approximation framework with a fast tree search procedure. More precisely, we regard the assignment from the original approximation as a starting point for a subsequent beam search. In an experimental evaluation on three real world data sets a substantial gain of assignment accuracy can be observed while the run time remains remarkable low.04B - Beitrag KonferenzschriftPublikation Computing Upper and Lower Bounds of Graph Edit Distance in Cubic Time(Springer, 2014) Riesen, Kaspar; Fischer, Andreas; Bunke, Horst; El Gayar, Neamat; Schwenker, Friedhelm; Suen, ChengExact computation of graph edit distance (GED) can be solved in exponential time complexity only. A previously introduced approximation framework reduces the computation of GED to an instance of a linear sum assignment problem. Major benefit of this reduction is that an optimal assignment of nodes (including local structures) can be computed in polynomial time. Given this assignment an approximate value of GED can be immediately derived. Yet, since this approach considers local – rather than the global – structural properties of the graphs only, the GED derived from the optimal assignment is suboptimal. The contribution of the present paper is twofold. First, we give a formal proof that this approximation builds an upper bound of the true graph edit distance. Second, we show how the existing approximation framework can be reformulated such that a lower bound of the edit distance can be additionally derived. Both bounds are simultaneously computed in cubic time.04B - Beitrag KonferenzschriftPublikation Open Educational Resources(Springer Gabler, 2017) Bendel, OliverOpen Educational Resources (OER) sind Bildungsmaterialien jeglicher Art und in jedem Medium, die unter einer offenen Lizenz (etwa Creative Commons oder GNU General Public License) veröffentlicht werden. Diese ermöglicht den kostenlosen (mehrheitlich insgesamt bedingungslosen) Zugang sowie die kostenlose Nutzung, Bearbeitung und Weiterverbreitung durch andere Personen und Gruppen ohne oder mit geringfügigen Einschränkungen.04A - Beitrag SammelbandPublikation Qualitätssicherung(Oldenbourg, 2012) Linder, Ute; Haake, Jörg; Schwabe, Gerhard; Wessner, MartinDer Beitrag beschreibt Ansätze zur Qualitätsentwicklung und Qualitätssicherung von Bildungsangeboten, in deren Verlauf Lehrende und Lernende gemeinsam netzbasiert kommunizieren und arbeiten. Es werden zwei Ansätze präsentiert, "Qualitätsmanagement" und "Evaluation", deren Kombination eine Optimierung sowohl einzelner Lernangebote als auch des komplexen Arbeitsprozesses ermöglicht, in dessen Verlauf Lernangebote entstehen.04A - Beitrag Sammelband