Searching paths of constant bandwidth

DSpace Repository

Show simple item record

dc.contributor.author Borchert, Bernd de_DE
dc.contributor.author Reinhardt, Klaus de_DE
dc.date.accessioned 2004-11-15 de_DE
dc.date.accessioned 2014-03-18T10:13:31Z
dc.date.available 2004-11-15 de_DE
dc.date.available 2014-03-18T10:13:31Z
dc.date.issued 2004 de_DE
dc.identifier.other 11514076X de_DE
dc.identifier.uri http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-14494 de_DE
dc.identifier.uri http://hdl.handle.net/10900/48673
dc.description.abstract As a generalization of paths, the notion of paths of bandwidth w is introduced. We show that, for a given constant w >= 1, the corresponding search problem for such a path of length k in a given graph is NP-complete and fixed-parameter tractable in the parameter k, like this is known for the special case w=1, the LONGEST PATH problem. We state the FPT algorithm in terms of a guess and check protocol which uses witnesses of size polynomial in the parameter. 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 Pfad <Mathematik> , Pfadalgorithmus , Komplexitätsklasse NP de_DE
dc.subject.ddc 004 de_DE
dc.title Searching paths of constant bandwidth en
dc.type Report (Bericht) 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 1449 de_DE
utue.opus.portal wsi de_DE
utue.opus.portalzaehlung 2004.10000 de_DE
utue.publikation.source WSI ; 2004 ; 10 de_DE
utue.publikation.reihenname WSI-Reports - Schriftenreihe des Wilhelm-Schickard-Instituts für Informatik de_DE
utue.publikation.zsausgabe 2004, 10
utue.publikation.erstkatid 2919855-0

Dateien:

This item appears in the following Collection(s)

Show simple item record