基于因子图求解(3,4=)-CNF公式类下可满足问题

合取范式(CNF)公式F是(3,4=)-CNF公式,如果F中每个子句的长度是3,每个变元出现的次数恰好为4次.与(3,4=)-CNF公式所关联的因子图是一类规则的二部图,即每个子句结点的度为3,每个变元结点的度为4,此类规则图被称为(3,4)-双向正则二部图.对于一个(3,4=)-CNF公式F,如果它关联的因子图GF有P7路径因子,则F可满足.     

steiner树问题的近似算法

著名的Steiner树问题是,给定图G=(V、E),QV,在边集E上定义权函数f:E→Z~+,要求在图G上找一子树T=(Y,U),使得QY且 ∑_(c∈U)f(e)达到极小以后,我们称该问题为ST问题,R.M.Karp曾证明ST问题为NP-完全的,本文作者曾提出图上Steiner树问题:在图G=(V,E),QV上,要求一子树T=(Y,     

k-LSAT(k≥3)是NP-完全的(英文)

合取范式(conjunctive normal form,简称CNF)公式F是线性公式,如果F中任意两个不同子句至多有一个公共变元.如果F中的任意两个不同子句恰好含有一个公共变元,则称F是严格线性的.所有的严格线性公式均是可满足的,而对于线性公式类LCNF,对应的判定问题LSAT仍然是NP-完全的.LCNF≥k是子句长度大于或等于k的CNF公式子类,判定问题LSAT≥k的NP-完全性与LCNF≥k中是否含有不可满足公式密切相关.即LSAT≥k的NP-完全性取决于LCNF≥k是否含有不可满足公式.S.Porschen等人用超图和拉丁方的方法构造了LCNF≥3和LCNF≥4中的不可满足公式,并提出公开问题:对于k≥5,LCNF≥k是否含有不可满足公式?将极小不可满足公式应用于公式的归约,引入了一个简单的一般构造方法.证明了对于k≥3,k-LCNF含有不可满足公式,从而证明了一个更强的结果:对于k≥3,k-LSAT是NP-完全的.     

无向圆盘图中最大r跳独立邻居数的估计

本文考虑无向圆盘图中的最大r-跳独立邻居数(r≥2)。给定一个圆盘图G=(V,E),对任意v?V,用N'(V)表示所有距节点v跳数最多为r的节点集合,则对G中任何一个r-跳独立集I,其在N'(V)内最多有β个节点,■这里K是圆盘图的最大圆盘半径与最小圆盘半径的比值.     

一个正则NP-完全问题及其不可近似性

通过一个适当的归约变换,可以将一个CNF (conjunctive normal form)公式变换为另一个具有某种特殊结构或性质的公式,使两者具有相同的可满足性.带有正则结构的CNF公式的因子图在图论中具有某些良好的性质和结果,可以用于研究公式的可满足性和计算复杂性.极小不可满足公式具有一个临界特征,公式本身不可满足,从原始公式中删去任意一个子句后得到的公式可满足.借助此临界特性,给出了一个从3-CNF公式到正则(3,4)-CNF公式的多项式归约转换.这里,正则(3,4)-CNF公式是指公式中每个子句的长度恰为3,每个变元出现的次数恰为4.因此,正则(3,4)-SAT问题是一个NP-完全问题,并且MAX(3,4)-SAT是不可近似问题.     

极小不可满足公式在多项式归约中的应用

合取范式(CNF)公式F是极小不可满足的,如果F不可满足,并且从F中删去任意一个子句后得到的公式可满足,(r,s)-CNF是限制CNF公式中每个子句恰有r个不同的文字,且每个变元出现的次数不超过s次的公式类,对应的满足性问题(r,s)-SAT指实例公式限制于(r,s)-CNF.对于正整数r≥3,有一个临界函数f(r),使得(r,f(r))-CNF中的公式都是可满足的,而(r,f(r)+1)-SAT却是NP-完全的.函数f是否可计算是一个开问题,除了知道f(3)=3,f(4)=4外,只能估计f(r)的界.描述了极小不可满足公式在CNF公式类之间转换中的作用.为使转换过程中引入较少的新变元,给出了CNF公式到3-CNF公式的一种新的转换方法,对于长度为l(＞3)的子句,仅需引入|l/2|个新变元.并且,给出了CNF到(r,s)-CNF公式转换以及(r,s)-CNF中不可满足公式构造的原理和方法.     

正则(3,4)-CNF公式的社区结构

通过构造适当的极小不可满足公式以实现在多项式时间内将3-CNF公式归约转换为一个正则(3,4)-CNF公式,转换后的公式与原公式具有相同的可满足性,同时公式的结构也发生相应的变化。图的社区结构反映了图的模块特性,文中将CNF公式转化为相应的图,研究公式图的模块特性与公式某些性质之间的关系。将归约前后的两类公式转换为相应的图并研究其模块特性,发现转换后得到的正则(3,4)-CNF公式具有较高的模块度。此外,在使用DPLL(Davis Putnam Logemann Loveland)算法求解CNF公式的过程中,发生冲突时利用冲突驱动子句学习策略,得到一个学习子句并将其添加到原公式中,使得原公式的模块度降低。研究发现:将DPLL算法与冲突驱动子句学习策略结合应用到正则(3,4)-CNF公式时,其学习子句所包含的绝大部分变元位于不同的社区中。     

欧式平面上瓶颈Steiner树问题的一个近似算法

近些年来，Steiner树问题在理论和应用上都引起了极大的关注，尤其在日渐成熟的近似算法设计理论方面，该问题占有一定的中心地位。给定赋权连通图G=(V，E，W)及顶点子集S包含V(S中顶点称为terminals)，传统的Steiner树问题要求寻找一棵最小的树联接5中的所有顶点，该树可能包含V-S中的顶点(称为Steiner点)。即使图中每条边的权值仅限制为1或2时，传统的Steiner树问题仍然是MAX—SNP Hard。     

内部节点受限的最小生成树问题算法研究

研究内部节点受限的最小生成树问题：给定一个赋权无向完全图[G=V,E],假定[w:E→R+]为边集[E]的权重函数且满足三角不等式,给定点集[V]的一个子集[RR?V],目标是寻找图[G]的一个满足[R]中的点皆为内部顶点的权重最小的生成树。由于该问题是[NP-]困难的,提出了一个伪多项式时间最优算法,设计了一个近似比为2的多项式时间近似算法,并且给出例子以说明该近似比是紧的。     

图上STEINER树问题及其近似算法

1.图上STEINER树问题是NP-完全的 著名的网络上Steiner问题是:对给定图G=(V,E),其中V=PUS,在边集E(G)上定义权函数f:E(G)→Z~ ,构成网络N(G,f)。要求在网络N(G,f)上寻找一棵子树T=(Y,u),使得P(?)Y,且     

不可满足公式的同态证明系统

合取范式(CNF)公式H到F的同态φ是一个从H的文字集合到F的文字集合的映射,并保持补运算和子句映到子句.同态映射保持一个公式的不可满足性.一个公式是极小不可满足的是指该公式本身不可满足,而且从中删去任意一个子句后得到的公式可满足.MU(1)是子句数与变元数的差等于1的极小不可满足公式类.一个三元组(H,φ,F)称为的一个来自H的同态证明,如果φ是一个从H到F的同态.利用基础矩阵的方法证明了:一个不可满足公式F的树消解证明,可以在多项式时间内转换成一个来自MU(1)中公式的同态证明.从而,由MU(1)中的公式构成的同态证明系统是完备的,并且由MU(1)中的公式构成的同态证明系统与树消解证明系统之间是多项式等价的.     

Algorithms for Computing the QR Decomposition of a Set of Matrices with Common Columns

The QR decomposition of a set of matrices which have common columns is investigated. The triangular factors of the QR decompositions are represented as nodes of a weighted directed graph. An edge between two nodes exists if and only if the columns of one of the matrices is a subset of the columns of the other. The weight of an edge denotes the computational complexity of deriving the triangular factor of the destination node from that of the source node. The problem is equivalent to constructing the graph and finding the minimum cost for visiting all the nodes. An algorithm which computes the QR decompositions by deriving the minimum spanning tree of the graph is proposed. Theoretical measures of complexity are derived and numerical results from the implementation of this and alternative heuristic algorithms are given.     

图的树分解及其算法应用研究进展

图的树宽和树分解是图子式理论中发展起来的两个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。从图的树宽特性、图的树分解算法、图的树分解在复杂算法问题求解中的应用等方面对近年来的相关研究进展做了深入的分析和介绍,结合一些简洁的实例分析了一些重要的原理和方法,讨论了其中的一些问题,并给出了今后的一些研究方向。     

求解多文字可满足SAT问题的置信传播算法

可满足(SAT)问题是指:是否存在一组布尔变元赋值,使得合取范式公式中每个子句至少有一个文字为真.多文字可满足SAT问题是指:是否存在一组布尔变元赋值,使得CNF公式中每个子句至少有两个文字为真.显然,此问题仍然是一个NP难问题.为了研究解决多文字可满足SAT问题的算法,引入随机实例产生模型,设计求解多文字可满足SAT问题的置信传播算法.最后,用实例模型产生了大量数据进行实验验证,结果表明:该算法求解多文字可满足SAT问题的性能优于其他启发式算法.     

A simple and fast parallel coloring for distance-hereditary graphs

In the literature, there are quite a few sequential and parallel algorithms to solve problems on distance-hereditary graphs. Two well-known classes of graphs, which contain trees and cographs, belong to distance-hereditary graphs. We consider the vertex-coloring problem on distance-hereditary graphs. Let T/sub d/(|V|, |E|) and P/sub d/d(|V|, |E|) denote the time and processor complexities, respectively, required to construct a decomposition tree representation of a distance-hereditary graph G=(V,E) on a PRAM model M/sub d/. Our algorithm runs in O(T/sub d/(|V|, |E|)+log|V|) time using O(P/sub d/(|V|, |E|)+|V|/log|V|) processors on M/sub d/. The best known result for constructing a decomposition tree needs O(log/sup 2/ |V|) time using O(|V|+|E|) processors on a CREW PRAM. If a decomposition tree is provided as input, we solve the problem in O(log |V|) time using O(|V|/log |V|) processors on an EREW PRAM. To the best of our knowledge, there is no parallel algorithm for this problem on distance-hereditary graphs.     

A Heuristic for Dijkstra's Algorithm with Many Targets and Its Use in Weighted Matching Algorithms

We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node s and a target set T is specified and the goal is to compute a shortest path from s to a node in T . Our interest in the shortest path problem with many targets stems from its use in weighted bipartite matching algorithms. A weighted bipartite matching in a graph with n nodes on each side reduces to n SSMTSP problems, where the number of targets varies between n and 1 . The SSMTSP problem can be solved by Dijkstra's algorithm. We describe a heuristic that leads to a significant improvement in running time for the weighted matching problem; in our experiments a speed-up by up to a factor of 12 was achieved. We also present a partial analysis that gives some theoretical support for our experimental findings.     

Tree Spanners for Bipartite Graphs and Probe Interval Graphs

A tree t-spanner T in a graph G is a spanning tree of G such that the distance between every pair of vertices in T is at most t times their distance in G. The tree t-spanner problem asks whether a graph admits a tree t-spanner, given t. We first substantially strengthen the known results for bipartite graphs. We prove that the tree t-spanner problem is NP-complete even for chordal bipartite graphs for t ≥ 5, and every bipartite ATE-free graph has a tree 3-spanner, which can be found in linear time. The previous best known results were NP-completeness for general bipartite graphs, and that every convex graph has a tree 3-spanner. We next focus on the tree t-spanner problem for probe interval graphs and related graph classes. The graph classes were introduced to deal with the physical mapping of DNA. From a graph theoretical point of view, the classes are natural generalizations of interval graphs. We show that these classes are tree 7-spanner admissible, and a tree 7-spanner can be constructed in (m log n) time.     

多文字可满足SAT问题的相变点上界

可满足（SAT）问题是指：是否存在一组布尔变元赋值,使得随机合取范式（CNF）公式中每个子句至少有1个文字为真。多文字可满足SAT问题是指：是否存在一组布尔变元赋值,使得随机CNF公式中每个子句至少有2个文字为真。此问题仍然是一个NP难问题。定义约束密度α为CNF公式子句数与变元数之比,对该问题的相变点上界α*进行了研究。如果α>α*,则多文字可满足SAT问题高概率不可满足。通过一阶矩一个简单的推断,可以证明α*=-ln 2/ln(1-(k+1)/2k),当k=3时,α*=1。利用Kirousis等人的局部最大值技术,提升了多文字可满足3-SAT问题的相变点上界α*=0.7193。最后,选择了大量数据进行实验验证,结果表明,理论结果与实验结果相吻合。     

Two-manifold cell-decomposition of r-sets.

This paper discusses the relationships studied between manifold solids and r-sets by defining an r-set as a decomposition in two-manifold cells. This decomposition is represented as a graph (Two-manifold Cell Decomposition graph TCD) in which each node corresponds to a 2 manifold component of the regular set, while each arc or hyperarc defines a non-manifold adjacency between components. The TCD model and data structure encoding it were designed in order to be compatible with a traditional boundary architecture.