This Friday (11/20) the Computer Science Graduate Student Organization (CSGSO) will have Student Speaker Series at 3pm in the CS Library. All faculty and students are welcome to attend! Light refreshment will be provided.
Speaker: David Einstein
Topic: K-SPR routing
In ad-hoc networks routing can be done by designating some of the nodes as gateway nodes. The goal of the k-SPR (k- Shortest Path Routing) problem is to find a set of nodes in a graph such that for any two nodes in the graph there exists a shortest path between the two nodes having a gateway node every k or fewer hops. We show that the the k-SPR problem is NP-Complete on chordal and bipartite graphs, and that it is NP complete for specific values of k on Planar and unit disk graphs.
Joint work with Mike Reick of Drake University.
Biography:
David Einstein received a BS in applied math from UMass Lowell in 1989. He is currently underemployed by Structured Decisions Corporation where he has worked as an operations researcher for the past 15 years. He has published a handful of papers on combinatorics, most recently "On Sara's Dove Bar Habit", a combinatorial analysis of domestic harmony, in the November 2009 American Mathematical Monthly.
P.S.
Thank you,
Beibei (Betty) Yang
CSGSO President
No comments:
Post a Comment