Simple Paths and Cycles Avoiding Forbidden Paths

DOI10.1007/978-3-319-73117-9_20MaRDI QIDQ5127183zbMATH OpenOpenAlexFDO

Authors Benjamin Momège

Publication date 21 October 2020

Published in SOFSEM 2018: Theory and Practice of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-73117-9_20

zbMATH Keywords

exact algorithmsexponential-time algorithmsforbidden pathsgraph algorithmsHamiltonian cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Simple paths with exact and forbidden lengths
• Finding paths in graphs avoiding forbidden transitions
• Avoidable paths in graphs
• Shortest paths avoiding forbidden subpaths
• Shortest Paths Avoiding Forbidden Subpaths
• scientific article; zbMATH DE number 970792
• On the complexity of paths avoiding forbidden pairs
• Forbidden paths and cycles in ordered graphs and matrices
• Simple path covers in graphs
• scientific article; zbMATH DE number 3557820

Cited in

(6)

• Finding paths in graphs avoiding forbidden transitions
• Avoidable paths in graphs
• Finding paths in grids with forbidden transitions
• An exact algorithm to check the existence of (elementary) paths and a generalisation of the cut problem in graphs with forbidden transitions
• Non-permitted journeys and Hamiltonian paths
• On the complexity of paths avoiding forbidden pairs

This page was built for publication: Simple Paths and Cycles Avoiding Forbidden Paths

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