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.**

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