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ößeFormat 
main.pdfFull Thesis2,1 MBAdobe PDFÖffnen/Anzeigen


Diese Ressource wurde unter folgender Copyright-Bestimmung verĂśffentlicht: Lizenz von Creative Commons Creative Commons