Linear Time Additively Exact Algorithm for Transformation of Chain-Cycle Graphs for Arbitrary Costs of Deletions and Insertions

Konstantin Gorbunov and Vassily Lyubetsky
Additional contact information
Konstantin Gorbunov: Institute for Information Transmission Problems of the Russian Academy of Sciences, Bolshoi Karetnyi, 19, Moscow 127994, Russia
Vassily Lyubetsky: Institute for Information Transmission Problems of the Russian Academy of Sciences, Bolshoi Karetnyi, 19, Moscow 127994, Russia

Mathematics, 2020, vol. 8, issue 11, 1-30

Abstract: We propose a novel linear time algorithm which, given any directed weighted graphs a and b with vertex degrees 1 or 2, constructs a sequence of operations transforming a into b . The total cost of operations in this sequence is minimal among all possible ones or differs from the minimum by an additive constant that depends only on operation costs but not on the graphs themselves; this difference is small as compared to the operation costs and is explicitly computed. We assume that the double cut and join operations have identical costs, and costs of the deletion and insertion operations are arbitrary strictly positive rational numbers.

Keywords: discrete optimization; exact algorithm; additively exact algorithm; graph transformation; graph of degree 2; chain-cycle graph; operation cost; minimization of total cost (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/11/2001/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/11/2001/ (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:8:y:2020:i:11:p:2001-:d:442596

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