Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Computer Sciences
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 …
Graph Games: A Human Computing Game Framework, Ryan Alfuth, Matt Jara, Jeff Largent, Dan Simpson
Graph Games: A Human Computing Game Framework, Ryan Alfuth, Matt Jara, Jeff Largent, Dan Simpson
10th Annual Celebration of Undergraduate Research and Creative Performance (2011)
Graph Games is a suite of online casual games that make use of human computation to help solve several NP-complete graph problems. These problems are very difficult for computers to solve efficiently because they rapidly become computationally infeasible as their size increases. However, humans possess intelligent decision-making abilities that computers do not, so they can solve these problems more resourcefully than computers.
Graph Games seeks to harness these abilities to increase the body of knowledge about solving NP-complete problem by presenting problems in the form of puzzle-like games. Graph Games currently consists of three families of games, each being comprised …