Conflicting chip firing games on graphs and on trees
Chip Firing Games on (directed) graph are widely used in theoretical computer science and many other sciences. In this model, chips are fired from one vertex to all of its neighbors at the same time. The purpose of our paper is to study an extended version of this model, the Conflicting Chip Firing...
Saved in:
Main Authors: | , , |
---|---|
Format: | Article |
Language: | English |
Published: |
VNU
2014
|
Subjects: | |
Online Access: | http://repository.vnu.edu.vn/handle/11126/4686 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Vietnam National University, Hanoi |
Language: | English |
id |
oai:112.137.131.14:11126-4686 |
---|---|
record_format |
dspace |
spelling |
oai:112.137.131.14:11126-46862018-08-28T03:51:07Z Conflicting chip firing games on graphs and on trees Pham, Tra An Phan, Thi Ha Duong Tran, Thi Thu Huong Chip Firing Game Conflicting game, Convergence Discrete dynamical system Evolution rule Fxed point Tree Chip Firing Games on (directed) graph are widely used in theoretical computer science and many other sciences. In this model, chips are fired from one vertex to all of its neighbors at the same time. The purpose of our paper is to study an extended version of this model, the Conflicting Chip Firing Game, by considering that chips can be fired from one vertex to one of its neighbors at each time. Our main results are obtained when the support graph of this game is a rooted tree. In this case, we give the characterization of its reachable configurations and of its fixed points. Moreover we show the local lattice structure of its configuration space. 2014-03-20T02:27:06Z 2015-08-26T09:27:41Z 2014-03-20T02:27:06Z 2015-08-26T09:27:41Z 2008 Article Pham, Tra An, Phan, Thi Ha Duong, Tran, Thi Thu Huong. (2008). Conflicting chip firing games on graphs and on trees, VNU Journal of Science, Nature Sciences and Technology 24(2008), p. 103-109 http://repository.vnu.edu.vn/handle/11126/4686 en VNU Journal of Science, Nature Sciences and Technology application/pdf VNU |
institution |
Vietnam National University, Hanoi |
building |
VNU Library & Information Center |
country |
Vietnam |
collection |
VNU Digital Repository |
language |
English |
topic |
Chip Firing Game Conflicting game, Convergence Discrete dynamical system Evolution rule Fxed point Tree |
spellingShingle |
Chip Firing Game Conflicting game, Convergence Discrete dynamical system Evolution rule Fxed point Tree Pham, Tra An Phan, Thi Ha Duong Tran, Thi Thu Huong Conflicting chip firing games on graphs and on trees |
description |
Chip Firing Games on (directed) graph are widely used in theoretical computer science
and many other sciences. In this model, chips are fired from one vertex to all of its neighbors at the same time. The purpose of our paper is to study an extended version of this model, the Conflicting Chip Firing Game, by considering that chips can be fired from one vertex to one of its neighbors at
each time. Our main results are obtained when the support graph of this game is a rooted tree. In this case, we give the characterization of its reachable configurations and of its fixed points.
Moreover we show the local lattice structure of its configuration space. |
format |
Article |
author |
Pham, Tra An Phan, Thi Ha Duong Tran, Thi Thu Huong |
author_facet |
Pham, Tra An Phan, Thi Ha Duong Tran, Thi Thu Huong |
author_sort |
Pham, Tra An |
title |
Conflicting chip firing games on graphs and on trees |
title_short |
Conflicting chip firing games on graphs and on trees |
title_full |
Conflicting chip firing games on graphs and on trees |
title_fullStr |
Conflicting chip firing games on graphs and on trees |
title_full_unstemmed |
Conflicting chip firing games on graphs and on trees |
title_sort |
conflicting chip firing games on graphs and on trees |
publisher |
VNU |
publishDate |
2014 |
url |
http://repository.vnu.edu.vn/handle/11126/4686 |
_version_ |
1680963701462532096 |