On the difficulty of finding walks of length k

DOI10.1051/ITA/1997310504291MaRDI QIDQ4385673zbMATH OpenOpenAlexFDO

Authors Stefano Basagni, Danilo Bruschi, F. Ravasio

Publication date 3 August 1998

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/92570

zbMATH Keywords

computational complexitydirected graph

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On a problem of walks
• scientific article; zbMATH DE number 2104724
• scientific article; zbMATH DE number 3876620
• scientific article; zbMATH DE number 68918
• scientific article; zbMATH DE number 2121203
• On the greedy walk problem
• The length of self-avoiding walks on the complete graph
• scientific article; zbMATH DE number 6269059
• Asymptotic results regarding the number of walks in a graph
• On the number of walks in a triangular domain

Cites work

• Color-coding
• Exact arborescences, matchings and cycles
• Graphs, dynamic programming, and finite games
• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Random parallel algorithms for finding exact branchings, perfect matchings, and cycles
• Random pseudo-polynomial algorithms for exact matroid problems
• The complexity of restricted spanning tree problems

Cited in

(3)

• scientific article; zbMATH DE number 776078 (Why is no real title available?)
• Methods for determining cycles of a specific length in undirected graphs with edge weights
• Methods for finding paths of a prescribed length in weighted graphs

This page was built for publication: On the difficulty of finding walks of length k

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4385673)