模态K4、D4系统的归结推理

本文将Ｐ．Ｅｎｊａｌｂｅｒｔ和Ｌ．ＦａｒｉｎａｓｄｅｌＣｅｒｒｏ提出的模态归结推理方法推广到命题模态逻辑K₄和D₄系统，建立了K₄逻辑的归结推理ＲK₄；D₄逻辑的归结推理R D₄，分别证明了ＲK₄和ＲD₄关于K相似文献   

C~k连续的保形插值2k次样条函数

Ｃ~ｋ连续的保形插值２ｋ次样条函数方逵（国防科技大学，长沙）ＡＣ~ｋ－ＳＨＡＰＥ－ＰＲＥＳＥＲＶＩＮＧＩＮＴＥＲＰＯＬＡＴＩＮＧＳＰＬＩＮＥＦＵＮＣＴＩＯＮＯＦＤＥＧＲＥＥ２ｋ￥ＦａｎｇＫｕｉ（ＮａｔｉｏｎａｌＵｎｉｖｅｒｓｉｔｙｏｆＤｅｆｅｎｓｅＴｅ...     

通信协议转换器的性质

给定通信协议［Ａ，Ｂ］，［Ｇ，Ｈ］和重要信息映射集合Ｋ，可以构造Ｂ和Ｇ关于Ｋ的对偶积作为这两个协议关于Ｋ的转换器Ｃ．本文讨论这种协议转换模型［Ａ，Ｃ，Ｈ］的死锁和活锁的性质，并给出这种协议转换模型没有死锁和活锁的充要条件．     

三维空间中的最短路问题

