Empower - The Campaign for Northeastern University


Thesis Proposal: Analyzing graphical rendezvous in restricted domains

Title: Analyzing graphical rendezvous in restricted domainsSpeaker: Matthew Dippel, Northeastern University, PhD studentLocation: Northeastern University, 440 Huntington Avenue, West Village H, Room #164, Boston, Massachusetts 02115AbstractWe initiate a study of the problem of "asymmetric graphical rendezvous", a generalization of the more commonly analyzed symmetric graphical rendezvous. In this problem, agents restricted to different subgraphs of a larger connected graph need to meet at some node in their intersection, without knowledge of each others restricted subgraphs. We consider two particular cases: where these restricted subgraphs can be any subgraph of the containing graph, and when these subgraphs are limited to single edges of the graph. In the single edge case, we derive several hardness results and applicable algorithms. In the unrestricted subgraph case, we show matching upper and lower bounds for randomized rendezvous algorithms on general graphs. Motivated by this, we propose an analytical tool to derive near asymptotically optimal rendezvous algorithms for a variety of graph classes. We apply it to get rendezvous algorithms for several classes of graphs. We propose future directions for extending this work, and present prior work which works on one of these directions on clique graphs, showing that even in the simplest case, new analytical tools needed to be derived to make progress.Committee Ravi Sundaram (Northeastern University, Advisor) Rajmohan Rajaraman (Northeastern University) Huy Le Nguyen (Northeastern University) Alexander Russell (University of Connecticut, External Member)

Wednesday, December 19, 2018 at 11:00am



Google Calendar iCal Outlook

Recent Activity