[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..."

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.

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.

© Copyright 2017 by Sabanci University.