We characterize the computational complexity of the following combinatorial problem: Given a directed graph G = (V, E) endowed with a length function w : E ⇀ N, a pair of nodes s and t in V and an integer k ≥ 0, does G contain a walk π from s to t of length exactly k? We show that the problem is NP-complete when G is a directed graph, an undirected graph, or a directed acyclic graph. The problem becomes NL-complete when w is a unary function.
|Titolo:||On the difficulty of finding walks of length k|
BRUSCHI, DANILO MAURO (Primo)
|Parole Chiave:||Combinatorial problems; Computational complexity; Information Systems|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
|Data di pubblicazione:||1997|
|Appare nelle tipologie:||01 - Articolo su periodico|