Minimum Global Height支撑树及相关问题

本文研究了两个组合优化问题:minimum g1obal height支撑树和minimum aveageheight支撑树问题.利用3SAT问题的时间复杂性,本文证明了这两个问题都是NP-hard的,并分别给出了一个算法,即（mgh）-算法和（mah）-算法.在非负网络中,这两个算法的时间复杂性都为O（n3）.利用第一个问题的复杂性,本文证明了minimum height支撑树问题也是NP-hard的,从而纠正了有关文献中的一个错误结论.     

Minimal spanning trees

The main result is that a recursive weighted graph having a minimal spanning tree has a minimal spanning tree that is . This leads to a proof of the failure of a conjecture of Clote and Hirst (1998) concerning Reverse Mathematics and minimal spanning trees.

     

Spanning Trees on the Sierpinski Gasket

We present the numbers of spanning trees on the Sierpinski gasket SG _d (n) at stage n with dimension d equal to two, three and four. The general expression for the number of spanning trees on SG _d (n) with arbitrary d is conjectured. The numbers of spanning trees on the generalized Sierpinski gasket SG _d,b (n) with d = 2 and b = 3,4 are also obtained.     

An Application of Multiple Comparison Techniques to Model Selection

Akaike's information criterion (AIC) is widely used to estimate the best model from a given candidate set of parameterized probabilistic models. In this paper, considering the sampling error of AIC, a set of good models is constructed rather than choosing a single model. This set is called a confidence set of models, which includes the minimum {AIC} model at an error rate smaller than the specified significance level. The result is given as P-value for each model, from which the confidence set is immediately obtained. A variant of Gupta's subset selection procedure is devised, in which a standardized difference of AIC is calculated for every pair of models. The critical constants are computed by the Monte-Carlo method, where the asymptotic normal approximation of AIC is used. The proposed method neither requires the full model nor assumes a hierarchical structure of models, and it has higher power than similar existing methods.     

关于一类新型权函数Aλ3γ(λ1,λ2;E)的性质

Aλ3γ (λ1,λ2;E)-权函数是一类广义的权函数,可视为许多经典权函数的推广.文中给出了关于Aλ3γ(λ1,λ2;E)-权的和与积的运算性质,并进而证明了Aλ3γ(λ1,λ2;E)-权函数的两个充要条件.     

Lie superderivations of superalgebras

The aim of this paper is to investigate Lie superderivations of superalgebras, using the theory of functional identities in superalgebras. As a consequence, we obtain a definitive result on Lie superderivations of prime superalgebras.     

Linear extensions of orderings

A construction is given which makes it possible to find all linear extensions of a given ordered set and, conversely, to find all orderings on a given set with a prescribed linear extension. Further, dense subsets of ordered sets are studied and a procedure is presented which extends a linear extension constructed on a dense subset to the whole set.     

Being a Proper Trapezoid Ordered Set Is a Comparability Invariant

It is proved that if we replace an autonomous subset of a finite proper trapezoid ordered set with a proper trapezoid ordered set, then we obtain a proper trapezoid ordered set provided the autonomous subset is not an antichain, and analogously in the k-dimensional case. As corollaries we obtain that being a proper trapezoid ordered set is a comparability invariant, more generally, proper interval dimension is a comparability invariant.     

关于奇异的非线性椭圆型方程正的整体解的存在性

本文建立一类奇异的非线性椭圆型方程正的整体解的存在定理，并给出解在无穷远的增长性质，推广了文［１］的结果。     

Tight Bounds for Connecting Sites Across Barriers

Given m points (sites) and n obstacles (barriers) in the plane, we address the problem of finding a straight line minimum cost spanning tree on the sites, where the cost is proportional to the number of intersections (crossings) between tree edges and barriers. If the barriers are infinite lines, it is known that there is a spanning tree such that every barrier is crossed by tree edges, and this bound is asymptotically optimal. Asano et al. showed that if the barriers are pairwise disjoint line segments, then there is a spanning tree such that every barrier crosses at most 4 tree edges and so the total cost is at most 4n. Lower bound constructions are known with 3 crossings per barrier and 2n total cost. We obtain tight bounds on the minimum cost of spanning trees in the special case where the barriers are interior disjoint line segments that form a convex subdivision of the plane and there is a point in every cell of the subdivision. In particular, we show that there is a spanning tree such that every barrier crosses at most 2 tree edges, and there is a spanning tree of total cost 5n/3. Both bounds are the best possible. Work by Eynat Rafalin and Diane Souvaine was supported by the National Science Foundation under Grant #CCF-0431027. E. Rafalin’s research conducted while at Tufts University.