Feedback Arc Set Problem and NP-Hardness of Minimum Recurrent Configuration Problem of Chip-Firing Game on Directed Graphs

dc.creatorPerrot, Kévin
dc.creatorVan Pham, Trung
dc.date.accessioned2015-08-19T16:04:36Z
dc.date.available2015-08-19T16:04:36Z
dc.date.created2015-08-19T16:04:36Z
dc.date.issued2015
dc.identifierAnnals of Combinatorics 19 (2015) 373–396
dc.identifier0218-0006
dc.identifierDOI: 10.1007/s00026-015-0266-9
dc.identifierhttps://repositorio.uchile.cl/handle/2250/132926
dc.description.abstractIn 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.
dc.languageen
dc.publisherSpringer
dc.rightshttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
dc.rightsAtribución-NoComercial-SinDerivadas 3.0 Chile
dc.subjectSandpile model
dc.subjectComplexity
dc.subjectFeedback arc set
dc.subjectEulerian digraph
dc.subjectFecurrent configuration
dc.subjectCritical configuration
dc.subjectChip-firing game
dc.titleFeedback Arc Set Problem and NP-Hardness of Minimum Recurrent Configuration Problem of Chip-Firing Game on Directed Graphs
dc.typeArtículo de revista


Este ítem pertenece a la siguiente institución