LIÊN KẾT WEBSITE
Feedback Arc Set Problem and NP-Hardness of Minimum Recurrent Configuration Problem of Chip-Firing Game on Directed Graphs
Annals of Combinatorics Số 2, năm 2015 (Tập 19, trang 373-396)
ISSN: 2180006
ISSN: 2180006
DOI: 10.1007/s00026-015-0266-9
Tài liệu thuộc danh mục: ISI, Scopus
Article
English
Tóm tắt tiếng anh
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. © 2015, Springer Basel.