| Title | : | Realizability of Graph Specifications: Characterizations and Algorithms |
| Speaker | : | David Peleg (Weizmann Institute of Science, Israel) |
| Details | : | Tue, Feb 19, 2019 3:00 PM, @ Turing Hall |
| Abstract | : | This is cross-listed as a department seminar. The study of graphs and networks often involves studying various parameters of the graph vertices, capturing different aspects of the graph structure, such as the vertex degrees or the distances between the vertices. Given an n-vertex graph G and a parameter of interest f, one may associate with G a vector F(G) = (f1,...,fn) giving the value of f for each vertex. This vector can be thought of as the f-profile of the graph. This paper concerns the dual problem, where given an n-entry f-specification vector F = (f1,...,fn), we need to decide whether it is possible to find a graph G realizing this specification, namely, whose f-profile F(G) conforms to F. The paper introduces the notion of graph realiziations and illustrates a number of example problems related to finding graph realiziations for given specifications. (Based on joint work with Amotz Bar-Noy, Keerti Choudhary and Dror Rawitz) Speaker bio: Prof. David Peleg is the Norman D. Cohen Professorial Chair of Computer Science at the Weizmann Institute of Science, Rehovot, Israel. His research interests span algorithms (specifically graph algorithms and approximation algorithms), distributed computing, communication networks and mobile robot systems. His pioneering contributions have been recognized by the Edsger W. Dijkstra Prize in Distributed Computing, awarded jointly by ACM and EATCS in 2008, Prize for Innovation in Distributed Computing awarded by the Colloquium on Structural Information and Communication Complexity (SIROCCO) in 2001 among others. He is a fellow of the Association of Computing Machinery (ACM) since 2017. |