Finding paths in grids with forbidden transitions

DOI10.1007/978-3-662-53174-7_12MaRDI QIDQ2827809zbMATH OpenOpenAlexFDO

Authors Mamadou Moustapha Kanté, Benjamin Momège, Nicolas Nisse, Fatima Zahra Moataz

Publication date 21 October 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-53174-7_12

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

Recommendations

• An exact algorithm to check the existence of (elementary) paths and a generalisation of the cut problem in graphs with forbidden transitions
• Finding paths in graphs avoiding forbidden transitions
• Simple Paths and Cycles Avoiding Forbidden Paths
• Shortest path-planning in road nets with forbidden routes
• A note on shortest path problems with forbidden paths

Cites work

• Algorithms – ESA 2005
• Complexity of trails, paths and circuits in arc-colored digraphs
• Dynamic programming and planarity: improved tree-decomposition based algorithms
• Finding paths in graphs avoiding forbidden transitions
• Finding paths in grids with forbidden transitions
• Graph minors. II. Algorithmic aspects of tree-width
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• Labeling algorithm for the shortest path problem with turn prohibitions with application to large-scale road networks
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• Shortest path problem with forbidden paths: the elementary version
• Shortest paths avoiding forbidden subpaths
• The shortest path problem with forbidden paths
• Universality considerations in VLSI circuits

Cited in

(16)

• On minimum connecting transition sets in graphs
• Separating codes and traffic monitoring
• Domination problems with no conflicts
• Finding paths in graphs avoiding forbidden transitions
• On the complexity of independent dominating set with obligations in graphs
• Analyzing the reachability problem in choice networks
• Codon optimization by 0-1 linear programming
• The complexity of routing problems in forbidden-transition graphs and edge-colored 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
• scientific article; zbMATH DE number 1445371 (Why is no real title available?)
• scientific article; zbMATH DE number 7765417 (Why is no real title available?)
• Reachability in choice networks
• Introduction to routing problems with mandatory transitions
• On the routing problems in graphs with ordered forbidden transitions
• An efficient branch-and-bound algorithm for the one-to-many shortest path problem with additional disjunctive conflict constraints

This page was built for publication: Finding paths in grids with forbidden transitions

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