Graph separators - a parameterized view

DSpace Repository

Show simple item record

dc.contributor Tübingen / Wilhelm-Schickard-Institut für Informatik de_DE
dc.contributor.author Alber, Jochen de_DE
dc.contributor.author Fernau, Henning de_DE
dc.contributor.author Niedermeier, Rolf de_DE
dc.date.accessioned 2004-04-21 de_DE
dc.date.accessioned 2014-03-18T10:12:36Z
dc.date.available 2004-04-21 de_DE
dc.date.available 2014-03-18T10:12:36Z
dc.date.issued 2001 de_DE
dc.identifier.other 111265800 de_DE
dc.identifier.uri http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-11962 de_DE
dc.identifier.uri http://hdl.handle.net/10900/48585
dc.description.abstract Graph separation is a well-known tool to make (hard) graph problems accessible to a divide and conquer approach. We show how to use graph separator theorems in combination with (linear) problem kernels in order to develop fixed parameter algorithms for many well-known NP-hard (planar) graph problems. We coin the key notion of glueable select&verify graph problems and derive from that a prospective way of easily check wether a planar graph problem will allow for a fixed parameter algorithm of running time. Besides we introduce the novel cocept of "problem cores" that might serve as an alternative to problem kernels for devising parameterized algorithms. One of the main contributions of the paper is to exactly compute the base c of the exponential term and its dependence on the various parameters specified by the employed separator theorem and the underlying graph problem. We discuss several strategies to improve on the involved constant c. Our findings also give rise to studying further refinements of the complexity class FTP of fixed parameters tractable problems. en
dc.language.iso en de_DE
dc.publisher Universität Tübingen de_DE
dc.rights ubt-nopod de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=de de_DE
dc.rights.uri http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=en en
dc.subject.classification Tübingen / Wilhelm-Schickard-Institut für Informatik de_DE
dc.subject.ddc 004 de_DE
dc.subject.other planar graph problems , fixed parameter tractability , parameterized complexity , graph separators , divide and conquer algorithms en
dc.title Graph separators - a parameterized view en
dc.type Report de_DE
dc.date.updated 2012-10-11 de_DE
utue.publikation.fachbereich Sonstige - Informations- und Kognitionswissenschaften de_DE
utue.publikation.fakultaet 7 Mathematisch-Naturwissenschaftliche Fakultät de_DE
dcterms.DCMIType Text de_DE
utue.publikation.typ report de_DE
utue.opus.id 1196 de_DE
utue.opus.portal wsi de_DE
utue.opus.portalzaehlung 2001.08000 de_DE
utue.publikation.source WSI ; 2001 ; 8 de_DE
utue.publikation.reihenname WSI-Reports - Schriftenreihe des Wilhelm-Schickard-Instituts für Informatik de_DE
utue.publikation.zsausgabe 2001, 8
utue.publikation.erstkatid 2919855-0

Dateien:

This item appears in the following Collection(s)

Show simple item record