权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

CAREER: Exploiting Topology in Graph Algorithm Design

职业：在图算法设计中利用拓扑

基本信息

批准号：
1942597
负责人：
Kyle Fox
金额：
$ 58.67万
依托单位：
University of Texas at Dallas
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2020
资助国家：
美国
起止时间：
2020-10-01 至 2025-09-30
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1942597&HistoricalAwards=false
关键词：
CAREER Exploiting Topology Graph Algorithm

项目摘要

Graphs, also known as networks, are used to represent many kinds of relationships between pairs of entities. For example, a graph may describe pairs of networking devices directly connected together or pairs of roadway intersections connected by a stretch of road. Many useful tasks, such as understanding the reliability of a computer network or finding the fastest route between two locations, can be performed by doing computations on these graphs. When a graph has certain properties such as being drawable on a piece of paper without crossings between its connections, it becomes possible to do these types of computations much more quickly than if the properties were not present. Many of these faster computations rely on important results from topology, the mathematical study of what properties geometric objects maintain after certain types of deformations. This project seeks to better understand the role topology can take both in performing fast computations on graphs and explaining what graph properties are necessary for these fast computations. The project aims to make substantial topology based additions to the toolkit used in graph computations. These additions should make new computational tasks possible and greatly simplify established tasks. The project involves a substantial education component as well that includes educating students on the known connections between topology and computer science and providing undergraduate minority students their first opportunities to participate in the research process.The research activities have three components. The first involves generalizing known planar graph algorithms for many fundamental problems in computer science to graphs embeddable in low complexity surfaces. The second component explores how topological intuitions and tools created during the first component can be used to solve difficult problems back in the setting of planar graphs. The third component involves pushing these tools to their limits in the creation of algorithms for more general families of graphs than those embeddable in low complexity surfaces with a focus on the so-called H-minor-free graphs. The types of problems studied for all three components include the computations of optimal network flows, minimum cuts, and shortest paths. Student education will take place through the development of a new course in computational topology at the awardee institution that focusses on graph algorithms and topological data analysis. Activities for undergraduate minority students will consist primarily of the implementation and experimental analysis of algorithms designed during the primary research activities.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

图，也称为网络，用于表示实体对之间的多种关系。例如，一个图可以描述直接连接在一起的网络设备对或由一段道路连接的道路交叉口对。许多有用的任务，如理解计算机网络的可靠性或找到两个地点之间最快的路线，都可以通过对这些图进行计算来执行。当图具有某些属性时，例如可以在一张纸上绘制，其连接之间没有交叉点，则可以比不存在这些属性时更快地进行这些类型的计算。许多这些更快的计算依赖于拓扑学的重要结果，拓扑学是对几何物体在某些类型的变形后保持的属性的数学研究。本项目旨在更好地理解拓扑在图上执行快速计算和解释这些快速计算所需的图属性时所扮演的角色。该项目旨在为图计算中使用的工具包添加大量基于拓扑的内容。这些附加功能应该使新的计算任务成为可能，并大大简化已建立的任务。该项目还包含大量的教育内容，包括教育学生了解拓扑学和计算机科学之间的已知联系，并为少数族裔本科生提供第一次参与研究过程的机会。研究活动有三个组成部分。第一个涉及将已知的用于计算机科学中许多基本问题的平面图算法推广到可嵌入在低复杂度曲面上的图。第二个部分探讨了在第一个部分中创建的拓扑直觉和工具如何用于解决平面图形设置中的难题。第三个部分涉及到将这些工具推向其极限，以创建更一般的图族，而不是那些可嵌入低复杂性曲面的算法，重点是所谓的无h次元图。这三个组成部分研究的问题类型包括最优网络流、最小切割和最短路径的计算。学生教育将通过在获奖机构开设一门新的计算拓扑课程来进行，该课程侧重于图算法和拓扑数据分析。少数民族本科生的活动将主要包括在主要研究活动中设计的算法的实现和实验分析。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。