在包含一组相互分离凸多面体的三维空间中为任意两点寻找最短路的问题是NP问题.当凸多面体的个数k任意时,它为指数时间复杂度;而当k=1时,为O(n²)（n为凸多面体的顶点数）.文章主要研究了k=2情形下的最短路问题,提出一个在O(n²)时间内解决该问题的算法.所得结果大大优于此情形下迄今为止最好的结果——O(n^{3相似文献}   

低价格中求高性能

Ｃ Ｐ Ｕ：ＡＭＤＫ６－２４００ Ｓｏｃｋｅｔ７接口／散装主板：奔驰 ｋ６Ⅲ１５０ａ ＶＩＡ ＶＴ８２Ｃ５９８ＭＶＰ／ＡＴＸ／Ｓｕｐｅｒ ７／１Ｍ ＣＡＣＨＥ／ ＵＤＭＡ／６６硬盘： ＤｅｓｋＳｔａｒＧＸＰ／ＤＪＮＡ３７１３５０ １３．５Ｇ／ ＵＤＭＡ／６６／２Ｍ／７２００ｒｐｍ／ＩＤＥ／全国联保三年内存：ＡＣＥＲ（宏基）ＡＭ１／６４Ｍ８ｎｓ／１６８ＰＩＮ　ＳＤＲＥＭ／ＰＣ１００显示卡： ３ｄｆｘ Ｖｏｏｄｏｏ３ ２０００ Ｖｏｏｄｏｏ３／１６Ｍ ＳＤＲＡＭ／ＡＧＰ ２ｘ声卡：雅马哈ＹＡＭＡＨＡ７２４／３２硬波表…     

科学计算可视化软件平台GIVE

科学计算可视化软件平台ＧＩＶＥ科学计算可视化软件平台——ＧＩＶＥ（ＧｅｎｅｒａｌＩｎｔｅｒａｃ－ｔｉｖｅＶｌｓｕａｌｌｚａｔｌｏｎＥｎｖｉｒｏｎｍＲｎｔ）是浙江大学ＣＡ］３＆ＣＧ国家重点实验室历时。年开发议成的一个通用可视化应用构造工具，于１９９３年...     

InAs薄膜Hall器件

利用分子束外延（ＭＢＥ）生长的高迁移率ＩｎＡｓ外延层成功制备了的薄膜Ｈａｌ器件。这种Ｈａｌ器件具有灵敏度高、温度特性好等优点。室温下的积灵敏度和电压相关的灵敏度分别为１１ｍＶ／ｍＡ·ｋＧｓ和４０ｍＶ／Ｖ·ｋＧｓ（灵敏度比相同掺杂的ＧａＡｓＨａｌ器件高５０％）。在（２０～７０）℃温度区域内，内阻温度系数和Ｈａｌ电压温度系数分别为８×１０－４／℃，－２×１０－３／℃（恒流驱动）和－３×１０－３／℃（恒压驱动）。     

一类约化梯阵的RaRb表示

本文首先阐明线性R_aR_b变换之间的关系，并提出了算法MR_ab，再引用标准线性R_aR_b变换，证明了R_aR_b变换与算法MR_ab求解方程组的能力是等价的．然后讨论MR_ab与算法ALT之间的关系，进而说明受ALT攻击的那些有限自动机包含     

一种简单阈值方案的优化

秘密分存是一种安全有效的密钥管理技术，现已广泛应用于数据安全的各个方面．以往的（ｋ，ｎ）阈值方案，计算量较大．本文提出了用赋标号降低数据扩展的优化方法，给出了一种优化后的简单（ｋ，ｎ）阈值方案论证了其安全性并分析了其数据扩展．这种方案适用于图象秘密分存等秘密数据量较大的情况.     

嵌套谓词等式系与弱互模拟

带赋值符号迁移图是一般传值进程的语义模型,其强互模拟等价可以归结为谓词等式系的最大解.该文将这一结果推广到弱互模拟等价,为此,引入嵌套谓词等式系的概念,并提出算法,将带赋值符号迁移图的弱互模拟等价归结为形如E₂μE₁的嵌套谓词等式系的最大解.     

Exact exponential-time algorithms for finding bicliques

Due to a large number of applications, bicliques of graphs have been widely considered in the literature. This paper focuses on non-induced bicliques. Given a graph G=(V,E) on n vertices, a pair (X,Y), with X,Y⊆V, X∩Y=∅, is a non-induced biclique if {x,y}∈E for any x∈X and y∈Y. The NP-complete problem of finding a non-induced (k₁,k₂)-biclique asks to decide whether G contains a non-induced biclique (X,Y) such that |X|=k₁ and |Y|=k₂. In this paper, we design a polynomial-space O(n^1.6914)-time algorithm for this problem. It is based on an algorithm for bipartite graphs that runs in time O(n^1.30052). In deriving this algorithm, we also exhibit a relation to the spare allocation problem known from memory chip fabrication. As a byproduct, we show that the constraint bipartite vertex cover problem can be solved in time O(n^1.30052).     

On the 1-fault hamiltonicity for graphs satisfying Ore's theorem and its generalization

Consider any undirected and simple graph G=(V, E), where V and E denote the vertex set and the edge set of G, respectively. Let |G|=|V|=n. The well-known Ore's theorem states that if deg_G(u)+deg_G(v)≥n+k holds for each pair of nonadjacent vertices u and v of G, then G is traceable for k=?1, hamiltonian for k=0, and hamiltonian-connected for k=1. Lin et al. generalized Ore's theorem and showed that under the same condition as above, G is r*-connected for 1≤r≤k+2 with k≥1. In this paper, we improve both theorems by showing that the hamiltonicity or r*-connectivity of any graph G satisfying the condition deg_G(u)+deg_G(v)≥n+k with k≥?1 is preserved even after one vertex or one edge is removed, unless G belongs to two exceptional families.     

Approximation Algorithms for Bounded Degree Phylogenetic Roots

The Degree- Δ Closest Phylogenetic k th Root Problem (ΔCPR _k ) is the problem of finding a (phylogenetic) tree T from a given graph G=(V,E) such that (1) the degree of each internal node in T is at least 3 and at most Δ, (2) the external nodes (i.e. leaves) of T are exactly the elements of V, and (3) the number of disagreements, i.e., |E ⊕{{u,v} : u,v are leaves of T and d _T (u,v)≤k}|, is minimized, where d _T (u,v) denotes the distance between u and v in tree T. This problem arises from theoretical studies in evolutionary biology and generalizes several important combinatorial optimization problems such as the maximum matching problem. Unfortunately, it is known to be NP-hard for all fixed constants Δ,k such that either both Δ≥3 and k≥3, or Δ>3 and k=2. This paper presents a polynomial-time 8-approximation algorithm for Δ CPR ₂ for any fixed Δ>3, a quadratic-time 12-approximation algorithm for 3CPR ₃, and a polynomial-time approximation scheme for the maximization version of Δ CPR _k for any fixed Δ and k.     

The labeled perfect matching in bipartite graphs

In this paper, we deal with both the complexity and the approximability of the labeled perfect matching problem in bipartite graphs. Given a simple graph G=(V,E) with |V|=2n vertices such that E contains a perfect matching (of size n), together with a color (or label) function , the labeled perfect matching problem consists in finding a perfect matching on G that uses a minimum or a maximum number of colors.     

Approximation Algorithms with Bounded Performance Guarantees for the Clustered Traveling Salesman Problem

Let G=(V,E) be a complete undirected graph with vertex set V , edge set E , and edge weights l(e) satisfying triangle inequality. The vertex set V is partitioned into clusters V ₁ , . . ., V _k . The clustered traveling salesman problem is to compute a shortest Hamiltonian cycle (tour) that visits all the vertices, and in which the vertices of each cluster are visited consecutively. Since this problem is a generalization of the traveling salesman problem, it is NP-hard. In this paper we consider several variants of this basic problem and provide polynomial time approximation algorithms for them. Received February 13, 1998; revised July 8, 1998.     

The k-neighbourhood-covering problem on interval graphs

Let G=(V, E) be a simple connected graph and k be a fixed positive integer. A vertex w is said to be a k-neighbourhood-cover (kNC) of an edge (u, v) if d(u, w)≤k and d(v, w)≤k. A set C ? V is called a kNC set if every edge in E is kNC by some vertices of C. The decision problem associated with this problem is NP-complete for general graphs and it remains NP-complete for chordal graphs. In this article, we design an O(n) time algorithm to solve minimum kNC problem on interval graphs by using a data structure called interval tree.     

On a single server queue with two-stage heterogeneous service and deterministic server vacations

We analyse a single server queue with Poisson arrivals, two stages of heterogeneous service with different general (arbitrary) service time distributions and binomial schedule server vacations with deterministic (constant) vacation periods. After first-stage service the server must provide the second stage service. However, after the second stage service, he may take a vacation or may decide to stay on in the system. For convenience, we designate our model as M/G ₁, G ₂/D/1 queue. We obtain steady state probability generating function of the queue length for various states of the server. Results for some particular cases of interest such as M/E_{k 1} , E_{k 2} /D/1, M/M ₁, M ₂/D/1, M/E _k /D/1 and M/G ₁, G ₂/1 have been obtained from the main results and some known results including M/E_k /1 and M/G/1 have been derived as particular cases of our particular cases.     

I/O-Efficient Algorithms for Graphs of Bounded Treewidth

We present an algorithm that takes I/Os (sort(N)=Θ((N/(DB))log  _M/B (N/B)) is the number of I/Os it takes to sort N data items) to compute a tree decomposition of width at most k, for any graph G of treewidth at most k and size N, where k is a constant. Given such a tree decomposition, we use a dynamic programming framework to solve a wide variety of problems on G in I/Os, including the single-source shortest path problem and a number of problems that are NP-hard on general graphs. The tree decomposition can also be used to obtain an optimal separator decomposition of G. We use such a decomposition to perform depth-first search in G in  I/Os. As important tools that are used in the tree decomposition algorithm, we introduce flippable DAGs and present an algorithm that computes a perfect elimination ordering of a k-tree in I/Os. The second contribution of our paper, which is of independent interest, is a general and simple framework for obtaining I/O-efficient algorithms for a number of graph problems that can be solved using greedy algorithms in internal memory. We apply this framework in order to obtain an improved algorithm for finding a maximal matching and the first deterministic I/O-efficient algorithm for finding a maximal independent set of an arbitrary graph. Both algorithms take I/Os. The maximal matching algorithm is used in the tree decomposition algorithm. An abstract of this paper was presented at the 12th Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings, pp. 89–90, 2001. Research of A. Maheshwari supported by NSERC. Part of this work was done while the second author was a Ph.D. student at the School of Computer Science of Carleton University.     

Some new sufficient conditions for graphs to have fractional k-factors

Let G be a graph, and k a positive integer. Let h: E(G)→[0, 1] be a function. If ∑ _{e? x} h(e)=k holds for any x∈V(G), then we call G[F _h ] a fractional k-factor of G with indicator function h, where F _h ={e∈E(G):h(e)>0}. In this paper, we prove some results on the existence of a fractional k-factor in a simple graph depending on δ(G) and α(G). Furthermore, we show that the results are best possible in some sense.     

Simplicial powers of graphs

In a graph, a vertex is simplicial if its neighborhood is a clique. For an integer k≥1, a graph G=(V_G,E_G) is the k-simplicial power of a graph H=(V_H,E_H) (H a root graph of G) if V_G is the set of all simplicial vertices of H, and for all distinct vertices x and y in V_G, xyE_G if and only if the distance in H between x and y is at most k. This concept generalizes k-leaf powers introduced by Nishimura, Ragde and Thilikos which were motivated by the search for underlying phylogenetic trees; k-leaf powers are the k-simplicial powers of trees. Recently, a lot of work has been done on k-leaf powers and their roots as well as on their variants phylogenetic roots and Steiner roots. For k≤5, k-leaf powers can be recognized in linear time, and for k≤4, structural characterizations are known. For k≥6, the recognition and characterization problems of k-leaf powers are still open. Since trees and block graphs (i.e., connected graphs whose blocks are cliques) have very similar metric properties, it is natural to study k-simplicial powers of block graphs. We show that leaf powers of trees and simplicial powers of block graphs are closely related, and we study simplicial powers of other graph classes containing all trees such as ptolemaic graphs and strongly chordal graphs.