NO POLYNOMIAL BOUND FOR THE CHIP FIRING GAME ON DIRECTED-GRAPHS

被引：7

作者：

ERIKSSON, K

机构：

来源：

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY | 1991年 / 112卷 / 04期

关键词：

GRAPH; GAME; CHIP FIRING;

D O I：

10.2307/2048674

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Tardos has proved a polynomial bound on the length of a convergent chip firing game on an undirected graph. This paper demonstrates a game with exponential growth on a directed graph.

引用

页码：1203 / 1205

页数：3

共 11 条

[1] Chip-firing and rotor-routing on directed graphs
Holroyd, Alexander E.
Levine, Lionel
Meszaros, Karola
Peres, Yuval
Propp, James
Wilson, David B.
IN AND OUT OF EQUILIBRIUM 2, 2008, 60 : 331 - +
[2] Chip firing and the tutte polynomial
Criel Merino López
Annals of Combinatorics, 1997, 1 (1) : 253 - 259
[3] Source reversal and chip firing on graphs
Goles, E
Prisner, E
THEORETICAL COMPUTER SCIENCE, 2000, 233 (1-2) : 287 - 295
[4] A greedy chip-firing game
Li, Rupert
Propp, James
RANDOM STRUCTURES & ALGORITHMS, 2023, 62 (03) : 645 - 666
[5] Chip-firing games on mutating graphs
Eriksson, K
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1996, 9 (01) : 118 - 128
[6] A Variation on Chip-Firing: the diffusion game
Duffy, C.
Lidbetter, T. F.
Messinger, M. E.
Nowakowski, R. J.
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2018, 20 (01)
[7] MOTORS AND IMPOSSIBLE FIRING PATTERNS IN THE PARALLEL CHIP-FIRING GAME
Jiang, Tian-Yi
Scully, Ziv
Zhang, Yan X.
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (01) : 615 - 630
[8] Chip-firing games, potential theory on graphs, and spanning trees
Baker, Matthew
Shokrieh, Farbod
JOURNAL OF COMBINATORIAL THEORY SERIES A, 2013, 120 (01) : 164 - 182
[9] UCD: Upper confidence bound for rooted directed acyclic graphs
Saffidine, Abdallah
Cazenave, Tristan
Mehat, Jean
KNOWLEDGE-BASED SYSTEMS, 2012, 34 : 26 - 33
[10] A constant bound for the periods of parallel chip-firing games with many chips
Paul Myer Kominers
Scott Duke Kominers
Archiv der Mathematik, 2010, 95 : 9 - 13

← 1 2 →