05 29, 2023
Let T=(V,A) be a tournament with a nonnegative integral weight w(e) on each arc e. A subset F of arcs is called a feedback arc set (FAS) if T\F contains no cycles (directed). A collection F of FASs (with repetition allowed) is called an FAS packing if each arc e is used at most w(e) times by the members of F. The purpose of this paper is to give a characterization of all tournaments T=(V,A) with the property that, for every nonnegative integral weight function w defined on A, the minimum total weight of a cycle is equal to the maximum size of an FAS packing.
Publication:
Mathematics of Operations Research, Published Online: 23 Feb, 2023, https://doi.org/10.1287/moor.2023.1352
Author:
Xujin Chen
Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China
Email: xchen@amss.ac.cn
Guoli Ding
Mathematics Department, Louisiana State University, Baton Rouge, LA 70803, USA
Wenan Zang
Department of Mathematics, The University of Hong Kong, Hong Kong, China
Qiulan Zhao
Department of Mathematics, Nanjing University, Nanjing 210093, China
Copyright@2008,All Rights Reserved, Academy of Mathematics and Systems Science,CAS
Tel:86-10-82541777 Fax: 86-10-82541972 E-mail: contact@amss.ac.cn
京ICP备05002806-1号 京公网安备110402500020号