CS-IE-OPIM Joint Seminar 4 March 2015 at 13.40 at FENS G035

A Branch-and-cut algorithm for minimum triangulation of graphs

By Dr. Birol Yüceoğlu

Abstract: In a chordal (triangulated) graph the biggest cycle without a chord (an edge joining non-adjacent vertices of a cycle) has size 3. Given an undirected simple graph G, a triangulation (fill-in, chordalization) of G corresponds to adding edges to G such that the new (hyper)graph is chordal. The minimum triangulation problem is to find the smallest number of additional edges required to make the graph chordal. The problem has applications in Gaussian elimination of sparse matrices, database management, tensor-based recommender systems, and Bayesian networks. In order to solve the problem, we propose a solution approach that is based on perfect elimination orderings of graphs. After presenting an integer linear programming formulation based on perfect elimination orderings, we introduce several classes of valid inequalities in order to strengthen the formulation. We, then, present our computational study based on DIMACS graph instances for the graph coloring problem.

Bio: Dr. Birol Yüceoğlu received his BS. and MS. degrees from the Department of Manufacturing Systems/Industrial Engineering of Sabancı University in 2007 and 2009, respectively. He did his Ph.D. on Operations Research at the Department of Quantitative Economics at Maastricht University, the Netherlands. His research interests include integer programming, polyhedral theory, graph theory, and algorithms.