Multi-color pebble motion on graphs

Multi-color pebble motion on graphs

0.00 Avg rating0 Votes
Article ID: iaor20105811
Volume: 58
Issue: 3
Start Page Number: 610
End Page Number: 636
Publication Date: Nov 2010
Journal: Algorithmica
Authors: ,
Keywords: computational analysis
Abstract:

We consider a graph with n vertices, and p<n pebbles of m colors. A pebble move consists of transferring a pebble from its current host vertex to an adjacent unoccupied vertex. The problem is to move the pebbles to a given new color arrangement. We study the feasibility version of the problem– does a given instance have a solution? We use an algorithm of Auletta et al. (1999) for the problem where each pebble has a distinct color to give a linear time algorithm for the feasibility decision problem on a general graph.

Reviews

Required fields are marked *. Your email address will not be published.