ICS Theory Group

Fall 2016: Theory Seminar
DBH, Room 1300, 1:00pm

Dec 2, 2016:

Pebble Game Algorithms and Sparse Graphs

Authors: Audrey Lee, Ileana Streinu

Speaker: Elham Havvaei

A graph is (k,l)-sparse if the number of induced edges in any nonempty subgraph with n' vertices is at most kn'-l. Testing (k,l)-sparsity can be performed in polynomial time when k and l are integers and 0 ≤ l < 2k via a family of mathematical games called the (k,l)-pebble games. Pebble game is played by moving "pebbles" or "markers" on a directed graph according to certain rules.