Date of Award

7-7-2020

Publication Type

Master Thesis

Degree Name

M.S.

Department

Computer Science

Keywords

Bipartite graph, Chordal Graph, Nearly Chordal Graph, Triangulation

Supervisor

Asish Mukhopadhyay

Rights

info:eu-repo/semantics/openAccess

Abstract

Graph Generation aids in analysis of graphs and their properties while insinuating conjectures via counterexamples and even generating test instances for other algorithms. In certain cases, a list of graphs will deliver numerical information for enumerative problems devoid of theoretical solutions, or even supply a source from which specimen graphs may be adopted. Any given graph can be embedded in a chordal graph by adding edges, and the resulting chordal graph is called a triangulation of the input graph i.e., contains no induced chordless cycle on four or more vertices. Triangulation is classified into Minimal and Minimum, where both the approach seems to minimize the number of edges added. A comparison has been drawn amongst LB-Triangulation, Lex-M and Minimum Degree Vertex (MDV) approaches to achieve triangulation with as few edges as possible along with respective run times. While LB-Triang and Lex-M algorithms provide minimal triangulation, MDV is an approximation for minimum triangulation. Determining the minimum number of edges that must be added to a bipartite graph to make it a chain graph is NP-complete. We exploit this reduction to propose a heuristic for obtaining a chain graph from a bipartite graph via a chordal graph using MDV. Dirac's method of generating chordal graphs by the union is modified with the help of MDV. Nearly Chordal Graphs are generated using a novel heuristic from complete graphs. Recognition algorithm for nearly chordal graphs is introduced and the relationship between weakly chordal, nearly chordal and chordal graphs is established.

Download

Share

COinS