Imposing connectivity in network design problems

Abstract

Imposing connectivity arises in multiple real-world problems -- telecommunication network design, social network analysis, reserve network design, and redistricting to name a few. In network optimization, connectivity constraints are usually imposed in three spaces: (i) vertex space, (ii) edge space, and (iii) vertex-and-edge space. In this dissertation, we focus on imposing connectivity in the vertex and edge spaces. We study connectivity constraints in telecommunication and redistricting networks (both in the vertex space), revisit the spanning tree polytope in planar graphs (in the edge space), and conduct a polyhedral study of k connected components (in the vertex space).