On the core of cost-revenue games: Minimum cost spanning tree games with revenues

In this paper, we analyze cost sharing problems arising from a general service by explicitly taking into account the generated revenues. To this cost-revenue sharing problem, we associate a cooperative game with transferable utility, called cost-revenue game. By considering cooperation among the agents using the general service, the value of a coalition is defined as the maximum net revenues that the coalition may obtain by means of cooperation. As a result, a coalition may profit from not allowing all its members to get the service that generates the revenues. We focus on the study of the core of cost-revenue games. Under the assumption that cooperation among the members of the grand coalition grants the use of the service under consideration to all its members, it is shown that a cost-revenue game has a nonempty core for any vector of revenues if, and only if, the dual game of the cost game has a large core. Using this result, we investigate minimum cost spanning tree games with revenues. We show that if every connection cost can take only two values (low or high cost), then, the corresponding minimum cost spanning tree game with revenues has a nonempty core. Furthermore, we provide an example of a minimum cost spanning tree game with revenues with an empty core where every connection cost can take only one of three values (low, medium, or high cost).     

Efficient exponential-time algorithms for edit distance between unordered trees

The edit distance problem for rooted unordered trees is known to be NP-hard. Based on this fact, this paper studies exponential-time algorithms for the problem. For a general case, an $O(\min ({1.26}^{n_1+n_2},2^{b_1+b_2}\cdot \text{<mi mathvariant="italic" is="true">poly</mi>}(n_1,n_2)))$ time algorithm is presented, where $n_1$ and $n_2$ are the numbers of nodes and $b_1$ and $b_2$ are the numbers of branching nodes in two input trees. This algorithm is obtained by a combination of dynamic programming, exhaustive search, and maximum weighted bipartite matching. For bounded degree trees over a fixed alphabet, it is shown that the problem can be solved in $O({(1+ϵ)}^{n_1+n_2})$ time for any fixed $ϵ>0$. This result is achieved by avoiding duplicate calculations for identical subsets of small subtrees.     

Possibilistic sequential decision making

When the information about uncertainty cannot be quantified in a simple, probabilistic way, the topic of possibilistic decision theory is often a natural one to consider. The development of possibilistic decision theory has lead to the proposition a series of possibilistic criteria, namely: optimistic and pessimistic possibilistic qualitative criteria [7], possibilistic likely dominance [2], [9], binary possibilistic utility [11] and possibilistic Choquet integrals [24]. This paper focuses on sequential decision making in possibilistic decision trees. It proposes a theoretical study on the complexity of the problem of finding an optimal strategy depending on the monotonicity property of the optimization criteria – when the criterion is transitive, this property indeed allows a polytime solving of the problem by Dynamic Programming. We show that most possibilistic decision criteria, but possibilistic Choquet integrals, satisfy monotonicity and that the corresponding optimization problems can be solved in polynomial time by Dynamic Programming. Concerning the possibilistic likely dominance criteria which is quasi-transitive but not fully transitive, we propose an extended version of Dynamic Programming which remains polynomial in the size of the decision tree. We also show that for the particular case of possibilistic Choquet integrals, the problem of finding an optimal strategy is NP-hard. It can be solved by a Branch and Bound algorithm. Experiments show that even not necessarily optimal, the strategies built by Dynamic Programming are generally very good.     

关于树上连续状态马氏泛函的一类强偏差定理

强偏差定理一直是国际概率论界研究的中心课题之一.通过构造适当的非负鞅,将Doob鞅收敛定理应用于几乎处处收敛的研究,给出了一类特殊非齐次树上连续状态马氏泛函的若干强偏差定理.     

k-分支星状树的第二几何算术指标

数学化学中,第二几何算术指标是新近提出的一个图的拓扑指标,它与Szeged指标和点PI指标具有紧密关系.如果树的一个顶点υ的度大于等于3,则称顶点υ是其一个分支点.通过树的第二几何算术指标的一个增加或减少的变换,刻画了k-分支星状树的第二几何算术指标的最值,同时确定了相应的极图.     

微蜂窝环境中无线接收信号的特性分析

以微蜂窝系统为背景,研究了以测试射线法和虚拟源射线跟踪法为代表的射线跟踪技术,并用这两种方法对射线跟踪进行建模,分析比较两种模型的优缺点.利用这两种模型对实际情况进行计算,精确地找出所有给定情况的传播路径并可视化;对多波干涉的振幅进行了统计学分析,对宽带多波干涉现象进行了数学建模,并分析了合成波的包络统计特性.     

List Edge‐Coloring and Total Coloring in Graphs of Low Treewidth

We prove that the list chromatic index of a graph of maximum degree Δ and treewidth is Δ; and that the total chromatic number of a graph of maximum degree Δ and treewidth is . This improves results by Meeks and Scott.     

The non-approximability of bicriteria network design problems

Let G be an undirected graph with two edge costs (c-cost and d-cost). We want to minimize the diameter of a spanning subgraph S (under d-cost) subject to the constraint that the total cost of the edges in S (with respect to c) does not exceed a given budget. We prove that this problem is non-approximable, even in some special cases. Similar results are proved if the stretch factor or the root stretch factor is considered instead of the diameter.     

路或圈的笛卡尔乘积图的支撑树数

设G是路或圈的笛卡尔乘积图，t(G)表示G的支撑树数.该文借助于第二类Chebyshev多项式给出t(G)的公式，并考虑了t(G)的线性递归关系及渐近性态.