On reachability in graphs with obstacles

DOI10.1142/S1793830915500597zbMath1351.68193MaRDI QIDQ2788738

Kalpesh Kapoor, Udit Agarwal

Publication date: 22 February 2016

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

zbMATH Keywords

graph algorithmsgames involving graphsgraph configurationobstacles on verticesreachability in graphs

Mathematics Subject Classification ID

Games involving graphs (91A43) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Feasibility of motion planning on acyclic and strongly connected directed graphs
• The \((n^ 2-1)\)-puzzle and related relocation problems
• A linear-time algorithm for the feasibility of pebble motion on trees
• SOKOBAN and other motion planning problems
• Searching and pebbling
• Graph puzzles, homotopy, and the alternating group
• Optimal pebble motion on a tree
• Modelling and solving English peg solitaire
• Finding the Shortest Move-Sequence in the Graph-Generalized 15-Puzzle Is NP-Hard
• Feasibility of Motion Planning on Directed Graphs
• Reducing Multiple Object Motion Planning to Graph Searching
• Reconfigurations in Graphs and Grids

This page was built for publication: On reachability in graphs with obstacles