New Applied Problems in the Theory of Acyclic Digraphs

Gurami Tsitsiashvili and Victor Bulgakov
Additional contact information
Gurami Tsitsiashvili: Institute for Applied Mathematics, Far Eastern Branch of Russian Academy of Sciences, 690041 Vladivostok, Russia
Victor Bulgakov: Federal Scientific Center of the East Asia Biodiversity, Far Eastern Branch of Russian Academy of Sciences, 690022 Vladivostok, Russia

Mathematics, 2021, vol. 10, issue 1, 1-10

Abstract: The following two optimization problems on acyclic digraph analysis are solved. The first of them consists of determining the minimum (in terms of volume) set of arcs, the removal of which from an acyclic digraph breaks all paths passing through a subset of its vertices. The second problem is to determine the smallest set of arcs, the introduction of which into an acyclic digraph turns it into a strongly connected one. The first problem was solved by reduction to the problem of the maximum flow and the minimum section. The second challenge was solved by calculating the minimum number of input arcs and determining the smallest set of input arcs in terms of the minimum arc coverage of an acyclic digraph. The solution of these problems extends to an arbitrary digraph by isolating the components of cyclic equivalence in it and the arcs between them.

Keywords: acyclic digraph; maximal flow; minimal cut; minimal arc cover; bipartite digraph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/1/45/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/1/45/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2021:i:1:p:45-:d:709882

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().