Sublinear Insights: A Faster Classical Algorithm for Edge Coloring
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore a cutting-edge lecture on graph theory and algorithmic advancements presented by Sepehr Assadi from the University of Waterloo and Rutgers University. Delve into the world of edge coloring algorithms, starting with Vizing's theorem and its implications for graphs with maximum degree Delta. Discover a groundbreaking randomized algorithm that achieves a Delta+O(log n) coloring in near-linear time, challenging the longstanding O(m\sqrt(n)) time complexity of previous methods. Learn how this novel approach, inspired by sublinear algorithmic techniques, leads to an O(n^2 log(n)) expected time algorithm for the (Delta+1) edge coloring problem, marking a significant improvement over existing bounds. Gain insights into the theoretical foundations and practical implications of this research, which pushes the boundaries of graph coloring efficiency and opens new avenues for algorithmic graph theory.
Syllabus
Sublinear Insights: A Faster (Classical) Algorithm for Edge Coloring
Taught by
Simons Institute
Related Courses
Intro to AlgorithmsUdacity Algorithmic Thinking (Part 1)
Rice University via Coursera Design and Analysis of Algorithms
Chennai Mathematical Institute via Swayam Capstone: Analyzing (Social) Network Data
University of California, San Diego via Coursera Algorithms on Graphs
University of California, San Diego via Coursera