A linear-time algorithm for the feasibility of pebble motion on trees

DOI10.1007/PL00009259zbMath0921.68090OpenAlexW2083721544MaRDI QIDQ1283933

Pino Persiano, Angelo Monti, Vincenzo Auletta

Publication date: 30 March 1999

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/pl00009259

zbMATH Keywords

memory managementdeflection routingrobot motion planningpebble motion problem on trees

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Trees (05C05) Nonnumerical algorithms (68W05) Combinatorics in computer science (68R05)

Related Items (15)

Polynomial-time optimal liveness enforcement for guidepath-based transport systems ⋮ Token graphs ⋮ The connectivity of token graphs ⋮ Token Swapping on Trees ⋮ Reconfiguration of connected graph partitions ⋮ Colored pebble motion on graphs ⋮ On the 2-Token Graphs of Some Disjoint Union of Graphs ⋮ Multi-color pebble motion on graphs ⋮ Independence and matching numbers of some token graphs ⋮ On reachability in graphs with obstacles ⋮ Pebble exchange group of graphs ⋮ Efficient generation of performance bounds for a class of traffic scheduling problems ⋮ The edge-connectivity of token graphs ⋮ Introduction to reconfiguration ⋮ Pebble exchange on graphs

This page was built for publication: A linear-time algorithm for the feasibility of pebble motion on trees