权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Combinatorial Optimization Algorithms for Hereditary Graph Classes

遗传图类的组合优化算法

基本信息

批准号：
EP/H021426/1
负责人：
K Vuskovic
金额：
$ 12.27万
依托单位：
University of Leeds
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2010
资助国家：
英国
起止时间：
2010 至无数据
项目状态：
已结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FH021426%2F1
关键词：
Combinatorial Optimization Algorithms Hereditary Graph

项目摘要

Developing efficient algorithms for solving combinatorial problems has been of great importance to the modern technological society. The applications include diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, etc. Problems such as assigning frequencies to mobile telephones, can be modeled using graphs, and then the problem is reduced to coloring the vertices of the graph so that no two adjacent vertices receive the same color (of course the interest is in the minimum number of colors, and this is called the chromatic number of a graph). Many other applications in the real world reduce to the same coloring problem on graphs. Unfortunately, finding the chromatic number of a graph and some other optimization problems such as finding the size of a largest clique in a graph, are NP-complete in general. This means that it is highly unlikely that these problems can be solved efficiently on a computer (i.e. it is unlikely that polynomial time algorithms for these problems exist). One of the ways to deal with this situation is to find classes of graphs for which these problems can be solved in polynomial time.This project will focus on developing techniques for obtaining combinatorial optimization algorithms by expoliting structural analysis of hereditary graph classes. Many important graph classes are hereditary (i.e. closed under taking induced subgraphs), such as perfect graphs. For a difficult optimization problem, such as finding the chromatic number of a graph or the size of its largest clique, to be solvable in polynomial time for a given class, it means that this class must have some strong structure. The proposed research is about trying to understand what is this strong structure that will allow polynomial time combinatorial optimization algorithms, and developing techniques for obtaining the desired structure theorems and using them in algorithms.

开发解决组合问题的有效算法对于现代技术社会非常重要。应用包括交通、电信、分子生物学、工业工程等不同领域。诸如为移动电话分配频率之类的问题可以使用图进行建模，然后将问题简化为对图的顶点进行着色，以便没有两个相邻顶点接收相同的颜色（当然，兴趣在于颜色的最小数量，这称为图的色数）。现实世界中的许多其他应用程序都会简化为图形上的相同着色问题。不幸的是，求图的色数和其他一些优化问题（例如求图中最大团的大小）通常是 NP 完全问题。这意味着这些问题不太可能在计算机上有效解决（即不太可能存在针对这些问题的多项式时间算法）。处理这种情况的方法之一是找到可以在多项式时间内解决这些问题的图类。该项目将重点开发通过利用遗传图类的结构分析来获得组合优化算法的技术。许多重要的图类是遗传的（即在导出子图下封闭），例如完美图。对于一个困难的优化问题，例如找到图的色数或最大团的大小，对于给定类，要在多项式时间内解决，这意味着该类必须具有某种强大的结构。拟议的研究旨在尝试了解这种允许多项式时间组合优化算法的强大结构是什么，并开发获得所需结构定理并将其用于算法的技术。