Isomorphism Testing for Graphs Excluding Small Minors
Offered By: IEEE via YouTube
Course Description
Overview
Explore a 16-minute IEEE conference talk on graph isomorphism testing for graphs excluding small minors. Delve into the history and main results of the Graph Isomorphism Problem, focusing on t-CR-bounded graphs. Learn about key decomposition techniques, including the Main Decompositions Theorem, and their application in developing a quasipolynomial-time isomorphism algorithm. Discover how these concepts relate to finding "Patient Zero" in infection spread models. Gain insights from experts Martin Grohe, Daniel Neuen, and Daniel Wiebking as they present their research and discuss future perspectives in this fascinating area of graph theory and algorithms.
Syllabus
Intro
Graph Isomorphism Problem
History and Main Result
Main Decompositions Result
t-CR-bounded graphs
Finding Patient Zero
How the Infection Spreads?
Main Decompositions Theorem
Quasipolynomial-time isomorphism algorithm
Outlook
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
Aplicaciones de la teoría de grafos a la vida realMiríadax Aplicaciones de la Teoría de Grafos a la vida real
Universitat Politècnica de València via UPV [X] Introduction to Computational Thinking and Data Science
Massachusetts Institute of Technology via edX Genome Sequencing (Bioinformatics II)
University of California, San Diego via Coursera Algorithmic Information Dynamics: From Networks to Cells
Santa Fe Institute via Complexity Explorer