Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-35098
Titel: | Counting patterns in strings and graphs |
VerfasserIn: | Wellnitz, Philip |
Sprache: | Englisch |
Erscheinungsjahr: | 2021 |
DDC-Sachgruppe: | 500 Naturwissenschaften 510 Mathematik |
Dokumenttyp: | Dissertation |
Abstract: | We study problems related to finding and counting patterns in strings and graphs. In the string-regime, we are interested in counting how many substring of a text đ are at Hamming (or edit) distance at most đ to a pattern đ. Among others, we are interested in the fully-compressed setting, where both đ and đ are given in a compressed representation. For both distance measures, we give the first algorithm that runs in (almost) linear time in the size of the compressed representations. We obtain the algorithms by new and tight structural insights into the solution structure of the problems. In the graph-regime, we study problems related to counting homomorphisms between graphs. In particular, we study the parameterized complexity of the problem #IndSub(đˇ), where we are to count all đ-vertex induced subgraphs of a graph that satisfy the property đˇ. Based on a theory of LovĂĄsz, Curticapean et al., we express #IndSub(đˇ) as a linear combination of graph homomorphism numbers to obtain #W[1]-hardness and almost tight conditional lower bounds for properties đˇ that are monotone or that depend only on the number of edges of a graph. Thereby, we prove a conjecture by Jerrum and Meeks. In addition, we investigate the parameterized complexity of the problem #Hom(â â đ˘) for graph classes â and đ˘. In particular, we show that for any problem đ in the class #W[1], there are classes â_đ and đ˘_đ such that đ is equivalent to #Hom(â_đ â đ˘_đ ). Wir untersuchen Probleme im Zusammenhang mit dem Finden und Zählen von Mustern in Strings und Graphen. Im Stringbereich ist die Aufgabe, alle Teilstrings eines Strings đ zu bestimmen, die eine Hamming- (oder Editier-)Distanz von hĂśchstens đ zu einem Pattern đ haben. Unter anderem sind wir am voll-komprimierten Setting interessiert, in dem sowohl đ, als auch đ in komprimierter Form gegeben sind. FĂźr beide Abstandsbegriffe entwickeln wir die ersten Algorithmen mit einer (fast) linearen Laufzeit in der GrĂśĂe der komprimierten Darstellungen. Die Algorithmen nutzen neue strukturelle Einsichten in die LĂśsungsstruktur der Probleme. Im Graphenbereich betrachten wir Probleme im Zusammenhang mit dem Zählen von Homomorphismen zwischen Graphen. Im Besonderen betrachten wir das Problem #IndSub(đˇ), bei dem alle induzierten Subgraphen mit đ Knoten zu zählen sind, die die Eigenschaft đˇ haben. Basierend auf einer Theorie von LovĂĄsz, Curticapean, Dell, and Marx drĂźcken wir #IndSub(đˇ) als Linearkombination von Homomorphismen-Zahlen aus um #W[1]-Härte und fast scharfe konditionale untere Laufzeitschranken zu erhalten fĂźr đˇ, die monoton sind oder nur auf der Kantenanzahl der Graphen basieren. Somit beweisen wir eine Vermutung von Jerrum and Meeks. Weiterhin beschäftigen wir uns mit der Komplexität des Problems #Hom(â â đ˘) fĂźr Graphklassen â und đ˘. Im Besonderen zeigen wir, dass es fĂźr jedes Problem đ in #W[1] Graphklassen â_đ und đ˘_đ gibt, sodass đ äquivalent zu #Hom(â_đ â đ˘_đ ) ist. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291--ds-350981 hdl:20.500.11880/32103 http://dx.doi.org/10.22028/D291-35098 |
Erstgutachter: | Mehlhorn, Kurt |
Tag der mĂźndlichen PrĂźfung: | 2-Dez-2021 |
Datum des Eintrags: | 23-Dez-2021 |
Fakultät: | SE - Sonstige Einrichtungen |
Fachrichtung: | SE - Max-Planck-Institut fĂźr Informatik |
Professur: | SE - Sonstige |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | GrĂśĂe | Format | |
---|---|---|---|---|
main.pdf | Full Thesis | 2,1 MB | Adobe PDF | Ăffnen/Anzeigen |
Diese Ressource wurde unter folgender Copyright-Bestimmung verĂśffentlicht: Lizenz von Creative Commons