图的弦性计算

项目名称： 图的弦性计算

项目编号： No.11626181

项目类型： 专项基金项目

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 李碧

作者单位： 西安电子科技大学

项目金额： 3万元

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

中文关键词： 弦性；k-弦图；k-超毛毛虫；树分解；

英文摘要： 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

英文关键词： chordality；k-chordal graph；k-super-caterpillar；tree decompositions；