| Zitierfähiger Link: |
Bitte nutzen Sie diese URL, um auf das Dokument zu verlinken oder es zu zitieren:
http://nbn-resolving.de/urn:nbn:de:bsz:21-opus-14494 |
| URL: |
http://tobias-lib.uni-tuebingen.de/volltexte/2004/1449/ |
| Originalveröffentlichung: |
WSI ; 2004-10 |
| Fachgebiet/Einrichtung: |
Bereich 17 Fakultät für Informations- und Kognitionswissenschaften (ohne Institutszuordnung) |
| Dokumentart: |
Report (Bericht) |
| Sprache: |
Englisch |
| Erstellungsjahr: |
2004 |
| Publikationsdatum: |
15.11.2004 |
| Kurze Inhaltszusammenfassung auf Englisch |
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. |
| Kontrollierte Schlagwörter (Deutsch): |
Pfad <Mathematik> , Pfadalgorithmus , Komplexitätsklasse NP |
| DDC-Sachgruppe: |
Informatik |
| Lizenz: |
Veröffentlichungsvertrag (Version 1998)
|
PDF 114kB
