Aspects of Preprocessing Applied to Combinatorial Graph Problems

Weller, Mathias

Aspects of Preprocessing Applied to Combinatorial Graph Problems

dc.contributor.advisor	Niedermeier, Rolf	en
dc.contributor.author	Weller, Mathias	en
dc.contributor.grantor	Technische Universität Berlin, Fakultät IV - Elektrotechnik und Informatik	en
dc.date.accepted	2012-12-05
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.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.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.language	English	en
dc.language.iso	en	en
dc.publisher.name	Universitätsverlag der TU Berlin	en
dc.publisher.place	Berlin	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.title.translated	Aspekte der Vorverarbeitung angewandt auf Kombinatorische Graphprobleme	de
dc.type	Doctoral Thesis	en
dc.type.version	publishedVersion	en
tub.accessrights.dnb	free	*
tub.affiliation	Fak. 4 Elektrotechnik und Informatik>Inst. Softwaretechnik und Theoretische Informatik	de
tub.affiliation.faculty	Fak. 4 Elektrotechnik und Informatik	de
tub.affiliation.institute	Inst. Softwaretechnik und Theoretische Informatik	de
tub.identifier.opus3	3878
tub.identifier.opus4	3838
tub.publisher.universityorinstitution	Universitätsverlag der TU Berlin	en

Files

Original bundle

Now showing 1 - 1 of 1

Name:: weller_mathias.pdf
Size:: 6.48 MB
Format:: Adobe Portable Document Format
Description:

Download

Collections

Publications