Combinatorics of Mixed Graphs -- Complexity and Homomorphism

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

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

对于使用关系数据的人来说，图模型是一个基本工具。 它们允许社会科学家研究社会网络中改变社会和政治联盟的变化；他们允许医学院和医院一种将医疗居民与医院搭配的方法；它们允许工程师找到大型工程项目的有效时间表。但是，这些模型受到限制，因为他们通常认为一对对象（例如人，居民和医院或任务）之间的关系是相同的，无论考虑如何考虑。 在这项研究中，我们研究了一个图形模型，该模型允许更复杂的关系概念。例如，使用这样的模型，研究人员可以研究社交网络，其中家庭成员之间的关系被认为是与朋友之间的一种不同类型的关系。这项研究的长期目标是使用这种更复杂的关系概念开发图形模型的工具，以便研究人员和行业可以在各自的领域应用这些模型。特别是，这项研究的重点是分配问题；根据对象相互关系或不分组对象的问题。过去对分配问题的研究已导致编译器在并行处理，无线电通信网络中的频率分配以及时间表计划中的改善。这项研究探讨了有关针对关系更复杂概念的图形模型定义的分配问题计算性质的基本问题。它根据有效算法的存在（或怀疑缺乏）来表征这些问题。对于那些预期不存在有效算法的问题，本研究会开发近似算法，算法，这些算法提供了一种可以保证在固定误差界内近似最佳解决方案的解决方案。