Gast ::
| 001 | 993329 | ||
| 005 | 20241118140723.0 | ||
| 024 | 7 | _ | |2 HBZ |a HT030882911 |
| 024 | 7 | _ | |2 Laufende Nummer |a 43700 |
| 024 | 7 | _ | |2 datacite_doi |a 10.18154/RWTH-2024-08648 |
| 037 | _ | _ | |a RWTH-2024-08648 |
| 041 | _ | _ | |a English |
| 082 | _ | _ | |a 004 |
| 100 | 1 | _ | |0 P:(DE-82)IDM03515 |a Fluck, Eva |b 0 |u rwth |
| 245 | _ | _ | |a Graph decompositions : a study on decompositions of graphs and their application to logic and data science |c vorgelegt von Eva Fluck, Master of Science |h online |
| 260 | _ | _ | |a Aachen |b RWTH Aachen University |c 2024 |
| 300 | _ | _ | |a 1 Online-Ressource : Illustrationen |
| 336 | 7 | _ | |0 2 |2 EndNote |a Thesis |
| 336 | 7 | _ | |0 PUB:(DE-HGF)11 |2 PUB:(DE-HGF) |a Dissertation / PhD Thesis |b phd |m phd |
| 336 | 7 | _ | |2 BibTeX |a PHDTHESIS |
| 336 | 7 | _ | |2 DRIVER |a doctoralThesis |
| 336 | 7 | _ | |2 DataCite |a Output Types/Dissertation |
| 336 | 7 | _ | |2 ORCID |a DISSERTATION |
| 500 | _ | _ | |a Veröffentlicht auf dem Publikationsserver der RWTH Aachen University |
| 502 | _ | _ | |a Dissertation, RWTH Aachen University, 2024 |b Dissertation |c RWTH Aachen University |d 2024 |g Fak01 |o 2024-08-16 |
| 520 | 3 | _ | |a Wir untersuchen Zerlegungen von Graphen und deren Anwendung im Bereich der Expressivität von Zähllogik und im Bereich des Clusteranalyse von Daten. Abgesehen von den Zerlegungen selbst, betrachtet wir Graphparameter, die aus diesen Zerlegungen abgeleitet werden können, sowie Hindernisse für die Existenz guter Zerlegungen. Wir nennen die Klasse aller Graphen mit einer Zerlegung von beschränkter Baumtiefe, in der auch die Weite beschränkt ist, T^k_q . Dawar, Jakl und Reggio (2021) zeigen das die Homomorphismusununterscheidbarkeitsrelation dieser der Expressivität von Zähllogik entspricht. Ideen von Dvořák (2010) aufgreifend, können wir diese Verbindung erneut nachweisen. Darauf aufbauend konstruieren wir eine Graphklasse, die die Equivalenz unter überwachter Zähllogik beschreibt. Eine graphtheoretische Analyse von T^k_q zeigt das diese unterschiedlich ist vom Schnitt von TW_{k−1} (Baumweite höchstens k − 1) und TD_q (Baumtiefe höchstens q), wenn q ausreichend größer ist als k. Wir erhalten eine neue Beschreibung von Baumtiefe über Baumzerlegungen und ein Cops-und-Robber Spiel das T^k_q erfasst. Um die Separation auf die Equivalenzrelationen zu übertragen, zeigen wir, dass dieses Spiel monoton ist, dass heißt, dass Robber keinen Knoten erreichen kann, der bereits geräumt wurde. Dies gibt einen neuartigen Beweis der Monotonie des Cops-und-Robber Spiels für Baumweite, der ohne ein duales Objekt, wie Brambels, auskommt. Dies gibt uns, dass T^k_q und TD_q unter Homomorphismusunterscheidbarkeit abgeschlossen sind, was bereits von Roberson (2022) vermutet wurde. Tangles formalisieren Regionen mit hohem Zusammenhang in Graphen widerspruchsfrei. Auf abstrakte Zusammenhangssysteme übersetzt, beschreiben sie diese im unterliegenden Universum. Vor kurzem sind sie als Ansatz in der Clusteranalyse aufgekommen. Wir zeigen, dass die nichttrivialen Cluster des hierarchischen Single-Linkage-Verfahren, genau die Tangles einer entsprechend gewählten Zusammenhangsfunktion sind. Wir verallgemeinern dies zu einer Eins-zu-eins-Beziehung zwischen maximum-submodularen Zusammenhangsfunktionen und Dendogrammen, also einem beliebigen hierarchischem Clustering. Wir untersuchen auch flaches, weiches Clustering. Wir interpretieren Tangles als Cluster und untersuchen die Existenz von unvergleichbaren Tangles, also unterscheidbaren Clustern, in Daten die aus einer gemischten Gaussverteilung gezogen werden. Wir finden explizite Bedingungen so dass diese asymptotisch fast sicher existieren. Zuletzt untersuchen wir Zerlegungen in Graphklassen jenseits von Bäumen. Hier ist die Anzahl der Knoten in einem Beutel nicht länger ein nichttrivialer Weitebegriff, sobald die Graphklasse unbeschränkte Baumweite hat. Wir untersuchen eine Weitebegriff, der verwandt zu Baumbreite ist. Diesen nennen wir radiale Weite und wir messen den Radius des durch einen Beutel induzierten Teilgraphen. Wir finden verbotete Teilgraphen für jeden zusammenhängenden Graphen mit beschränkter radialer F-Weite, wobei entsprechend die Graphklasse aller Pfade, Kreise oder unterteilter Sterne ist. |l ger |
| 520 | _ | _ | |a We study decompositions of graphs and their application to the expressiveness of first-order logic with counting quantifiers and clustering data. Besides the decompositions themselves we also consider graph parameters that arise from these decompositions as well as obstructions to the existence of good decompositions. The graph class T^k_q are all graphs which have a bounded tree-depth decomposition that also bounds the width. Its homomorphism indistinguishability relation enjoys a rich connection to the expressiveness of counting logic, as shown by Dawar, Jakl and Reggio (2021). Building upon ideas by Dvořák (2010), we re-prove this connection. Our proof strategy also enables to construct a graph class which characterizes equivalence under guarded counting logic. A graph theoretic analysis of T^k_q allows us separate it from the intersection of TW_{k−1} , the class of graphs of tree-width at most k − 1, and TD_q the graphs of tree-depth at most q, if q is sufficiently larger than k. This also yields a new characterization of tree-depth via tree-decompositions and a characterization of T^k_q via a Cops-and-Robber game. To lift this separation to the respective equivalence relations, we show that this game is monotone, that is Robber can never reach a vertex that was cleared in some earlier round. This also give a novel proof of the monotonicity of the Cops-and-Robber game for tree-width without the use of any dual object, like brambles. Another part of the separation of the equivalence classes is to prove that T^k_q and TD_q are homomorphism distinguishing closed, which was conjectured by Roberson (2022). Tangles are a concept to formalize regions of high connectivity in graphs in an unambiguous way. It can be translated to more abstract connectivity systems, where they describe highly connected regions in the underling universe. Recently they emerged as a new approach to clustering data. We find that the non-trivial clusters resulting from the well known single linkage hierarchical clustering algorithm are exactly the tangles of an appropriately chosen connectivity function on the data points. We generalize this connection to a one-to-one correspondence between connectivity functions that are maximum-submodular and dendograms which are a way to represent the result of an arbitrary hierarchical clustering algorithm. Beyond that we study tangles as an approach to flat, fuzzy clustering. We interpret the tangles as clusters and study the existence of incomparable tangles, that is distinct clusters, in a data set drawn from a Gaussian mixture. We find explicit conditions such that asymptotically almost surely such clusters exists. Finally we study decompositions into graph classes beyond trees. Here we find that the number of vertices in a bag is no longer a non-trivial width measure if the graph class has unbounded tree-width. Therefore we study a different notion of width related to tree-breadth that we call radial-width where we measure the radius of the subgraph induced by a bag. We find forbidden subgraphs for any connected graph of bounded radial F-width for the graph classes F of all paths, cycles and subdivided stars respectively. |l eng |
| 588 | _ | _ | |a Dataset connected to Lobid/HBZ |
| 591 | _ | _ | |a Germany |
| 700 | 1 | _ | |0 P:(DE-82)IDM00084 |a Grohe, Martin |b 1 |e Thesis advisor |u rwth |
| 700 | 1 | _ | |0 P:(DE-82)996627 |a Adler, Isolde |b 2 |e Thesis advisor |
| 856 | 4 | _ | |u https://publications.rwth-aachen.de/record/993329/files/993329.pdf |y OpenAccess |
| 856 | 4 | _ | |u https://publications.rwth-aachen.de/record/993329/files/993329_source.zip |y Restricted |
| 909 | C | O | |o oai:publications.rwth-aachen.de:993329 |p openaire |p open_access |p VDB |p driver |p dnbdelivery |
| 910 | 1 | _ | |0 I:(DE-588b)36225-6 |6 P:(DE-82)IDM03515 |a RWTH Aachen |b 0 |k RWTH |
| 910 | 1 | _ | |0 I:(DE-588b)36225-6 |6 P:(DE-82)IDM00084 |a RWTH Aachen |b 1 |k RWTH |
| 914 | 1 | _ | |y 2024 |
| 915 | _ | _ | |0 StatID:(DE-HGF)0510 |2 StatID |a OpenAccess |
| 920 | 1 | _ | |0 I:(DE-82)122910_20140620 |k 122910 |l Lehrstuhl für Logik und Theorie diskreter Systeme (Informatik 7) |x 0 |
| 920 | 1 | _ | |0 I:(DE-82)120000_20140620 |k 120000 |l Fachgruppe Informatik |x 1 |
| 980 | 1 | _ | |a FullTexts |
| 980 | _ | _ | |a I:(DE-82)120000_20140620 |
| 980 | _ | _ | |a I:(DE-82)122910_20140620 |
| 980 | _ | _ | |a UNRESTRICTED |
| 980 | _ | _ | |a VDB |
| 980 | _ | _ | |a phd |
| Library | Collection | CLSMajor | CLSMinor | Language | Author |
|---|