SHARP logo Hope College, Holland, Michigan
All About SHARP applicants

projects

program directors

 

 

All About Sharp
Project details

Algorithms for Graph Pebbling

Project Full Title:

Algorithms for Graph Pebbling

Project Mentor(s):

Cusack,Charles

Project Mentor(s) EMail:

cusack@hope.edu

Project Start Date:

5/31/2015

Project End Date:

7/29/2015

Project Description:

This interdisciplinary project will incorporate the disciplines of Computer Science and Mathematics. However the project is specifically housed within the Hope College Department of Computer Science.

This project will involve developing and testings algorithms for graph pebbling problems. A graph G = (V, E) is composed of a set of vertices, V, and a set of pairs of vertices, E, called edges. Two vertices of a graph are adjacent if they are connected by an edge. A pebbling configuration is a function C from vertices to non-negative integers, where C(v) is the number of pebbles on vertex v. For any vertex v such that C(v) is at least 2, a pebbling step consists of removing two pebbles from v and placing one pebble on a vertex adjacent to v. Thus, pebbles can be moved from one vertex to any adjacent vertex, but each time a pebble is moved, another pebble from that vertex is removed from the graph. A configuration is called r-solvable if there is a sequence of pebbling steps that places at least one pebble on a specified vertex r. We refer to the problem of determining whether or not a configuration is r-solvable as Reachable. A configuration is called solvable if it is r-solvable for every vertex in the graph—that is, if it is possible to place a pebble on any vertex of the graph using pebbling steps. This problem is referred to as Solvable.

There is no known efficient algorithm to solve either Reachable or Solvable. The goal of this project will be to create algorithms for these problem that are efficient for some classes of graphs. In particular, we will be interested in diameter-two graphs (graphs in which every pair of vertices is either connected by an edge or has a common adjacent neighbor).

Some background in programming, preferably Java, will be required. Preference will be given to candidates who have taken a course in algorithms, data structures, combinatorics, and/or graph theory.

External Link:

BACK

 

 

© 2007-2010 Hope College, Holland, Michigan, USA. All rights reserved.