Feedback Arc Set Problem and NP-Hardness of Minimum Recurrent Configuration Problem of Chip-Firing Game on Directed Graphs
| Author | dc.contributor.author | Perrot, Kévin | |
| Author | dc.contributor.author | Van Pham, Trung | |
| Admission date | dc.date.accessioned | 2015-08-19T16:04:36Z | |
| Available date | dc.date.available | 2015-08-19T16:04:36Z | |
| Publication date | dc.date.issued | 2015 | |
| Cita de ítem | dc.identifier.citation | Annals of Combinatorics 19 (2015) 373–396 | en_US |
| Identifier | dc.identifier.issn | 0218-0006 | |
| Identifier | dc.identifier.other | DOI: 10.1007/s00026-015-0266-9 | |
| Identifier | dc.identifier.uri | https://repositorio.uchile.cl/handle/2250/132926 | |
| General note | dc.description | Artículo de publicación ISI | en_US |
| Abstract | dc.description.abstract | 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 general directed graphs. A computational problem that arises naturally from this model is to find the minimum number of chips of a recurrent configuration, which we call the minimum recurrent configuration (MINREC) problem. We point out a close relationship between MINREC and the minimum feedback arc set (MINFAS) problem on Eulerian directed graphs, and prove that both problems are NP-hard. | en_US |
| Patrocinador | dc.description.sponsorship | Vietnam Institute for Advanced Study in Mathematics (VIASM), Vietnamese National Foundation for Science and Technology Development (NAFOSTED), Fondecyt , Nucleo Milenio Informacion y Coordinacion en Redes (ACGO) | en_US |
| Lenguage | dc.language.iso | en | en_US |
| Publisher | dc.publisher | Springer | en_US |
| Type of license | dc.rights | Atribución-NoComercial-SinDerivadas 3.0 Chile | * |
| Link to License | dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | * |
| Keywords | dc.subject | Sandpile model | en_US |
| Keywords | dc.subject | Complexity | en_US |
| Keywords | dc.subject | Feedback arc set | en_US |
| Keywords | dc.subject | Eulerian digraph | en_US |
| Keywords | dc.subject | Fecurrent configuration | en_US |
| Keywords | dc.subject | Critical configuration | en_US |
| Keywords | dc.subject | Chip-firing game | en_US |
| Título | dc.title | Feedback Arc Set Problem and NP-Hardness of Minimum Recurrent Configuration Problem of Chip-Firing Game on Directed Graphs | en_US |
| Document type | dc.type | Artículo de revista |
Files in this item
This item appears in the following Collection(s)
-
Artículos de revistas
Artículos de revistas
Except where otherwise noted, this item's license is described as Atribución-NoComercial-SinDerivadas 3.0 Chile