• Chỉ mục bởi
  • Năm xuất bản

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

Perrot K. Departamento de Ingeniería Matemática, Universidad de Chile, CMM (UMI 2807 - CNRS), Blanco Encalda, Santiago 2120, Chile|
Van Pham T. Aix Marseille Université, CNRS, LIF UMR 7279, Marseille, 13288, France|

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



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.

Xem chi tiết