• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

An Improved Upper Bound for the Pebbling Threshold of the n-path

Wierman, Adam, Salzman, Julia, Jablonski, Michael, Godbole, Anant P. 28 January 2004 (has links)
Given a configuration of t indistinguishable pebbles on the n vertices of a graph G, we say that a vertex v can be reached if a pebble can be placed on it in a finite number of "moves". G is said to be pebbleable if all its vertices can be thus reached. Now given the n-path Pn how large (resp. small) must t be so as to be able to pebble the path almost surely (resp. almost never)? It was known that the threshold th(Pn) for pebbling the path satisfies n2clgn≤th(Pn)≤n22lgn, where lg=log2 and c<1/2 is arbitrary. We improve the upper bound for the threshold function to th(Pn)≤n2dlgn, where d>1 is arbitrary.

Page generated in 0.5117 seconds