SCHEDULE: NOV 10-16, 2012
When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.
A Multithreaded Algorithm for Network Alignment via Approximate Matching
SESSION: Graph Algorithms
EVENT TYPE: Papers
TIME: 4:30PM - 5:00PM
SESSION CHAIR: Esmond G. Ng
AUTHOR(S):Arif Khan, David Gleich, Mahantesh Halappanavar, Alex Pothen
Network alignment is an optimization problem to find the best one-to-one map between the vertices of a pair of graphs that overlaps in as many edges as possible. It is a relaxation of the graph isomorphism problem and is closely related to the subgraph isomorphism problem. The best current approaches are entirely heuristic and iterative in nature. They generate real-valued heuristic weights that must be rounded to find integer solutions. This rounding requires solving a bipartite maximum weight matching problem at each iteration in order to avoid missing high quality solutions. We investigate substituting a parallel, half-approximation for maximum weight matching instead of an exact computation. Our experiments show that the resulting difference in solution quality is negligible. We demonstrate almost a 20-fold speedup using 40 threads on an 8 processor Intel Xeon E7-8870 system and now solve real-world problems in 36 seconds instead of 10 minutes.
Esmond G. Ng (Chair) - Lawrence Berkeley National Laboratory
Arif Khan - Purdue University
David Gleich - Purdue University
Mahantesh Halappanavar - Pacific Northwest National Laboratory
Alex Pothen - Purdue University