Stereology of tubular structures

The morphology of a tubular structure can be characterized, in at least some of its important respects, through stereological methods. We study the geometric meaning of standard stereological quantities when applied to tubular structures, with particular regard to their curvature or tortuosity. Measures defined specifically in relation to tubular structures are also introduced for practical use. The ideal smooth bent cylinder, used here, is not realistic but provides general principles from which a more specialized investigation should be developed. The emphasis is placed on simple counting methods of measurement, specifically the tangent counts introduced by DeHoff, and counts of section profiles exhibiting a particular character (such as ‘figure-eights’). These measures convey information about the tortuosity of tubular structures, whereas the standard indices V_v, S_v, M_v give no information about tortuosity. Some data from human testicular tubules are discussed.     

基于关键节点和多播节点的多播路由算法

在视频会议等多播应用中，降低多播树网络费用非常重要。本文提出了基于关键节点和目的节点的多播路由KDDMC算法。由于在算法中优先考虑采用关键节点，实现更多链路的共享，从而降低网络费用。在随机网络上的仿真结果表明，KDDMC算法的多播树网络费用优于SPH算法。同时证明了KDDMC算法的复杂度为O(n^3)，且利用所提出的路由表算法易于分布式实现。     

Optimal multicast routing with quality of service constraints

We consider the problem of optimal multicast routing with Quality of Service constraints motivated by the requirements of interactive continuous media communication, e.g., real-time teleconferencing. We concentrate on distributed algorithms for determining a tree over the network topology, rooted at the source and spanning the intended destinations. Quality of Service requirements for interactive continuous media typically impose constraints on some metric over the individual paths from the source to each destination, usually in the form of an upper bound on the delay. Thus, we focus on the problem of minimizing the cost of the tree while at the same time satisfying a common constraint over individual source-destination paths. We have shown that this problem is intractable, but have also devised centralized polynomial time heuristics that perform well. Here we present distributed algorithms to minimize tree cost while satisfying the constraints on the paths from the source to each destination.     

Digital Steiner sets and Matheron semi-groups

There are various ways to define digital convexity in Zⁿ$Z^n$. The proposed approach focuses on structuring elements (and not the sets under study), whose digital versions should allow to construct hierarchies of operators satisfying Matheron semi-groups law _γλγμ=_γmax(λ,_μ)${\gamma }_{\lambda }{\gamma }_{\mu }={\gamma }_{\max (\lambda \text{,}\mu )}$, where λ$\lambda$ is a size factor. In Rⁿ$R^n$ the convenient class is the Steiner one. Its elements are Minkowski sums of segments. We prove that it admits a digital equivalent when the segments of Zⁿ$Z^n$ are Bezout. The conditions under which the Steiner sets are convex in Zⁿ$Z^n$, and are connected, are established. The approach is then extended to structuring elements that vary according to the law of perspective, and also to anamorphoses, so that the digital Steiner class and its properties can extend to digital spaces as a sphere or a torus.     

Wireless network design via 3-decompositions

We consider some network design problems with applications for wireless networks. The input for these problems is a metric space (X,d) and a finite subset UX of terminals. In the Steiner Tree with Minimum Number of Steiner Points (STMSP) problem, the goal is to find a minimum size set SX−U of points so that the unit-disc graph of S+U is connected. Let Δ be the smallest integer so that for any finite VX for which the unit-disc graph is connected, this graph contains a spanning tree with maximum degree Δ. The best known approximation ratio for STMSP was Δ−1 [I.I. Măndoiu, A.Z. Zelikovsky, A note on the MST heuristic for bounded edge-length Steiner trees with minimum number of Steiner points, Information Processing Letters 75 (4) (2000) 165–167]. We improve this ratio to (Δ+1)/2+1+ε.In the Minimum Power Spanning Tree (MPST) problem, V=X is finite, and the goal is to find a “range assignment” on the nodes so that the edge set contains a spanning tree, and ∑_vVp(v) is minimized. We consider a particular case {0,1}-MPST of MPST when the distances are in {0,1}; here the goal is to find a minimum size set SV of “active” nodes so that the graph (V,E₀+E₁(S)) is connected, where , and E₁(S) is the set the edges in with both endpoints in S. We will show that the (5/3+ε)-approximation scheme for MPST of [E. Althaus, G. Calinescu, I. Măndoiu, S. Prasad, N. Tchervenski, A. Zelikovsky, Power efficient range assignment for symmetric connectivity in static ad hoc wireless networks, Wireless Networks 12 (3) (2006) 287–299] achieves a ratio 3/2 for {0,1}-distances. This answers an open question posed in [E. Lloyd, R. Liu, S. Ravi, Approximating the minimum number of maximum power users in ad hoc networks, Mobile Networks and Applications 11 (2006) 129–142].     

