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

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

We propose a novel linear time algorithm which, given any directed weighted graphs <i>a</i> and <i>b</i> with vertex degrees 1 or 2, constructs a sequence of operations transforming <i>a</i> into <i>b</i>. The total cost of operations in this sequence...

Full description

Bibliographic Details
Main Authors: Konstantin Gorbunov, Vassily Lyubetsky
Format: Article
Language:English
Published: MDPI AG 2020-11-01
Series:Mathematics
Subjects:
discrete optimization
exact algorithm
additively exact algorithm
graph transformation
graph of degree 2
chain-cycle graph
Online Access:https://www.mdpi.com/2227-7390/8/11/2001

Internet

https://www.mdpi.com/2227-7390/8/11/2001

Similar Items