Graph Algorithms (WT 2023/24) - tele-TASKhttps://www.tele-task.de/series/1483/Graphs play a central role in the world of algorithms. For example, navigation devices use an algorithm to compute shortest paths on a graph to answer a route query. Many planning and assignment problems can also be easily modeled as problems on graphs. In principle, it is true that a great many problems can be thought of as graph problems, so designing efficient algorithms for such problems is an important subfield of theoretical computer science.
In this lecture we will enter the world of graph algorithms. On the one hand, we will learn about important algorithmic problem classes on graphs and efficient algorithms to solve them. Among other things, we will look at finding shortest paths, flows, cuts, separators, and matchings in graphs. Algorithms for these problems have a wide variety of applications, making them an important and useful tool for any algorithmicist. On the other hand, we will also study how constraints on the graphs at hand affect the complexity of the problems and their algorithmic solution. For example, many algorithmic problems are more efficiently solvable on trees and planar graphs (i.e., graphs that can be embedded in the plane without intersection) than on general graphs. We will also explore some properties of graphs that we can exploit specifically for designing efficient algorithms. For example, trees and planar graphs have small separators (sets of nodes whose removal causes the graphs to decompose into multiple context components), which helps design efficient divide & conquer algorithms.
The goal of the lecture is the development and training of a structured approach to algorithmic problems on graphs. In doing so, we will jointly develop efficient graph algorithms with appropriate data structures, prove their correctness, and analyze their resource requirements (runtime and memory). In addition, the lecture will highlight special graph classes and other important concepts in graph theory and their impact on the world of algorithms.High quality e-learning content created with tele-TASK - more than video! Powered by Hasso Plattner Institute (HPI)Dr. George SkretasGraphs play a central role in the world of algorithms. For example, navigation devices use an algorithm to compute shortest paths on a graph to answer a route query. Many planning and assignment problems can also be easily modeled as problems on graphs. In principle, it is true that a great many problems can be thought of as graph problems, so designing efficient algorithms for such problems is an important subfield of theoretical computer science.
In this lecture we will enter the world of graph algorithms. On the one hand, we will learn about important algorithmic problem classes on graphs and efficient algorithms to solve them. Among other things, we will look at finding shortest paths, flows, cuts, separators, and matchings in graphs. Algorithms for these problems have a wide variety of applications, making them an important and useful tool for any algorithmicist. On the other hand, we will also study how constraints on the graphs at hand affect the complexity of the problems and their algorithmic solution. For example, many algorithmic problems are more efficiently solvable on trees and planar graphs (i.e., graphs that can be embedded in the plane without intersection) than on general graphs. We will also explore some properties of graphs that we can exploit specifically for designing efficient algorithms. For example, trees and planar graphs have small separators (sets of nodes whose removal causes the graphs to decompose into multiple context components), which helps design efficient divide & conquer algorithms.
The goal of the lecture is the development and training of a structured approach to algorithmic problems on graphs. In doing so, we will jointly develop efficient graph algorithms with appropriate data structures, prove their correctness, and analyze their resource requirements (runtime and memory). In addition, the lecture will highlight special graph classes and other important concepts in graph theory and their impact on the world of algorithms.notele-TASKtele-task@hpi.deen℗; ©; tele-TASKThu, 30 Nov 2023 01:44:39 GMTPyRSS2Gen-1.1.0http://blogs.law.harvard.edu/tech/rss- Minimum Cuts Algorithm by Stoer and Wagnerhttps://www.tele-task.de/lecture/video/10316/enDr. George Skretas00:56:43tele-TASK, HPI, computer science, technology, Germany, PotsdamDr. George SkretasDr. George Skretashttps://www.tele-task.de/lecture/video/10316/Mon, 27 Nov 2023 13:30:00 GMT
- Flows, Cuts and the Gomory Hu-Treehttps://www.tele-task.de/lecture/video/10306/enDr. George Skretas01:09:26tele-TASK, HPI, computer science, technology, Germany, PotsdamDr. George SkretasDr. George Skretashttps://www.tele-task.de/lecture/video/10306/Thu, 23 Nov 2023 11:00:00 GMT
- Flow with costshttps://www.tele-task.de/lecture/video/10298/enDr. George Skretas01:22:07tele-TASK, HPI, computer science, technology, Germany, PotsdamDr. George SkretasDr. George Skretashttps://www.tele-task.de/lecture/video/10298/Mon, 20 Nov 2023 00:00:00 GMT
- Maximum Flows Using PUSH-RELABELhttps://www.tele-task.de/lecture/video/10288/enDr. George Skretas01:08:57tele-TASK, HPI, computer science, technology, Germany, PotsdamDr. George SkretasDr. George Skretashttps://www.tele-task.de/lecture/video/10288/Mon, 13 Nov 2023 13:30:00 GMT
- Maximum Flows - Tuning of Ford-Fulkersonhttps://www.tele-task.de/lecture/video/10274/enDr. George Skretas00:39:18tele-TASK, HPI, computer science, technology, Germany, PotsdamDr. George SkretasDr. George Skretashttps://www.tele-task.de/lecture/video/10274/Thu, 09 Nov 2023 11:00:00 GMT
- Maximum Flowshttps://www.tele-task.de/lecture/video/10267/enDr. George Skretas00:00:00tele-TASK, HPI, computer science, technology, Germany, PotsdamDr. George SkretasDr. George Skretashttps://www.tele-task.de/lecture/video/10267/Mon, 06 Nov 2023 13:30:00 GMT
- Applications of BFS/DFShttps://www.tele-task.de/lecture/video/10230/enDr. George Skretas01:14:45tele-TASK, HPI, computer science, technology, Germany, PotsdamDr. George SkretasDr. George Skretashttps://www.tele-task.de/lecture/video/10230/Mon, 23 Oct 2023 13:30:00 GMT