On Light Spanners, Low-Treewidth Embeddings and Efficient Traversing in Minor-Free Graphs

On Light Spanners, Low-Treewidth Embeddings and Efficient Traversing in Minor-Free Graphs

IEEE FOCS: Foundations of Computer Science via YouTube Direct link

Intro

1 of 16

1 of 16

Intro

Class Central Classrooms beta

YouTube videos curated by Class Central.

Classroom Contents

On Light Spanners, Low-Treewidth Embeddings and Efficient Traversing in Minor-Free Graphs

Automatically move to the next video in the Classroom when playback concludes

  1. 1 Intro
  2. 2 Capacitated Vehicle Routing (CVR)
  3. 3 "Approximable" Instances.
  4. 4 "Approximable" means
  5. 5 Results for Subset TSP
  6. 6 Two techniques to design a PTAS
  7. 7 PTAS from Light Preservers
  8. 8 PTAS from Low Treewdith Embedding
  9. 9 The Framework
  10. 10 Light Preservers from Local Spanners
  11. 11 The rest of the talk: find L-local spanners.
  12. 12 Planar graph + One Vortex and D = 0(L)
  13. 13 Removing Diameter Constraint
  14. 14 Planar graph + O(1) Vortices
  15. 15 Tree of Clique-sums of Nearly-embed. Graphs
  16. 16 Open problems

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.