1.0Arbeitsgemeinschaft der Universitätsverlagehttps://universitaetsverlage.euXMLRPChttps://universitaetsverlage.eu/author/xmlrpc/rich600338<blockquote class="wp-embedded-content"><a href="https://universitaetsverlage.eu/bucher-e-books/titel/classic-graph-problems-made-temporal-a-parameterized-complexity-analysis-ebook/">Classic graph problems made temporal – a parameterized complexity analysis</a></blockquote> <script type='text/javascript'> <!--//--><![CDATA[//><!-- /*! This file is auto-generated */ !function(d,l){"use strict";var e=!1,o=!1;if(l.querySelector)if(d.addEventListener)e=!0;if(d.wp=d.wp||{},!d.wp.receiveEmbedMessage)if(d.wp.receiveEmbedMessage=function(e){var t=e.data;if(t)if(t.secret||t.message||t.value)if(!/[^a-zA-Z0-9]/.test(t.secret)){var r,a,i,s,n,o=l.querySelectorAll('iframe[data-secret="'+t.secret+'"]'),c=l.querySelectorAll('blockquote[data-secret="'+t.secret+'"]');for(r=0;r<c.length;r++)c[r].style.display="none";for(r=0;r<o.length;r++)if(a=o[r],e.source===a.contentWindow){if(a.removeAttribute("style"),"height"===t.message){if(1e3<(i=parseInt(t.value,10)))i=1e3;else if(~~i<200)i=200;a.height=i}if("link"===t.message)if(s=l.createElement("a"),n=l.createElement("a"),s.href=a.getAttribute("src"),n.href=t.value,n.host===s.host)if(l.activeElement===a)d.top.location.href=t.value}}},e)d.addEventListener("message",d.wp.receiveEmbedMessage,!1),l.addEventListener("DOMContentLoaded",t,!1),d.addEventListener("load",t,!1);function t(){if(!o){o=!0;var e,t,r,a,i=-1!==navigator.appVersion.indexOf("MSIE 10"),s=!!navigator.userAgent.match(/Trident.*rv:11\./),n=l.querySelectorAll("iframe.wp-embedded-content");for(t=0;t<n.length;t++){if(!(r=n[t]).getAttribute("data-secret"))a=Math.random().toString(36).substr(2,10),r.src+="#?secret="+a,r.setAttribute("data-secret",a);if(i||s)(e=r.cloneNode(!0)).removeAttribute("security"),r.parentNode.replaceChild(e,r)}}}}(window,document); //--><!]]> </script><iframe sandbox="allow-scripts" security="restricted" src="https://universitaetsverlage.eu/bucher-e-books/titel/classic-graph-problems-made-temporal-a-parameterized-complexity-analysis-ebook/embed/" width="600" height="338" title="„Classic graph problems made temporal – a parameterized complexity analysis“ — Arbeitsgemeinschaft der Universitätsverlage" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" class="wp-embedded-content"></iframe>https://universitaetsverlage.eu/wp-content/uploads/asolmerce/image-9783798331723.jpg17502483In dieser Dissertation untersuchen wir die parametrisierte Berechnungskomplexität von sechs klassischen Graphproblemen, die in einen temporalen Kontext gestellt werden. Formaler ausgedrückt betrachten wir Probleme, die auf temporalen Graphen definiert sind, wobei temporale Graphen aus einer unveränderlichen Knotenmenge bestehen, zusammen mit einer Kantenmenge, die sich über einen diskreten Zeitraum hinweg verändern darf. Temporale Graphen eignen sich besonders gut zum Modellieren dynamischer Daten und sind daher in Situationen von Bedeutung, in denen dynamische Veränderungen oder zeitabhängige Interaktionen eine wichtige Rolle spielen. Beispiele hierfür sind das Betrachten von Kommunikationsnetzwerken, sozialen Netzwerken oder Netzwerken, deren Interaktionen räumliche Annäherungen modellieren. Das wichtigste Auswahlkriterium für unsere Problemstellungen war, dass sie in Kontexten der Analyse dynamischer Daten wohlmotiviert sind.Da temporale Graphen mathematisch gesehen komplexer sind als statische Graphen, ist es vielleicht nicht sehr überraschend, dass alle Probleme, die wir in dieser Dissertation betrachten, NP-schwer sind. Wir konzentrieren uns auf die Entwicklung exakter Algorithmen, wobei wir versuchen FPT-Resultate zu erzielen oder durch spezialisierte Reduktionen zu zeigen, dass das betrachtete Problem NP-schwer auf sehr eingeschränkten Instanzen ist, oder berechnungsschwer im parametrisierten Sinne bezüglich möglichst „großer“ Parameter ist. Im Kontext temporaler Graphen betrachten wir in erster Linie Strukturparameter des unterliegenden Graphen, das heißt des Graphen, den man erhält, wenn man alle Zeitinformationen ignoriert. Allerdings studieren wir auch andere Parameter, zum Beispiel solche, die das Ausmaß der zeitlichen Veränderung eines temporalen Graphen messen. Im Folgenden geben wir einen kurzen Überblick über unsere Problemstellungen und wichtigsten Ergebnisse.Restless Temporal Paths. Ein Pfad in einem temporalen Graph muss Kausalität oder Zeit respektieren. Dies bedeutet, dass die Kanten, die von dem temporalen Pfad benutzt werden, nicht zu abnehmenden Zeitpunkten erscheinen dürfen. Wir untersuchen temporale Pfade, die darüber hinaus eine maximal erlaubte Wartezeit in allen Knoten haben. Unsere Hauptresultate sind, dass Pfade dieser Art zu finden NP-schwer ist, sogar in sehr restriktiven Instanzen, und dass das Problem W[1]-schwer bezüglich der kreiskritischen Knotenzahl des unterliegenden Graphen ist.Temporal Separators. Ein temporaler Separator ist eine Knotenmenge, die, wenn sie aus einem temporalen Graph entfernt wird, alle temporalen Pfade zwischen zwei iausgewählten Knoten zerstört. Wir erzielen hier zwei Hauptresultate: Auf der einen Seite untersuchen wir die Berechnungskomplexität des Findens von temporalen Separatoren in temporalen Einheitsintervallgraphen, einer Verallgemeinerung von Einheitsintervallgraphen im temporalen Kontext. Wir zeigen, dass das Problem auf temporalen Einheitsintervallgraphen NP-schwer ist, aber identifizieren eine weitere Einschränkung, die es erlaubt, das Problem in Polynomzeit zu lösen. Auf Letzterem aufbauend entwickeln wir einen FPT-Algorithmus, der eine „Distanz-zur-Trivialität“-Parametrisierung nutzt. Auf der anderen Seite zeigen wir, dass das Finden temporaler Separatoren, die alle ruhelosen temporalen Pfade zerstören, Σ-P-2-schwer ist.Temporal Matchings. Wir führen ein Modell für Matchings in temporalen Graphen ein, bei dem sich zwei Knoten „erholen“ müssen, nachdem sie zu einem bestimmten Zeitpunkt einander zugeordnet wurden. Das heißt, für eine gewisse Zeit können diese Knoten nicht wieder einander zugeordnet werden. Wir nutzen das Konzept von temporalen Kantengraphen, um zu zeigen, dass das Finden von temporalen Matchings NP-schwer ist, selbst wenn der unterliegende Graph ein Pfad ist.Temporal Coloring. Wir übertragen das klassische Knotenfärbungsproblem in den temporalen Rahmen. In unserem Modell muss jede Kante in jedem Zeitfenster einer bestimmten Größe mindestens einmal gültig gefärbt sein, also beide Endpunkte eine andere Farbe haben. Wir zeigen, dass dieses Problem schon auf sehr eingeschränkten Instanzen NP-schwer ist – sogar für zwei Farben. Wir beschreiben einfache Exponentialzeitalgorithmen für dieses Problem. Eines unserer Hauptresultate ist, dass diese Algorithmen vermutlich nicht signifikant verbessert werden können.Temporal Cliques and s-Plexes. Wir stellen ein Modell für temporale s-Plexe vor, das eine kanonische Verallgemeinerung eines existierenden Modells für temporale Cliquen ist. Unser Hauptresultat ist ein FPT-Algorithmus, der alle maximalen temporalen s-Plexe aufzählt, wobei wir eine temporale Variante von Degeneriertheit von Graphen als Parameter benutzen.Temporal Cluster Editing. Wir stellen ein Modell für Clustereditierung in temporalen Graphen vor, bei dem wir alle „Schichten“ eines temporalen Graphens in hinreichend ähnliche Cluster überführen wollen. Unsere Hauptergebnisse sind zum einen ein FPT-Algorithmus bezüglich des Parameters „Anzahl der Editierungen plus Ähnlichkeit der Cluster“. Zum anderen geben wir eine effiziente Vorverarbeitungsmethode an, welche die Größe der Eingabeinstanz beweisbar so reduziert, dass sie unabhängig von der Anzahl der Knoten der ursprünglichen Instanz ist.