Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 2 of 2
Full-Text Articles in Physical Sciences and Mathematics
The Complexity Of Pebbling In Diameter Two Graphs, Timothy Lewis, Daniel Simpson, Sam Taggart
The Complexity Of Pebbling In Diameter Two Graphs, Timothy Lewis, Daniel Simpson, Sam Taggart
11th Annual Celebration of Undergraduate Research and Creative Performance (2012)
Given a simple, connected graph, a pebbling configuration is a function from its vertex set to the nonnegative integers. A pebbling move between adjacent vertices removes two pebbles from one vertex and adds one pebble to the other. A vertex r is said to be reachable under a configuration if there exists a sequence of pebbling moves that places one pebble on r. A configuration is solvable if every vertex is reachable. We prove tight bounds on the number of vertices with two and three pebbles that can exist in an unsolvable configuration on a diameter two graph in terms …
Graph Games: Human Computing Games To Solve Graph Problems, Hsiang Lin, Russell Zinn
Graph Games: Human Computing Games To Solve Graph Problems, Hsiang Lin, Russell Zinn
11th Annual Celebration of Undergraduate Research and Creative Performance (2012)
Graph Games is a collection of games with the purpose of gathering data from player solutions for solving graph-related problems that are difficult for computers to solve efficiently. The data will be used to solve instances of and improve algorithms for various problems on graphs. We made several important improvements to the Graph Games software. Now every move made by the player, including the timing between moves, is stored. The replay system was also improved so that player solutions can be replayed move by move, in real time, or sped up or slowed down. So that players can more easily …