Objekt-Metadaten
Zur Komplexität von Reduzierbarkeitsproblemen über H-Comparabilitygraphen

Autor :Michael Andresen
Herkunft :OvGU Magdeburg, Fakultät für Mathematik
Datum :03.11.2009
 
Dokumente :
Dataobject from HALCoRe_document_00007938
 
Typ :Dissertation
Format :Text
Kurzfassung :In dieser Arbeit wird das folgende Entscheidungsproblem hinsichtlich seiner Komplexität untersucht. Gegeben ist ein Plan eines Open-Shop Schedulingproblems über einer beliebigen Operationenmenge. Ist dieser Plan irreduzibel? In einer Formulierung mittels sogenannter H-Comparabilitygraphen lautet die Problemstellung für das komplementäre Problem co-IRREDUCIBILITY: "Existiert ein Comparabilitygraph G*, der ein echter Teilgraph von G ist und G(SIJ) als Teilgraph enthält?", wobei G(SIJ) der zu der Operationenmenge SIJ gehörende induzierte Teilgraph des Hamming-Graphen Kn × Km, und G der H-Comparabilitygraph zu dem gegebenen Ausgangsplan ist. Trotz der Ähnlichkeit ist dieses Problem kein Spezialfall des COMPARABILITY-GRAPH-SANDWICH Problems, dessen NP-Vollständigkeit bekannt ist. Bekannt ist die Zugehörigkeit von IRREDUCIBILITY zu co-NP. Untersucht werden die Bedingungen, unter denen IRREDUCIBILITY in NP, und damit im Schnitt von NP und co-NP (= ZPP*), oder sogar in P liegt. Es wird ein Algorithmus vorgestellt, der reduzierbare Pläne nichtdeterministisch reduziert, und irreduzible Pläne nur unter sehr engen Voraussetzungen nicht als irreduzibel erkennen kann. Basierend auf begründeten Zweifeln an der Existenz von Instanzen, die diese engen Voraussetzungen erfüllen, wird vermutet, dass IRREDUCIBILITY in NP liegt. Bei Richtigkeit dieser Vermutung liegt IRREDUCIBILITY entweder in P, oder in NP-incomplete = NP − (P + NP-complete). Die Hinweise auf die Zugehörigkeit zu P werden diskutiert.
Schlagwörter :irreduzible Pläne,H-Comparabilitygraphen,Open-Shop,Komplexität,ZPP*,NP-unvollständig
Rechte :Dieser Text ist urheberrechtlich geschützt
Größe :VI, 186 S.
 
Erstellt am :19.02.2010 - 11:28:29
Letzte Änderung :22.04.2010 - 08:19:19
MyCoRe ID :HALCoRe_document_00007938
Statische URL :http://edoc.bibliothek.uni-halle.de/servlets/DocumentServlet?id=7938