Searching paths of constant bandwidth

DSpace Repository


Dokumentart: Report
Date: 2004
Source: WSI ; 2004 ; 10
Language: English
Faculty: 7 Mathematisch-Naturwissenschaftliche Fakultät
Department: Sonstige - Informations- und Kognitionswissenschaften
DDC Classifikation: 004 - Data processing and computer science
Keywords: Pfad <Mathematik> , Pfadalgorithmus , Komplexitätsklasse NP
Show full item record


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.

This item appears in the following Collection(s)