Speaker: Mustafa Kemal Tural, Middle East Technical University
Date & Time: March 17, 2023, Friday 13:30
Place: EA-409
Title: Minimum Weighted 1-Maximal Total Nearly Perfect Set Problem
Abstract: Given an undirected graph G=(V,E), a subset of the nodes S is called a total nearly perfect set (TNPS) if every node in G has at most element of S in its open neighborhood. A TNPS S of size k is said to be 1-maximal if it is not a proper subset of any other TNPS of size k+1. In a paper written by Hedetniemi and Haynes [Unsolved Algorithmic Problems on Trees, AKCE International Journal of Graphs and Combinatorics, 3:1,
1-37 (2006)], the authors ask for an algorithm to compute the minimum size of a 1-maximal TNPS in trees. We study the more general problem of finding a 1-maximal TNPS of minimum weight in a node-weighted graph and obtain some structural and algorithmic results for general graphs with additional results specifically for trees.
This is joint work Melodi Cebesoy and Şakir Buğra Kollar.
Bio: Mustafa Kemal Tural received his B.S. degrees in Industrial Engineering and Mathematics from Boğazici University in 2004 and his Ph.D. degree in Operations Research from the University of North Carolina at Chapel Hill, NC, US in 2009. Following his Ph.D., with the support of the Institute for Mathematics and its Applications (IMA), he spent one year as an NSF industrial postdoc at Telcordia Technologies and one year as an NSF postdoctoral researcher in the Industrial Engineering and Operations Research Department at Columbia University.
He joined the Department of Industrial Engineering at the Middle East Technical University in November 2011, where he is currently an assistant professor. His main research interests are in theory and applications of (integer) linear and nonlinear optimization and graph theory.