Searching Paths of Constant Bandwidth

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Conference object , Article , Report 01 Jan 2006 Germany Publisher:Springer Berlin Heidelberg

Authors: Borchert, Bernd; Reinhardt, Klaus;

doi: 10.1007/11611257_16

handle: 10900/48673

Searching Paths of Constant Bandwidth

- Summary
- Subjects
- Metrics

Abstract

As a generalization of paths, the notion of paths of bandwidth w is introduced. We show that, for 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 (FPT) 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.

Country

Germany

Related Organizations

University of Tübingen
Germany

Keywords

Pfad <Mathematik> , Pfadalgorithmus , Komplexitätsklasse NP, Pfadalgorithmus, Pfad, Komplexitätsklasse NP, 004

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average

Found an issue? Give us feedback

0

Average

Green