Approximate Graph Products

近似图产品

• 批准号: 25023853
• 负责人: Professor Dr. Peter Florian Stadler
• 金额: --
• 依托单位: Lehrstuhl für Angewandte Mathematik
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2006
• 资助国家: 德国
• 起止时间: 2005-12-31 至 2011-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/25023853?language=en
• 关键词: Approximate; Graph; Products

Graph products arise in a variety of different contexts, from computer science to theoretical biology and computational engineering. At the abstract level, one arrives at the same set of mathematical and algorithmic questions. For each of the four standard products, the Cartesian product, the strong product, the direct product, and the lexicographic product, one may ask a series of questions of increasing complexity: How much can graph products be perturbed such that the product structure is still recognizable and unique? How can we recognize that a given graph contains a factorizable subgraph as an induced subgraph, isometric subgraph, or convex subgraph? What happens if we only require approximate factorizability? Given the practical interest in approximate graph factorizations in computational biology, and for example in computational engineering, it may come as a surprise that this topic has received little systematic attention so far. Here we propose to investigate both the mathematical structure of approximate graph products as well as their algorithmic aspects. While it is likely that many of the problems mentioned above will turn out to be NP-complete it is nevertheless of interest to investigate exact algorithms, exact approximations, and heuristic approaches.

图形产品出现在各种不同的背景下，从计算机科学到理论生物学和计算工程。在抽象的层面上，人们会遇到同样的数学和算法问题。对于四种标准积（笛卡尔积、强积、直积和字典序积）中的每一种，人们可能会问一系列越来越复杂的问题：图积可以被扰动多少，使得积的结构仍然是可识别的和唯一的？我们怎样才能识别一个给定的图包含一个可因子分解的子图是导出子图、等距子图还是凸子图？如果我们只需要近似可因式分解会发生什么？考虑到在计算生物学和计算工程中对近似图因子分解的实际兴趣，到目前为止，这个主题几乎没有受到系统的关注，这可能会让人感到惊讶。在这里，我们建议调查的数学结构的近似图产品，以及他们的算法方面。虽然上面提到的许多问题很可能是NP完全的，但研究精确算法、精确近似和启发式方法仍然很有意义。