Combinatorics of Mixed Graphs -- Complexity and Homomorphism

混合图的组合——复杂性和同态

• 批准号: RGPIN-2019-04857
• 负责人: Duffy, Christopher
• 金额: $ 1.68万
• 依托单位: University of Saskatchewan
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2019
• 资助国家: 加拿大
• 起止时间: 2019-01-01 至 2020-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=679181
• 关键词: Combinatorics; Mixed; Graphs; Complexity; Homomorphism

Graph models are a fundamental tool for those working with relational data; they allow social scientists to study changing social and political alliances within a social network; they allow medical schools and hospitals a method to fairly pair medical residents with hospitals; and they allow engineers to find efficient schedules for large-scale engineering projects. However, these models are limited in that they often assume that the relationship between a pair of objects (such as people, resident and hospitals, or tasks) is identical, regardless of the pair being considered. ******In this research we study a graph model that allows for a more sophisticated notion of relationship. For example, using such a model, researchers can study social networks in which the relationship between family members is noted as a different kind of relationship as that between friends. The long-term goal of this research is to develop tools for graph models with this more sophisticated notion of relationship so that researchers and industry may apply these models in their respective areas. In particular, this research focusses on assignment problems; problems in which objects are grouped, or not grouped, based on their relationship to one another. The past study of assignment problems has lead to improvements in compiler use in parallel processing, in frequency assignments in radio communications networks, and in timetable scheduling. This research explores fundamental questions about the computational nature of assignment problems defined for graph models with more sophisticated notions of relationship. It characterizes these problems based on the existence (or suspected lack thereof) of efficient algorithms. For those problems for which it is expected that no efficient algorithm can exist, this research develops approximation algorithms, algorithms that provide a solution that is guaranteed to approximate the optimal solution within a fixed error bound.**

图模型是处理关系数据的基本工具；它们使社会科学家能够研究社会网络中不断变化的社会和政治联盟；它们允许医学院和医院公平地将住院医生与医院配对；它们还允许工程师为大型工程项目找到有效的时间表。然而，这些模型是有限的，因为它们通常假设一对对象（如人、住院医生和医院或任务）之间的关系是相同的，而不考虑这对对象。******在这项研究中，我们研究了一个图形模型，它允许更复杂的关系概念。例如，使用这样的模型，研究人员可以研究社会网络，其中家庭成员之间的关系被视为与朋友之间的关系不同。这项研究的长期目标是开发具有这种更复杂的关系概念的图形模型工具，以便研究人员和工业界可以在各自的领域应用这些模型。特别地，本研究聚焦于指派问题；对象根据彼此之间的关系分组或不分组的问题。过去对分配问题的研究已经使编译器在并行处理、无线电通信网络的频率分配和时间表安排中的使用有所改进。本研究探讨了为具有更复杂关系概念的图模型定义的分配问题的计算性质的基本问题。它基于有效算法的存在（或怀疑缺乏）来描述这些问题。对于那些预期不存在有效算法的问题，本研究开发了近似算法，该算法提供的解保证在固定的误差范围内近似最优解。**