Matches in DBpedia 2016-04 for { <http://dbpedia.org/resource/Pebble_game> ?p ?o }
Showing triples 1 to 44 of
44
with 100 triples per page.
- Pebble_game abstract "For the popular game, see Go (game).In mathematics and computer science, a pebble game is a type of mathematical game played by moving \"pebbles\" or \"markers\" on a directed graph. A variety of different pebble games exist. A general definition of pebbling is given below. Pebbling is a game that involves placing pebbles on the vertices of a directed acyclic graph G according to certain rules. A given step of the game consists of either placing a pebble on an empty vertex of G or removing a pebble from a previously pebbled vertex. A vertex may be pebbled only if all its predecessors have pebbles. The object of the game is to successively pebble each vertex of G (in any order) while minimizing the number of pebbles that are ever on the graph simultaneously. Running time: The trivial solution is to pebble an n-vertex graph in n steps using n pebbles. Hopcroft, Paul and Valiant showed that any vertex of an n-vertex graph can be pebbled with O(n/log n) pebbles where the constant depends on the maximum in-degree. This enabled them to prove that DTIME(f(n)) is contained in DSPACE(f(n)/log f(n)) for all time-constructible f. Lipton and Tarjan showed that any n-vertex planar acyclic directed graph with maximum in-degree k can be pebbled using O( √n + k log2 n) pebbles. They also proved that it is possible to obtain a substantial reduction in pebbles while preserving a polynomial bound on the number of pebbling steps with a theorem that any n-vertex planar acyclic directed graph with maximum in-degree k can be pebbled using O(n2/3 +k) pebbles in O(n5/3 ) time. Alon, Seymour and Thomas showed that any n-vertex acyclic directed graph with no kh -minor and with maximum in-degree k can be pebbled using O(h3/2 n1/2 +k log n) pebbles. An extension of this game, known as \"black-white pebbling\", was developed by Stephen Cook and Ravi Sethi in a 1976 paper. It also adds white pebbles, which may be placed at any vertex at will, but can only be removed if all the vertex's immediate descendant vertices are also pebbled. The goal remains to place a black pebble on the target vertex, but the pebbling of adjacent vertices may be done with pebbles of either color. Takumi Kasai et al. developed a game in which a pebble may be moved along an edge-arrow to an unoccupied vertex only if a second pebble is located at a third, control vertex; the goal is to move a pebble to a target vertex. This variation makes the pebble game into a generalization of games such as Chinese checkers and Halma. They determined the computational complexity of the one and two-player versions of this game, and special cases thereof. In the two-player version, the players take turns moving pebbles. There may also be constraints on which pebbles a player can move. Pebbling may be used to extend Ehrenfeucht–Fraïssé games.↑ ↑ ↑ ↑ ↑ ↑".
- Pebble_game wikiPageID "22531014".
- Pebble_game wikiPageLength "5821".
- Pebble_game wikiPageOutDegree "27".
- Pebble_game wikiPageRevisionID "673286933".
- Pebble_game wikiPageWikiLink Category:Combinatorial_game_theory.
- Pebble_game wikiPageWikiLink Category:Computational_complexity_theory.
- Pebble_game wikiPageWikiLink Chinese_checkers.
- Pebble_game wikiPageWikiLink Computational_complexity_theory.
- Pebble_game wikiPageWikiLink Computer_science.
- Pebble_game wikiPageWikiLink Constructible_function.
- Pebble_game wikiPageWikiLink DSPACE.
- Pebble_game wikiPageWikiLink DTIME.
- Pebble_game wikiPageWikiLink Directed_acyclic_graph.
- Pebble_game wikiPageWikiLink Directed_graph.
- Pebble_game wikiPageWikiLink Ehrenfeucht–Fraïssé_game.
- Pebble_game wikiPageWikiLink Go_(game).
- Pebble_game wikiPageWikiLink Graph_minor.
- Pebble_game wikiPageWikiLink Graph_pebbling.
- Pebble_game wikiPageWikiLink Halma.
- Pebble_game wikiPageWikiLink Jakob_Nordström.
- Pebble_game wikiPageWikiLink Logical_Methods_in_Computer_Science.
- Pebble_game wikiPageWikiLink Mathematical_game.
- Pebble_game wikiPageWikiLink Mathematics.
- Pebble_game wikiPageWikiLink Nick_Pippenger.
- Pebble_game wikiPageWikiLink Planar_graph.
- Pebble_game wikiPageWikiLink Ravi_Sethi.
- Pebble_game wikiPageWikiLink Springer_Science+Business_Media.
- Pebble_game wikiPageWikiLink Stephen_Cook.
- Pebble_game wikiPageWikiLink Thomas_J._Watson_Research_Center.
- Pebble_game wikiPageWikiLinkText "Pebble game".
- Pebble_game wikiPageWikiLinkText "pebble game".
- Pebble_game wikiPageUsesTemplate Template:Cite_book.
- Pebble_game wikiPageUsesTemplate Template:Reflist.
- Pebble_game subject Category:Combinatorial_game_theory.
- Pebble_game subject Category:Computational_complexity_theory.
- Pebble_game type Combinatoric.
- Pebble_game comment "For the popular game, see Go (game).In mathematics and computer science, a pebble game is a type of mathematical game played by moving \"pebbles\" or \"markers\" on a directed graph. A variety of different pebble games exist. A general definition of pebbling is given below. Pebbling is a game that involves placing pebbles on the vertices of a directed acyclic graph G according to certain rules.".
- Pebble_game label "Pebble game".
- Pebble_game sameAs Q7158529.
- Pebble_game sameAs m.05zp6gm.
- Pebble_game sameAs Q7158529.
- Pebble_game wasDerivedFrom Pebble_game?oldid=673286933.
- Pebble_game isPrimaryTopicOf Pebble_game.