YoVDO

New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs

Offered By: Association for Computing Machinery (ACM) via YouTube

Tags

Algorithms Courses Graph Algorithms Courses

Course Description

Overview

Explore cutting-edge algorithms and complexity analysis for incremental single-source shortest paths (SSSP) in directed graphs in this 23-minute conference talk presented at an Association for Computing Machinery (ACM) event. Delve into the problem definition, examine the ES Tree and Lazy ES Tree data structures, and gain insights into new algorithmic approaches. Understand the challenges and hardness associated with solving SSSP problems in dynamic directed graphs, and discover how these findings contribute to the field of graph algorithms and theoretical computer science.

Syllabus

Introduction
Problem Definition
ES Tree
Lazy ES Tree
Algorithm
Summary


Taught by

Association for Computing Machinery (ACM)

Related Courses

Information Theory
The Chinese University of Hong Kong via Coursera Intro to Computer Science
University of Virginia via Udacity Analytic Combinatorics, Part I
Princeton University via Coursera Algorithms, Part I
Princeton University via Coursera Divide and Conquer, Sorting and Searching, and Randomized Algorithms
Stanford University via Coursera