Searching paths of constant bandwidth

DSpace Repositorium (Manakin basiert)

Searching paths of constant bandwidth

Borchert, Bernd; Reinhardt, Klaus
Dateien:
Thumbnail
114. KB
PDF
Zitierfähiger Link (URI): http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-14494
http://hdl.handle.net/10900/48673
Dokumentart: Verschiedenartige Texte
Erscheinungsdatum: 2004
Originalveröffentlichung: WSI ; 2004 ; 10
Sprache: Englisch
Fakultät: 7 Mathematisch-Naturwissenschaftliche Fakultät
Fachbereich: Sonstige - Informations- und Kognitionswissenschaften
DDC-Klassifikation: 004 - Informatik
Schlagworte: Pfad <Mathematik> , Pfadalgorithmus , Komplexitätsklasse NP
Lizenz: http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=de http://tobias-lib.uni-tuebingen.de/doku/lic_ubt-nopod.php?la=en
Zur Langanzeige

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.

Das Dokument erscheint in: