2020/03/20 by Sudiksha Khanduja, Aayushi Srivastava, Khanduja, Sudiksha +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms
paper · pdf · doi:10.48550/arxiv.2003.13786
openalex publication_date 2020/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a scheme for generating a weakly chordal graph from a randomly generated input graph, G = (V, E). We reduce G to a chordal graph H by adding fill-edges, using the minimum vertex degree heuristic. Since H is necessarily a weakly chordal graph, we use an algorithm for deleting edges from a weakly chordal graph that preserves the weak chordality property of H. The edges that are candidates for deletion are the fill-edges that were inserted into G. In order to delete a maximal number of fill-edges, we maintain these in a queue. A fill-edge is removed from the front of the queue, which we then try to delete from H. If this violates the weak chordality property of H, we reinsert this edge at the back of the queue. This loop continues till no more fill-edges can be removed from H. Operationally, we implement this by defining a deletion round as one in which the edge at the back of the queue is at the front.We stop when the size of the queue does not change over two successive deletion rounds and output H.