[cs-talks] Upcoming CS Seminars: PhD Oral Exam (Thurs)

cs, Group cs at bu.edu
Wed Sep 9 09:14:42 EDT 2015


Ph.D Oral Exam
A Theory of Network Typings and its Optimization Problems
Saber Mirzaei, BU
Tuesday, September 10, 2015 at 1:00 pm in MCS B08

Abstract: A theory of network typings gives rise to problems of polyhedral analysis and different forms of graph decomposition. Some of these problems are new and still to be examined, others can be shown reducible or equivalent to problems already resolved or partially resolved by other researchers. We introduce some of the new notions, relate them to earlier notions in the literature, and focus on one problem -- which we call the "graph reassembling" problem.  Given an abstraction of a flow network in the form of a simple connected graph G = (V,E), a definition (not the only possible one) of the reassembling of G is specified in two steps: (1) We cut every edge of G into two halves to obtain a collection of n = |V| one-node components, and (2) we splice the two halves of all the edges, one edge at a time, in some order that minimizes the complexity of constructing a typing for G, starting from the typings of its one-node components. One optimization is to minimize the *maximum* edge-boundary degree of any component encountered during the reassembling of G. Another optimization is to minimize the sum of all edge-boundary degrees encountered during the reassembling of G. In this talk: (a) We start with a brief presentation of previous work on the elements of a typing theory for flow networks and the concepts of sound, complete and principal typings. In this part we present some approaches in order to find a principal typing for flow networks. (b) In the second part of the talk, we focus on the new problem of graph reassembling arising in the effort to introduce an efficient algorithm for finding principal typings for flow networks. (c) We follow our talk by showing the relation between some variations of graph reassembling problem and some well-known graph layout problems, i.e. Minimum Cut-Width (CutWidth) and Minimum Linear Arrangement (MinArr) problems. Subsequent to the presentation of some more important and previously known results on these two problems, we introduce our result on MinArr of Halin graphs. (d) We conclude with a short overview of some open problems, to be studied and investigated in order to improve the original work of the flow networks typing theory, as the base framework for a compositional approach for the flow networks algorithms. Examining committee: Steve Homer, Assaf Kfoury, Lorenzo Orecchia



-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/cs-talks/attachments/20150909/71411c66/attachment.html>


More information about the cs-talks mailing list