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.
On the difficulty of finding walks of length k / S. Basagni, D. Bruschi, F. Ravasio. - In: RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS. - ISSN 0988-3754. - 31:5(1997), pp. 429-435.
On the difficulty of finding walks of length k
D. BruschiPrimo
;
1997
Abstract
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.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
ITA_1997__31_5_429_0.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
713.39 kB
Formato
Adobe PDF
|
713.39 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
