Title :
A tight bound for black and white pebbles on the pyramid
Abstract :
Lengauer and Tarjan proved that the number of black and white pebbles needed to pebble the root of a tree is at least 1/2 the number of black pebbles needed to pebble the root. We extend this result to a larger class of acyclic directed graphs including pyramid graphs.
Keywords :
Application software; Computational modeling; Computer languages; Computer science; Laboratories; Optimizing compilers; Program processors;
Conference_Titel :
Foundations of Computer Science, 1983., 24th Annual Symposium on
Conference_Location :
Tucson, AZ, USA
Print_ISBN :
0-8186-0508-1
DOI :
10.1109/SFCS.1983.3
