TY  - THES
AB  - Parametrisierte Komplexitätstheorie beschreibt eine neu-denierte Klassikation von schweren Problemen basierend auf einem mehrdimensionalen Design und der Komplexitätsanalyse von deterministischen Algorithmen. Die Forschung von parametrisierter Komplexität wurde auf das parallele Rechnen erweitert und ist im Allgemeinen als Parametrisierte Parallele Komplexität bekannt. Diese Arbeit konzentriert sich auf die Fragestellung, welche Probleme effiziente parametrisierbare parallele Algorithmen erlauben. Ein Problem ist fixed-parameter parallel-tractable (FPPT), wenn es einen Algorithmus gibt, der Laufzeit O(f(k)(log n)) mit O(n) parallelen Prozessoren hat. Wir präsentieren einen effizienten parallelen Algorithmus für das generelle MONOTONE CIRCUIT VALUE PROBLEM mit n Gattern und einem zugrunde liegenden Graphen mit k-begrenzendem Geschlecht. Insbesondere implizieren unsere Ergebnisse, dass für ein gegebenes P-vollständiges Problem ein Algorithmus gefunden werden kann, der das Problem in NC sein lässt durch Fixierung von ein oder mehreren Parametern. Wenn wir uns auf P-vollständige Probleme eingrenzen, existiert folgende Analogie: FPPT für P-vollständige Probleme ist ähnlich wie FPT für NP-vollständige Probleme. Diese Arbeit erweitert das FPPT Framework zu einer generellen Kernelmethode, crown decomposition. Aus diesem Ergebnis erhalten wir direkt einen effizienten parallelen Algorithmus, der den besten bekannten parallelen Algorithmus für das VERTEX COVER PROBLEM verbessert. Daher ist sowohl die parallele crown decomposition als auch die parametrisierte Knotenüberdeckung in FPPT.Des Weiteren haben wir einen weiteren Parameter, die modular-width, untersucht. Wir haben die Forschung von modular-width auf die parametrisierte parallele Komplexität erweitert und zeigen.
AU  - Li, Shouwei
CY  - Paderborn
DA  - 2017
DO  - 10.17619/UNIPB/1-252
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 12.10.2017
N1  - Universität Paderborn, Dissertation, 2017
PB  - Veröffentlichungen der Universität
PY  - 2017
SP  - 1 Online-Ressource (xii, 53 Seiten)
T2  - Heinz Nixdorf Institut (HNI)
TI  - Parallel fixed parameter tractable problems
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-30011
Y2  - 2025-01-25T02:13:07
ER  -