Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Algorithmic Paradigms for Dynamic Graph Problems

Description

This lecture introduces algorithmic paradigms for dynamic graph problems, focusing on real-world computation challenges like summarizing large networks and tracking communities in social networks. The instructor discusses dynamic algorithms, dynamic problems, and balanced binary search trees. The lecture explores the concept of dynamic connectivity and the study of dynamic graphs by theorists. It also covers the use of expander decomposition and local clustering in dynamic settings, breaking barriers in k-vertex connectivity problems. The lecture concludes with a discussion on the future of dynamic algorithms and the collaboration with various researchers in the field.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (32)

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Connectivity (graph theory)

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network. In an undirected graph G, two vertices u and v are called connected if G contains a path from u to v.

Social network

A social network is a social structure made up of a set of social actors (such as individuals or organizations), sets of dyadic ties, and other social interactions between actors. The social network perspective provides a set of methods for analyzing the structure of whole social entities as well as a variety of theories explaining the patterns observed in these structures. The study of these structures uses social network analysis to identify local and global patterns, locate influential entities, and examine network dynamics.

Shortest path problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment.

Related lectures (49)

Graph Algorithms II: Traversal and Paths

Explores graph traversal methods, spanning trees, and shortest paths using BFS and DFS.

Graph Algorithms: Ford-Fulkerson and Strongly Connected Components

Discusses the Ford-Fulkerson method and strongly connected components in graph algorithms.

Algorithms: Union Find and Minimum Spanning Trees

Discusses Union-Find data structures and Minimum Spanning Trees, covering algorithms and their applications in network design and optimization.

Graphs: Properties and Representations

Covers graph properties, representations, and traversal algorithms using BFS and DFS.

Fixed Points in Graph Theory