Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-3708
For citation please use:
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorNiedermeier, Rolfen
dc.contributor.authorWeller, Mathiasen
dc.date.accessioned2015-11-20T22:32:04Z-
dc.date.available2013-08-26T12:00:00Z-
dc.date.issued2013-08-26-
dc.date.submitted2013-02-25-
dc.identifier.isbn978-3-7983-2509-8-
dc.identifier.uriurn:nbn:de:kobv:83-opus-38783-
dc.identifier.urihttp://depositonce.tu-berlin.de/handle/11303/4005-
dc.identifier.urihttp://dx.doi.org/10.14279/depositonce-3708-
dc.descriptionDie Printversion ist im Universitätsverlag der TU Berlin unter ISBN 978-3-7983-2508-1 erschienen und im Buchhandel lieferbar. .en
dc.description.abstractDiese Arbeit beschäftigt sich mit diversen Aspekten effizienter (also in Polynomzeit ausführbarer) Vorverarbeitung für NP-schwere Probleme im Kontext der Parameterisierten Komplexitätstheorie. Im Einzelnen geht es um Nichtstandardparameter, Linearzeitkernelisierung, Vorverarbeitung ohne Problemkern und parallelisierbare Turingkerne, welche alle von praktischer Relevanz sind. Besonders hervorzuheben ist das letztgenannte Thema, zu welchem erste theoretische Pionierarbeit geleistet wird.de
dc.description.abstractThis work considers multiple aspects of efficient (that is, polynomial-time executable) preprocessing for NP-hard problems in the context of parameterized complexity theory. Special emphasis is put on the following topics: Non-standard parameterization, linear-time kernelization, preprocessing beyond kernelization, and parallelizable Turing kernelization. All these topics are practically relevant and, pioneering work on parallelizable Turing kernelizations, the final topic is of special theoretical interest.en
dc.languageEnglishen
dc.language.isoenen
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/en
dc.subject.ddc004 Datenverarbeitung; Informatiken
dc.subject.otherEffiziente Vorverarbeitungde
dc.subject.otherGraphende
dc.subject.otherKernelisationde
dc.subject.otherNichtstandardparameterde
dc.subject.otherParameterisierte Komplexitätde
dc.subject.otherTheoretische Informatikde
dc.subject.otherTuring Kernelde
dc.subject.otherFixed-Parameter Tractabilityen
dc.subject.otherKernelizationen
dc.subject.otherNetworksen
dc.subject.otherNP-hard Problems preprocessingen
dc.titleAspects of Preprocessing Applied to Combinatorial Graph Problemsen
dc.typeDoctoral Thesisen
tub.accessrights.dnbfree*
tub.publisher.universityorinstitutionUniversitätsverlag der TU Berlinen
dc.contributor.grantorTechnische Universität Berlin, Fakultät IV - Elektrotechnik und Informatiken
dc.date.accepted2012-12-05-
dc.publisher.nameUniversitätsverlag der TU Berlinen
dc.publisher.placeBerlinen
dc.title.translatedAspekte der Vorverarbeitung angewandt auf Kombinatorische Graphproblemede
dc.type.versionpublishedVersionen
tub.identifier.opus33878-
tub.identifier.opus43838-
tub.affiliationFak. 4 Elektrotechnik und Informatik » Inst. Softwaretechnik und Theoretische Informatikde
Appears in Collections:Technische Universität Berlin » Publications

Files in This Item:
weller_mathias.pdf
Format: Adobe PDF | Size: 6.64 MB
DownloadShow Preview
Thumbnail

Item Export Bar

Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.