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

共 50 条

[1] NO POLYNOMIAL BOUND FOR THE PERIOD OF THE PARALLEL CHIP FIRING GAME ON GRAPHS
KIWI, MA
NDOUNDAM, R
TCHUENTE, M
GOLES, E
THEORETICAL COMPUTER SCIENCE, 1994, 136 (02) : 527 - 532
[2] KERNELS IN DIRECTED-GRAPHS - A POISON GAME
DUCHET, P
MEYNIEL, H
DISCRETE MATHEMATICS, 1993, 115 (1-3) : 273 - 276
[3] VANISHING OF HOCHSCHILD COHOMOLOGIES AND DIRECTED-GRAPHS WITH POLYNOMIAL WEIGHTS
ZENG, Q
JOURNAL OF ALGEBRA, 1993, 154 (02) : 387 - 405
[4] A LOWER BOUND FOR THE STEINER TREE PROBLEM IN DIRECTED-GRAPHS
LIU, WG
NETWORKS, 1990, 20 (06) : 765 - 778
[5] A LOWER BOUND FOR THE SHORTEST HAMILTONIAN PATH IN DIRECTED-GRAPHS
MACULAN, N
SALLES, JJC
OR SPEKTRUM, 1991, 13 (02) : 99 - 102
[6] DIRECTED TRIANGLES IN DIRECTED-GRAPHS
DEGRAAF, M
SCHRIJVER, A
SEYMOUR, PD
DISCRETE MATHEMATICS, 1992, 110 (1-3) : 279 - 282
[7] ON GRACEFUL DIRECTED-GRAPHS
BLOOM, GS
HSU, DF
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1985, 6 (03): : 519 - 536
[8] HOMOGENEOUS DIRECTED-GRAPHS
CHERLIN, GL
JOURNAL OF SYMBOLIC LOGIC, 1987, 52 (01) : 296 - 296
[9] Chip-firing games on directed graphs
Bjoerner, Anders
Lovas, Laszlo
Journal of Algebraic Combinatorics, 1992, 1 (04)
[10] DECOMPOSITION OF DIRECTED-GRAPHS
CUNNINGHAM, WH
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1982, 3 (02): : 214 - 228

← 1 2 3 4 5 →