图 书 馆
曲面嵌入图的基本算法Basic algorithms for surface-embedded graphs |
|
| 课程网址: | http://videolectures.net/computationaltopology2013_erickson_algor... |
| 主讲教师: | Jeff Erickson |
| 开课单位: | 伊利诺伊大学 |
| 开课时间: | 2013-11-04 |
| 课程语种: | 英语 |
| 中文简介: |  对于许多经典的算法图问题，对于具有附加结构的图，已知更快的算法。这个简短的课程将探讨一些重要的算法技术，以解决图形无法在平面或其他表面上绘制而不会交叉边缘的问题。本课程将介绍几种基本的数学工具，包括欧拉公式，旋转系统，对偶，树cotree分解，组合高斯邦纳定理，同伦，同构，覆盖空间，平衡分隔符和树宽，以及这些工具在计算中的应用几个NP硬概率的最小生成树，最短路径，最小割和近似解 |
| 课程简介: | For many classical algorithmic graph problems, faster algorithms are known for graphs that have additional structure. This short course will survey some important algorithmic techniques for graphs that can be drawn in the plane or other surfaces without crossing edges. The course will introduce several fundamental mathematical tools, including Euler's formula, rotation systems, duality, tree-cotree decompositions, the combinatorial Gauss-Bonnet theorem, homotopy, homology, covering spaces, balanced separators, and treewidth, as well as applications of these tools for computing minimum spanning trees, shortest paths, minimum cuts, and approximation solutions for several NP-hard prob |
| 关 键 词: | 算法; 数学工具 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2020-10-12：zyk |
| 最后编审: | 2020-10-12：zyk |
| 阅读次数: | 42 |