Optimal pebble motion on a tree

DOI10.1006/INCO.2000.3005MaRDI QIDQ1854411zbMATH OpenOpenAlexFDO

Authors V. Auletta, P. Persiano

Publication date 14 January 2003

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/inco.2000.3005

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• A linear-time algorithm for the feasibility of pebble motion on trees
• O(1)-approximations for maximum movement problems
• A linear time algorithm for the feasibility of pebble motion on trees
• Multi-color pebble motion on graphs
• The optimal pebbling number of the complete \(m\)-ary tree

Cites work

• A linear time algorithm for the feasibility of pebble motion on trees
• Graph puzzles, homotopy, and the alternating group

Cited in

(11)

• A linear-time algorithm for the feasibility of pebble motion on trees
• Multi-color pebble motion on graphs
• On reachability in graphs with obstacles
• Efficient algorithms for the 2-gathering problem
• Efficient algorithms for the 2-gathering problem
• Motions of a connected subgraph representing a swarm of robots inside a graph of work stations
• A linear time algorithm for the feasibility of pebble motion on trees
• On Complete S-Reachable Graphs
• Token Swapping on Trees
• Multi-agent pathfinding on strongly connected digraphs: feasibility and solution algorithms
• Feasibility of motion planning on acyclic and strongly connected directed graphs

This page was built for publication: Optimal pebble motion on a tree

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