Variations of a Pebble Game on Graphs.

Abstract

Two variations are examined of a one-person pebble game played on directed graphs, which has been studied as a model of register allocation. The black-white pebble game of Cook and Sethi is shown to require as many pebbles in the worst case as the normal pebble game, to within a constant factor. For another version of the pebble game, the problem of deciding whether a given number of pebbles is sufficient for a given graph is shown to be complete in polynomial space.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Sep 01, 1978
Accession Number
ADA060794

Entities

People

  • John R. Gilbert
  • Robert Tarjan

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Automata
  • Clocks
  • Computations
  • Computer Science
  • Computers
  • Construction
  • Intervals
  • Language
  • Machines
  • Military Research
  • Parallel Computing
  • Polynomials
  • Simulations
  • Time Intervals
  • Trees (Data Structures)
  • Universities

Readers

  • Business Analytics
  • Game Theory.
  • Operations Research

Technology Areas

  • Space