图的弦性计算

The chordality of a graph equals to the length of the longest induced cycle in the graph. The structural properties of the class of graph with bounded chordality plays an important role in the algorithmic design. In this project, we will study the problem of computing the chordality of graphs, mainly including the following three parts: (1) based on the fact that chordal graphs, graphs with chordality at most 3, are closed related with the tree decompositions, we will study the relations between k-chordal graphs, graphs with chordality at most k≥3, and the k-super-caterpillar tree decompositions; and design practical algorithms for computing the chordality using k-super-caterpillar tree decompositions; (2) In the class of planar graphs, design more efficient algorithms taking advantages of the structural properties of the planar k-super-caterpillars; (3) A relative interesting problem is the complexity of deciding whether there exists a Hamiltonian cycle in a graph with a Hamiltonian path. The research will design new algorithms for computing the chordality of graphs; and improve the applications of the structural properties of graphs with bounded chordality in large scale networks in practice.

一个图的弦性等于该图中最长的生成圈的长度，弦性有界的图类的结构特征在算法设计中起到重要作用，本项目旨在研究图的弦性计算问题，拟进行三方面的研究：（1）以弦图，即弦性至多是3的图类，与树分解之间的关系为基础，研究k-弦图，即弦性至多是k≥3的图类，与k-超毛毛虫树分解之间的关系，设计出以k-超毛毛虫树分解为工具的实用算法计算图的弦性；（2）在平面图类里，由平面k-超毛毛虫的结构特征，设计出较一般图更有效的算法；（3）一个相关的有趣问题是：判定一个有哈密尔顿路的图是否存在哈密尔顿圈问题的计算复杂度。本项目的研究对于设计计算图的弦性的实用算法，并将弦性有界的图类的结构特征应用于大规模复杂网络中具有重要的促进作用。