Multiplicatively Exact Algorithms for Transformation and Reconstruction of Directed Path-Cycle Graphs with Repeated Edges

Konstantin Gorbunov and Vassily Lyubetsky
Additional contact information
Konstantin Gorbunov: Institute for Information Transmission Problems, Russian Academy of Sciences, 127051 Moscow, Russia
Vassily Lyubetsky: Institute for Information Transmission Problems, Russian Academy of Sciences, 127051 Moscow, Russia

Mathematics, 2021, vol. 9, issue 20, 1-19

Abstract: For any weighted directed path-cycle graphs, a and b (referred to as structures ), and any equal costs of operations (intermergings and duplication), we obtain an algorithm which, by successively applying these operations to a , outputs b if the first structure contains no paralogs (i.e., edges with a repeated name) and the second has no more than two paralogs for each edge. In finding the shortest sequence of operations to be applied to pass from a to b , the algorithm has a multiplicative error of at most 13/9 + ?, where ? is any strictly positive number, and its runtime is of the order of n O ( ? ? 2.6 ) , where n is the size of the input pair of graphs. In the case of no paralogs, equal sets of names in the structures, and equal operation costs, we have considered the following conditions on the transformation of a into b : all structures in them are from one cycle; all structures are from one path; all structures are from paths. For each of the conditions, we have obtained an exact (i.e., zero-error) quadratic time algorithm for finding the shortest transformation of a into b . For another list of operations (join and cut of a vertex, and deletion and insertion of an edge) over structures and for arbitrary costs of these operations, we have obtained an algorithm for the extension of structures specified at the leaves of a tree onto its interior vertices. The algorithm is exact if the tree is a star—in this case, structures in the leaves may even have unequal sets of names or paralogs. The runtime of the algorithm is of the order of n ? + n 2 log( n ), where n is the number of names in the leaves, and ? is an easily computable characteristic of the structures in the leaves. In the general case, a cubic time algorithm finds a locally minimal solution.

Keywords: discrete optimization; minimization of total cost; operation cost; path-cycle graph; exact algorithm; multiplicatively exact algorithm; graph transformation; graph reconstruction (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/20/2576/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/20/2576/ (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:9:y:2021:i:20:p:2576-:d:655793

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 ().