[CS seminar on Feb 18] "A Branch-and-cut algorithm for minimum..."
  • FENS
  • [CS seminar on Feb 18] "A Branch-and-cut algorithm for minimum..."

You are here

Title: A Branch-and-cut algorithm for minimum triangulation of graphs
Speaker: Birol Yüceoğlu
Date: February 18, 2015, 13:40-14:30 
Place: FENS G035
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.