6 papers
Generating Weakly Chordal Graphs from Arbitrary Graphs
Sudiksha Khanduja, Aayushi Srivastava, Md. Zamilur Rahman +1
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 minimu…
Semi-dynamic Algorithms for Strongly Chordal Graphs
Md. Zamilur Rahman, Asish Mukhopadhyay
There is an extensive literature on dynamic algorithms for a large number of graph theoretic problems, particularly for all varieties of shortest path problems. Germane to this pap…
Strongly Chordal Graph Generation using Intersection Graph Characterisation
Md. Zamilur Rahman, Asish Mukhopadhyay
Strongly chordal graphs are a subclass of chordal graphs. Farber also established a number of different characterisations for this class of graphs. These include an intersection gr…
A separator-based method for generating weakly chordal graphs
Md. Zamilur Rahman, Asish Mukhopadhyay, Yash P. Aneja
We propose a scheme for generating a weakly chordal graph on n vertices with m edges. In this method, we first construct a tree and then generate an orthogonal layout (which is a w…
An Algorithm for Generating Strongly Chordal Graphs
Md. Zamilur Rahman, Asish Mukhopadhyay, Yash P. Aneja
Strongly chordal graphs are a subclass of chordal graphs. The interest in this subclass stems from the fact that many problems which are NP-complete for chordal graphs are solvable…
A greedy approximation algorithm for the minimum (2,2)-connected dominating set problem
Yash P. Aneja, Asish Mukhopadhyay, Md. Zamilur Rahman
Using a connected dominating set (CDS) to serve as the virtual backbone of a wireless sensor network (WSN) is an effective way to save energy and reduce the impact of broadcasting…