Feedback arc set problem and NP-hardness of minimum recurrent configuration problem of Chip-firing game on directed graphs

K Perrot, T Van Pham - Annals of Combinatorics, 2015 - Springer
In this paper we present further studies of recurrent configurations of chip-firing games on
Eulerian directed graphs (simple digraphs), a class on the way from undirected graphs to …

Chip-firing game and partial Tutte polynomial for Eulerian digraphs

K Perrot, T Van Pham - arXiv preprint arXiv:1306.0294, 2013 - arxiv.org
The Chip-firing game is a discrete dynamical system played on a graph, in which chips
move along edges according to a simple local rule. Properties of the underlying graph are of …

[PDF][PDF] A chip-firing variation and a Markov chain with uniform stationary distribution.

D Perkins, PM Kayll - Australas. J Comb., 2017 - researchgate.net
We continue our study of burn-off chip-firing games on graphs initiated in [Discrete Math.
Theor. Comput. Sci. 15 (2013), no. 1, 121–132]. Here we introduce randomness by choosing …

[HTML][HTML] Elimination schemes and lattices

ME Messinger, RJ Nowakowski, P Prałat - Discrete Mathematics, 2014 - Elsevier
Perfect vertex elimination schemes are part of the characterizations for several classes of
graphs, including chordal and cop-win. Partial elimination schemes reduce a graph to an …

Les piles de sable Kadanoff

K Perrot - 2013 - theses.hal.science
Les modèles de pile de sable sont une sous-classe d'automates cellulaires. Bak et al. les
ont introduit en 1987 comme une illustration de la notion intuitive d'auto-organisation …

[PDF][PDF] A survey on the stability of (Extended) Linear Sand Pile Model

PTH Duong - math.ac.vn
We give a survey of our works on the natural extensions of the wellknown Sand Pile Model.
These extensions consist of adding outside grains on random columns, allowing sand …

Linear time algorithm for computing the rank of divisors on cactus graphs

PTH Duong - arXiv preprint arXiv:1601.03038, 2016 - arxiv.org
arXiv:1601.03038v1 [math.CO] 12 Jan 2016 Linear time algorithm for computing the rank of
divisors on cactus graphs Page 1 arXiv:1601.03038v1 [math.CO] 12 Jan 2016 Linear time …

[PDF][PDF] Properties of stable configurations of the Chip-firing game and extended models

T Van Pham - 2015 - math.ac.vn
The Chip Firing Game (CFG) is a discrete dynamical model which was first defined by A.
Björner, L. Lovász and W. Shor while studying the 'balancing game'[6, 7, 42]. The model has …

[引用][C] Np-hardness of minimum feedback arc set problem on eulerian digraphs and minimum recurrent configuration problem of chip-firing game

K Perrot, VT Pham - CoRR, abs/1303.3708, 2013

[引用][C] NP hardness of minimum feedback arc set problem on Eulerian digraphs and minimum recurrent configuration problem of Chipfiring game Bạn đang xem bản …

LVB Cáo, KN Mềm, M Slide, KDT Thị, KTQ Lý…