GAINESVILLE, FL:  Dr. Vladimir Boginski, Assistant Professor of Industrial and Systems Engineering will give a seminar on Thursday, September 27, in FLG 0245, at 4:05 p.m.

Title:  Diameter-based Clique Relaxations in Networks

We consider the problems of analysis and design of network clusters with bounded diameter, which can be viewed as a “relaxation” of the well-known definition of a clique. In many situations, one of the key network robustness requirements is the connectivity between each pair of nodes through a path that is short enough, that is, restricting the number of intermediate nodes and links in a path. A k-club, which by definition is a subgraph with a diameter of at most k, is a structure that addresses this requirement (assuming that k is small enough with respect to the size of the original network). We consider the problem of identifying the largest k-club in a given graph and describe new solution techniques for this problem. Moreover, we introduce a related concept referred to as an R-robust k-club, which extends the standard definition of a k-club by explicitly requiring at least R distinct paths of length at most k between each pair of nodes within a cluster. R-robust k-clubs are shown to possess “strong attack tolerance” characteristics. The problems of R-robust k-club design and augmentation in undirected and directed graphs are also considered.

Bio:

Vladimir Boginski serves as Assistant Professor of Industrial and Systems Engineering at the University of Florida at the Research and Engineering Education Facility (REEF) in Shalimar, Florida.  He is also Director of the Defense-Oriented Operations Research (DOOR) Lab. His research has been supported by DoD, DoE, and NSF. He is also a recent recipient of the DTRA Young Investigator Award.