Multi-Color Pebble Motion on Graphs | Zendy

Gilad Goraly | Zendy; Refael Hassin | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Multi-Color Pebble Motion on Graphs

Author(s) -

Gilad Goraly,

Refael Hassin

Publication year - 2009

Publication title -

algorithmica

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.647

H-Index - 78

eISSN - 1432-0541

pISSN - 0178-4617

DOI - 10.1007/s00453-009-9290-7

Subject(s) - pebble , vertex (graph theory) , combinatorics , theory of computation , graph , computer science , mathematics , algorithm , geomorphology , geology

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 (6) 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research