The problem of determining the minimal weight feedback edge set in an oriented weighted graph when the graph represents a network flow is the focus of this paper. The proposed solution is especially interesting since it can be directly applied in solving the linearization of genome sequence graphs (GSG) which represent a set of individual haploid reference genomes as paths in a single graph and can find frequent human genetic variations, including translocations, inversions, deletions, and insertions. The linearization is essential for the efficiency of storing and traversal as well as visualization of the graph. In this paper properties of the flow function are used to obtain some features of the optimal ordering of nodes when the weight of the feedback edge set is minimal.
Two-terminal flow network ,Feedback arcs, Linearization , Flow graph
© Association for Information and Communication Technologies www.ict-act.org Developed by tdelev