Non-Cooperative Tree Creation

In this paper we consider the connection game, a simple network design game with independent selfish agents that was introduced by Anshelevich et al. (Proc. 35th Ann. ACM Symp. Theo. Comp. (STOC), pp. 511–520, 2003). Our study concerns an important subclass of tree games, in which every feasible network is guaranteed to be connected. It generalizes the class of single-source games considered by Anshelevich et al. We focus on the existence, quality, and computability of pure-strategy exact and approximate Nash equilibria. For tree connection games, in which every player holds two terminals, we show that there is a Nash equilibrium as cheap as the optimum network. In contrast, for single-source games, in which every player has at most three terminals, the price of stability is at least k−2, and it is -complete to decide the existence of a Nash equilibrium. Hence, we propose polynomial time algorithms for computing approximate Nash equilibria, which provide relaxed stability and cost efficiency guarantees. For the case of two terminals per player, there is an algorithm to find a (2+ε,1.55)-approximate Nash equilibrium. It can be generalized to an algorithm to find a (3.1+ε,1.55)-approximate Nash equilibrium for general tree connection games. This improves the guarantee of the only previous algorithm for the problem, which returns a (4.65+ε,1.55)-approximate Nash equilibrium. Tightness results for the analysis of all algorithms are derived. Our algorithms use a novel iteration technique for trees that might be of independent interest. This work has appeared in part as an extended abstract at the 31st Symposium on Mathematical Foundations of Computer Science (MFCS 2006) and the 17th International Symposium on Algorithms and Computation (ISAAC 2006). Supported by DFG Research Training Group 1042 “Explorative Analysis and Visualization of Large Information Spaces”.     

An efficient distributed algorithm for generating and updating multicast trees

As group applications are becoming widespread, efficient network utilization becomes a growing concern. Multicast transmission represents a necessary lower network service for the wide diffusion of new multimedia network applications. Multicast transmission may use network resources more efficiently than multiple point-to-point messages; however, creating optimal multicast trees (Steiner Tree Problem in networks) is prohibitively expensive. This paper proposes a distributed algorithm for the heuristic solution of the Steiner Tree Problem, allowing the construction of effective distribution trees using a coordination protocol among the network nodes. Furthermore, we propose a novel distributed technique for dynamically updating the multicast tree. The approach proposed has been implemented and extensively tested both in simulation, and on experimental networks. Performance evaluation indicates that the distributed algorithm performs as well as the centralized version, providing good levels of convergence time and communication complexity.     

基于CBT的多源Steiner树构造算法

构造最小代价树问题可形式化为图论中Steiner树问题。而Steiner树的求解已经被证明是一个NP-complete问题，不可能在多项式时间求得其精确解，所以出现许多启发式算法：在可接受时间内，得到一棵近似的最优多播树。这些算法一般先指定所有链接边的费用，通过一定方法或规则，找出包含源端和所有目的端的一棵近似最优的多播树。很显然，它们并没有考虑由于路径的共享重叠而引起最小生成树链接边费用的变化。现利用CBT算法思想对变化的费用进行建模并对典型启发式算法作了改进，以适应不断变化了的链路费用。     

低代价最短路径树快速算法的时间复杂度研究

低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗.快速低代价最短路径树算法FLSPT是在DDSP算法的基础上,通过改进节点的搜索过程,该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP,其时间复杂度为O(nlog n e).FLSPT是利用Fibonacci堆来选择图中未计算点的最小值来计算时间复杂度的.通过对FLSPT的程序和Fibonacci堆的分析发现,用O(log(n!) e)来表示FLSPT算法的时间复杂度比文献[6]中分析的O(nlog(n) e)更能体现FLSPT算法高效率.     

基于蚁群算法的QoS多播路由优化策略

对QoS多播路由和约束最小Steiner多播树进行了分析,提出了基于蚁群算法搜索约束最小Steiner多播树的ACMC算法,并与DDMC算法进行了实验比较.结果表明,在同样环境和多播组规模的条件下,ACMC算法花费的网络代价小于DDMC算法,从而验证了ACMC算法的有效性和可行性.