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）将Gragr Grammars应用到块间隔，（7）随机的最高型jones polynom sam and（7）jones polynom als and and jones plody and sampll and jones sampl and（8）。在该研究项目中，我们为上述问题设计了许多算法。我们开发的是：一种用于计数图形同构的多项式时间算法时，当这些输入图具有界型树宽度时，当这些输入图具有有限的路径宽度时，用于图形的对数空间空间算法，一种多项式时代近似值。提取K-EDGE子图，这是一种用于确定给定平面图是否具有双重欧拉游览的线性时间算法，一种用于计算某些类别的椒盐脆饼链接的多项式算法，用于计算某些类别的jones多项式链接的最大程度SAT/MAXSAT问题的输入数据。

项目成果

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）。

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：“平面圆盘地图上的分层拓扑推理”计算科学讲义。

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

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

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

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

Motoki, M., Uehara, R.: "Unique Solution Instance Generation for the 3-Satisfiability(3AT)Problems"Frontiers in Artificial Intelligence and Applications. Vol.63. 293-307 (2000)

Motoki, M.、Uehara, R.：“针对 3-可满足性 (3AT) 问题的独特解决方案实例生成”人工智能和应用前沿。