[cs-talks] Upcoming CS Seminars: PhD Defense (Fri)
fgreen1 at bu.edu
Tue Jan 12 13:43:16 EST 2016
A Theory of Network Typings and its Optimization Problems
Saber Mirzaei, BU
Friday, January 15, 2016 at 11am in MCS 148
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 connected graph G = (V,E), one possible definition 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 and problems of graph embedding studied by other researchers (such as Linear Arrangement, Routing Tree Embedding, and Tree Layout). We present known results regarding these previously
studied problems, as well as our own results regarding Graph Reassembling.
(d) We conclude with a short overview of some open problems, to be studied and investigated in order to improve the original work of flow-network typing theory, as a basic framework for a compositional approach to the design and analysis of flow-network algorithms.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the cs-talks