File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1287/moor.2023.1352
- Scopus: eid_2-s2.0-85191611303
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Article: Packing Feedback Arc Sets in Tournaments Exactly
Title | Packing Feedback Arc Sets in Tournaments Exactly |
---|---|
Authors | |
Keywords | breadth-first search cycle feedback arc set minimax relation tournament |
Issue Date | 1-Feb-2024 |
Publisher | Institute for Operations Research and Management Sciences |
Citation | Mathematics of Operations Research, 2024, v. 49, n. 1, p. 151-170 How to Cite? |
Abstract | 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. |
Persistent Identifier | http://hdl.handle.net/10722/348279 |
ISSN | 2023 Impact Factor: 1.4 2023 SCImago Journal Rankings: 1.215 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Chen, Xujin | - |
dc.contributor.author | Ding, Guoli | - |
dc.contributor.author | Zang, Wenan | - |
dc.contributor.author | Zhao, Qiulan | - |
dc.date.accessioned | 2024-10-08T00:31:23Z | - |
dc.date.available | 2024-10-08T00:31:23Z | - |
dc.date.issued | 2024-02-01 | - |
dc.identifier.citation | Mathematics of Operations Research, 2024, v. 49, n. 1, p. 151-170 | - |
dc.identifier.issn | 0364-765X | - |
dc.identifier.uri | http://hdl.handle.net/10722/348279 | - |
dc.description.abstract | 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. | - |
dc.language | eng | - |
dc.publisher | Institute for Operations Research and Management Sciences | - |
dc.relation.ispartof | Mathematics of Operations Research | - |
dc.subject | breadth-first search | - |
dc.subject | cycle | - |
dc.subject | feedback arc set | - |
dc.subject | minimax relation | - |
dc.subject | tournament | - |
dc.title | Packing Feedback Arc Sets in Tournaments Exactly | - |
dc.type | Article | - |
dc.identifier.doi | 10.1287/moor.2023.1352 | - |
dc.identifier.scopus | eid_2-s2.0-85191611303 | - |
dc.identifier.volume | 49 | - |
dc.identifier.issue | 1 | - |
dc.identifier.spage | 151 | - |
dc.identifier.epage | 170 | - |
dc.identifier.eissn | 1526-5471 | - |
dc.identifier.issnl | 0364-765X | - |