Главная
Study mode:
on
1
Intro
2
Capacitated Vehicle Routing (CVR)
3
"Approximable" Instances.
4
"Approximable" means
5
Results for Subset TSP
6
Two techniques to design a PTAS
7
PTAS from Light Preservers
8
PTAS from Low Treewdith Embedding
9
The Framework
10
Light Preservers from Local Spanners
11
The rest of the talk: find L-local spanners.
12
Planar graph + One Vortex and D = 0(L)
13
Removing Diameter Constraint
14
Planar graph + O(1) Vortices
15
Tree of Clique-sums of Nearly-embed. Graphs
16
Open problems
Description:
Explore cutting-edge graph theory concepts in this 24-minute IEEE conference talk covering light spanners, low-treewidth embeddings, and efficient traversing in minor-free graphs. Delve into Capacitated Vehicle Routing, Subset TSP, and techniques for designing Polynomial-Time Approximation Schemes (PTAS). Learn about light preservers, local spanners, and their applications in planar graphs with vortices. Examine tree structures of clique-sums in nearly-embedded graphs and discover open problems in the field. Gain insights from researchers Vincent Cohen-Addad, Arnold Filtser, Philip N. Klein, and Hung Le as they present advanced algorithms and graph theory applications.

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

IEEE
Add to list