Aspects of Preprocessing Applied to Combinatorial Graph Problems

Weller, Mathias

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 Field	Value	Language
dc.contributor.advisor	Niedermeier, Rolf	en
dc.contributor.author	Weller, Mathias	en
dc.date.accessioned	2015-11-20T22:32:04Z	-
dc.date.available	2013-08-26T12:00:00Z	-
dc.date.issued	2013-08-26	-
dc.date.submitted	2013-02-25	-
dc.identifier.isbn	978-3-7983-2509-8	-
dc.identifier.uri	urn:nbn:de:kobv:83-opus-38783	-
dc.identifier.uri	http://depositonce.tu-berlin.de/handle/11303/4005	-
dc.identifier.uri	http://dx.doi.org/10.14279/depositonce-3708	-
dc.description	Die Printversion ist im Universitätsverlag der TU Berlin unter ISBN 978-3-7983-2508-1 erschienen und im Buchhandel lieferbar. .	en
dc.description.abstract	Diese 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.abstract	This 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.language	English	en
dc.language.iso	en	en
dc.rights.uri	http://rightsstatements.org/vocab/InC/1.0/	en
dc.subject.ddc	004 Datenverarbeitung; Informatik	en
dc.subject.other	Effiziente Vorverarbeitung	de
dc.subject.other	Graphen	de
dc.subject.other	Kernelisation	de
dc.subject.other	Nichtstandardparameter	de
dc.subject.other	Parameterisierte Komplexität	de
dc.subject.other	Theoretische Informatik	de
dc.subject.other	Turing Kernel	de
dc.subject.other	Fixed-Parameter Tractability	en
dc.subject.other	Kernelization	en
dc.subject.other	Networks	en
dc.subject.other	NP-hard Problems preprocessing	en
dc.title	Aspects of Preprocessing Applied to Combinatorial Graph Problems	en
dc.type	Doctoral Thesis	en
tub.accessrights.dnb	free	*
tub.publisher.universityorinstitution	Universitätsverlag der TU Berlin	en
dc.contributor.grantor	Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik	en
dc.date.accepted	2012-12-05	-
dc.publisher.name	Universitätsverlag der TU Berlin	en
dc.publisher.place	Berlin	en
dc.title.translated	Aspekte der Vorverarbeitung angewandt auf Kombinatorische Graphprobleme	de
dc.type.version	publishedVersion	en
tub.identifier.opus3	3878	-
tub.identifier.opus4	3838	-
tub.affiliation	Fak. 4 Elektrotechnik und Informatik » Inst. Softwaretechnik und Theoretische Informatik	de
Appears in Collections:	Technische Universität Berlin » Publications

Files in This Item:

weller_mathias.pdf
Format: Adobe PDF | Size: 6.64 MB
Download Show Preview

Show simple item record

Item Export Bar