News & Events
Department Events & Announcements

Events

  • Feb
    19

    Theory Seminar - Katina Russell "Efficient Construction of Directed Hopsets and Parallel Approximate Shortest Paths"

    Department of Computer Science

    2:00 PM

    EVENT DETAILS

    Abstract

    The approximate single-source shortest-path problem is as follows: given a graph with non-negative edge weights and a designated source vertex s, return estimates of the distances from s to each other vertex such that the estimate falls between the true distance and (1 + ε) times the distance. Our result is the first nearly work-efficient parallel algorithm with sublinear span (also called depth) for the approximate shortest-path problem on directed graphs. Specifically, for constant ε and polynomially-bounded edge weights, our algorithm has work O ̃(m) and span n1/2+o(1). Several algorithms were previously known for the case of undirected graphs, but none of the techniques seem to translate to the directed setting. The main technical contribution is the first nearly linear-work algorithm for constructing hopsets on directed graphs. A (β,ε)-hopset is a set of weighted edges (sometimes called shortcuts) which, when added to the graph, admit β-hop paths with weight no more than (1+ε) times the true shortest-path distances. There is a simple sequential algorithm that takes as input a directed graph and produces a linear-cardinality hopset with β = O( n), but its running time is quite high—specifically O ̃(m√n). Our algorithm is the first more efficient algorithm that produces a directed hopset with similar characteristics. Specifically, our sequential algorithm runs in O ̃(m) time and constructs a hopset with O ̃(n) edges and β = n1/2+o(1). A parallel version of the algorithm has work O ̃(m) and span n1/2+o(1).

    Biography

    Katina Russell is a Ph.D. candidate in the Department of Computer Science at Georgetown University. She is advised by professor Jeremy T. Fineman. Before Georgetown, Katina received her masters degree in computer science from Tufts University, and her bachelors degree in math from Boston College. Her current research focuses on graph algorithms, parallel algorithms, and data structures.

    more

    TIME Friday, February 19, 2021 at 2:00 PM - 3:00 PM

    ADD TO CALENDAR

    CONTACT Pamela Villalovoz    pmv@northwestern.edu EMAIL

    CALENDAR Department of Computer Science

  • Sep
    8

    Welcome & Breakfast for New McCormick PhD Students

    McCormick School of Engineering and Applied Science

    9:00 AM LR2 & Tech East Plaza, Technological Institute

    EVENT DETAILS

    TIME Monday, September 8, 2025 at 9:00 AM - 10:00 AM

    LOCATION LR2 & Tech East Plaza, Technological Institute    map it

    ADD TO CALENDAR

    CONTACT Andi Joppie    andi.joppie@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • Sep
    12

    New Undergraduate Fall 2025 Registration

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Friday, September 12, 2025

    ADD TO CALENDAR

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar

  • Sep
    15

    Welcome & Luncheon for New Full-time Graduate Students

    McCormick School of Engineering and Applied Science

    11:00 AM Ryan Auditorium & Tech East Plaza, Technological Institute

    EVENT DETAILS

    TIME Monday, September 15, 2025 at 11:00 AM - 12:30 PM

    LOCATION Ryan Auditorium & Tech East Plaza, Technological Institute    map it

    ADD TO CALENDAR

    CONTACT Andi Joppie    andi.joppie@northwestern.edu EMAIL

    CALENDAR McCormick School of Engineering and Applied Science

  • Sep
    16

    Fall Classes Begin. Change of Registration (Drop/Add) Late registration for returning students begins

    University Academic Calendar

    All Day

    EVENT DETAILS

    TIME Tuesday, September 16, 2025

    ADD TO CALENDAR

    CONTACT Office of the Registrar    nu-registrar@northwestern.edu EMAIL

    CALENDAR University Academic Calendar