Analyzing Computational Complexity of Graph-Theoretic Problems with Restrictions on Width Parameters

分析具有宽度参数限制的图论问题的计算复杂性

• 批准号: 10205224
• 负责人: TODA Seinosuke
• 金额: $ 6.98万
• 依托单位: Nihon University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research on Priority Areas (B)
• 财政年份: 1998
• 资助国家: 日本
• 起止时间: 1998 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-10205224/
• 关键词: algorithm engineering; computational complexity; graph theory; isomorphism problem; isomorphism counting; tree width; Jones polynomial; graph grammar; 計算量理論; 独立点集合問題; 同型性判定; 全域木; マッチング; 二分決定グラフ; アルゴリズム; 辺連結度; 完全独立全域木; サイクル被覆; 独立点集合; 木幅

The purpose of our research project is to analyze the computational complexity of several graph-theoretic problems, mainly in case that those input graphs are bounded on some width parameters. We investigate the following problems : (1) counting graph isomorphisms, (2) graph reachability, (3) extracting k-edge connected subgraphs, (4) deciding whether some plane graph has a dual euler tour, (5) graph decomposition, (6) applications of graph grammars to block diagrams, (7) deciding the maximum degree of a Jones polynomial, (8) random sampling and random generation. In this research project, we design many algorithms for the above problems. What we developed are : a polynomial-time algorithm for counting graph isomorphisms when those input graphs are of bounded tree-width, a logarithmic-space algorithm for graph reachability when those input graphs are of bounded path-width, a polynomial-time approximation scheme for. extracting k-edge subgraphs, a linear-time algorithm for deciding whether a given plane graph has a dual euler tour, a polynomial-time algorithm for computing the maximum degree of Jones polynomial of some class of pretzel links, design a graph grammar for manipulating block diagrams and an efficient algorithm for those syntactic analysis, an efficient random algorithm for generating uniformly an input data for SAT/MAXSAT problem.

我们研究项目的目的是分析几个图论问题的计算复杂性，主要是在这些输入图受某些宽度参数限制的情况下。我们研究以下问题：（1）计算图同构，（2）图可达性，（3）提取k边连通子图，（4）判断某个平面图是否具有对偶欧拉图，（5）图分解，（ 6）图语法在框图中的应用，（7）确定琼斯多项式的最大次数，（8）随机采样和随机生成。在本研究项目中，我们针对上述问题设计了许多算法。我们开发的是：当这些输入图具有有界树宽度时用于计算图同构的多项式时间算法、当这些输入图具有有界路径宽度时用于计算图可达性的对数空间算法、多项式时间近似方案为了。提取k边子图，用于确定给定平面图是否具有双欧拉游览的线性时间算法，用于计算某类椒盐卷饼链接的琼斯多项式最大次数的多项式时间算法，设计用于操作的图语法框图和用于句法分析的有效算法，用于为 SAT/MAXSAT 问题统一生成输入数据的有效随机算法。

项目成果

Z.-Z.Chen and X.He: "Hierarchical Topological Inference on Planar Disc Maps"Lecture Notes in Compute Science. Vol.1858. 115-125 (2000)

Z.-Z.Chen 和 X.He：“平面圆盘地图上的分层拓扑推理”计算科学讲义。

Chen, Z.-Z.: "Approximation Algorithms for Independent Sets in Map Graphs"Lecture Notes in Computer Science(CoCoon'2000). Vol.1858. 105-114 (2000)

Chen, Z.-Z.：“地图中独立集的近似算法”计算机科学讲义（CoCoon2000）。

Plummer, Y., Saito, A.: "Closure and factor-critical graphs"Discrete Mathematics. Vol.215. 171-179 (2000)

Plummer, Y.，Saito, A.：“闭包和因子关键图”离散数学。

Uehara, R., Chen, Z.-Z.: "Parallel Approximation Algorithms for Maximal Weighted Matching in General Graphs"Information Processing Letters. Vo.76. 13-17 (2000)

Uehara, R.、Chen, Z.-Z.：“一般图中最大加权匹配的并行近似算法”信息处理快报。

Hasunuma, T.: "On edge-disjoint spanning trees with small depths"Information Processing Letters. Vol.75. 71-74 (2000)

Hasunuma, T.：“关于小深度的边不相交生成树”信息处理快报。