Transversals, colouring, matchings and covers

横向、着色、匹配和封面

• 批准号: 138677-2010
• 负责人: Haxell, Penelope
• 金额: $ 1.46万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2010
• 资助国家: 加拿大
• 起止时间: 2010-01-01 至 2011-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=451876
• 关键词: Transversals; colouring; matchings; covers

The objectives of my research will be to solve various extremal-type problems in graphs and hypergraphs. A hypergraph H is an abstract object consisting of a set of vertices V and a set of hyperedges E such that each element of E is a subset of V. A graph is just a hypergraph in which every (hyper)edge has size 2. Many important problems, both theoretical and practical, can be expressed in terms of basic questions about graphs or hypergraphs. The problems I will address can all be stated in this purely abstract terminology, and usually involve partitions with certain special properties. However in many cases they come from very concrete problems. Two specific applications I have worked on recently involve effective routing protocols in the internet, and the development of effective schemes for performing automatic fault restoration in electrical power systems. Fault restoration is the process of restoring power in an electrical grid by reconfiguring the network, after a power failure caused by a storm or other accidental damage to power lines or other components of the network. With the development of the smart grid, the need for automation in power restoration and other aspects of network operation is becoming much greater.

我的研究目标是解决图和超图中的各种极值问题。超图H是一个抽象对象，由一组顶点V和一组超边E组成，使得E的每个元素都是V的子集。许多重要的理论和实际问题都可以用关于图或超图的基本问题来表达。我将要解决的问题都可以用这个纯粹抽象的术语来描述，并且通常涉及具有某些特殊属性的分区。然而，在许多情况下，它们来自非常具体的问题。我最近从事的两个具体应用涉及互联网中的有效路由协议，以及在电力系统中执行自动故障恢复的有效方案的开发。故障恢复是在由风暴或对电力线或网络的其他组件的其他意外损坏引起的电力故障之后，通过重新配置网络来恢复电网中的电力的过程。 随着智能电网的发展，对电力恢复和网络运行的其他方面的自动化的需求变得越来越大。