Computing the Degree-4 Shortest Network under a Given Topology

Let F be a set of n (n being an even number) fixed points and let M be a set of n / 2 -1 moving points, whose locations are to be determined, in the plane. A topology is a set of edges connecting these points in the set V=Fcup M . Let E be a full 4-degree Steiner topology; i.e., the topology forms a tree which contains fixed points of degree 1 and moving points of degree 4, and let H(E) be a set of topologies which include E and its degeneracies. We define a canonical tree over V as one whose topology belongs to H(E) and in which the sum of two adjacent angles around any node is not less than π . In this paper we prove that if a canonical tree exists, then it is the shortest (degree-4) network under a given topology E . We present an O(n ² ) time algorithm for finding a degree-4 shortest network whose topology belongs to H(E) . Received November 16, 1998.     

Optimally Computing the Shortest Weakly Visible Subedge of a Simple Polygon

Given ann-vertex simple polygonP, the problem of computing the shortest weakly visible subedge ofPis that of finding a shortest line segmentson the boundary ofPsuch thatPis weakly visible froms(ifsexists). In this paper, we present new geometric observations that are useful for solving this problem. Based on these geometric observations, we obtain optimal sequential and parallel algorithms for solving this problem. Our sequential algorithm runs inO(n) time, and our parallel algorithm runs inO(log n) time usingO(n/log n) processors in the CREW PRAM computational model. Using the previously best known sequential algorithms to solve this problem would takeO(n²) time. We also give geometric observations that lead to extremely simple and optimal algorithms for solving, both sequentially and in parallel, the case of this problem where the polygons are rectilinear.     

An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains

We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain $\mathcal D $ D , consisting of $n$ n tetrahedra with positive weights, and a real number $\varepsilon \in (0,1)$ ε ∈ ( 0 , 1 ) , our algorithm constructs paths in $\mathcal D $ D from a fixed source vertex to all vertices of $\mathcal D $ D , the costs of which are at most $1+\varepsilon $ 1 + ε times the costs of (weighted) shortest paths, in $O(\mathcal{C }(\mathcal D )\frac{n}{\varepsilon ^{2.5}}\log \frac{n}{\varepsilon }\log ^3\frac{1}{\varepsilon })$ O ( C ( D ) n ε 2.5 log n ε log 3 1 ε ) time, where $\mathcal{C }(\mathcal D )$ C ( D ) is a geometric parameter related to the aspect ratios of tetrahedra. The efficiency of the proposed algorithm is based on an in-depth study of the local behavior of geodesic paths and additive Voronoi diagrams in weighted three-dimensional domains, which are of independent interest. The paper extends the results of Aleksandrov et al. (J ACM 52(1):25–53, 2005), to three dimensions.     

Shortest Paths with Shortest Detours

This paper is concerned with a biobjective routing problem, called the shortest path with shortest detour problem, in which the length of a route is minimized as one criterion and, as second, the maximal length of a detour route if the chosen route is blocked is minimized. Furthermore, the relation to robust optimization is pointed out, and we present a new polynomial time algorithm, which computes a minimal complete set of efficient paths for the shortest path with shortest detour problem. Moreover, we show that the number of nondominated points is bounded by the number of arcs in the graph.     

基于全局可达点的中国教育网平均最短路径近似算法

平均最短路径长度是复杂网络的一个重要特性,但由于计算时间的限制,求解大规模网络的平均最短路径长度很困难.以中国教育网数据为例,分析了中国教育网的拓扑结构,提出了全局可达点和局部可达点的概念,发现整个网络的平均最短路径长度由全局可达点决定.通过分析全局可达点的平均单源最短路径长度分布,发现整个网络的平均最短路径长度可由少数随机选取的点的平均最短路径长度来近似.通过三个网络验证了近似计算方法的有效性,并通过随机选取的数百个点,计算得到了含49041472个点的中国教育网的平均最短路径长度在14-15之间.     

Shortest billiard trajectories

In this paper we prove that any convex body of the d-dimensional Euclidean space (d ≥ 2) possesses at least one shortest generalized billiard trajectory moreover, any of its shortest generalized billiard trajectories is of period at most d + 1. Actually, in the Euclidean plane we improve this theorem as follows. A disk-polygon with parameter r > 0 is simply the intersection of finitely many (closed) circular disks of radii r, called generating disks, having some interior point in common in the Euclidean plane. Also, we say that a disk-polygon with parameter r > 0 is a fat disk-polygon if the pairwise distances between the centers of its generating disks are at most r. We prove that any of the shortest generalized billiard trajectories of an arbitrary fat disk-polygon is a 2-periodic one. Also, we give a proof of the analogue result for ε-rounded disk-polygons obtained from fat disk-polygons by rounding them off using circular disks of radii ε > 0. Our theorems give partial answers to the very recent question raised by S. Zelditch on characterizing convex bodies whose shortest periodic billiard trajectories are of period 2. K. Bezdek partially supported by a Natural Sciences and Engineering Research Council of Canada Discovery Grant.     

Shortest path games

We study cooperative games that arise from the problem of finding shortest paths from a specified source to all other nodes in a network. Such networks model, among other things, efficient development of a commuter rail system for a growing metropolitan area. We motivate and define these games and provide reasonable conditions for the corresponding rail application. We show that the core of a shortest path game is nonempty and satisfies the given conditions, but that the Shapley value for these games may lie outside the core. However, we show that the shortest path game is convex for the special case of tree networks, and we provide a simple, polynomial time formula for the Shapley value in this case. In addition, we extend our tree results to the case where users of the network travel to nodes other than the source. Finally, we provide a necessary and sufficient condition for shortest paths to remain optimal in dynamic shortest path games, where nodes are added to the network sequentially over time.     

最短区间估计问题研究

给出了正态分布总体及指数分布总体在给定置信水平下参数的最短区间估计.为便于实际工作者的应用,文章给出了计算用表.     

Shortest Inspection Curves for the Sphere

What is the form of the shortest curve C going outside the unit sphere S in ?³ such that passing along C we can see all points of S from outside? How will the form of C change if we require that C has one (or both) of its endpoints on S? A solution to the latter problem also answers the following question. You are in a half-space at a unit distance from the boundary plane P, but you do not know where P is. What is the shortest space curve C such that going along C you will certainly come to P? Geometric arguments suggest that the required curves should be looked for in certain classes depending on several parameters. A computer-aided analysis yields the best curves in the classes. Some other questions are solved in a similar way. Bibliography: 4 titles.     

最短路的灵敏度分析

最短路的灵敏度分析就是讨论当网络中边的权值发生波动时，对目前的最短路带来的影响，本讨论了网络中边的权值在何种范围的变化时，极小最短路子网络不发生变化。     

具有最大能量的最短路

本文讨论一类新的赋权图 ,称为双权图 ,G=( V,E;w,c) ,w称为权函数 ,c为容量函数 .并给出了 G中两顶点 u与 v之间具有最大能量的最短路的算法 .     

Shortest string containing all permutations

In this paper, we consider the problem of constructing a shortest string of {1,2,…,n} containing all permutations on n elements as subsequences. For example, the string 1 2 1 3 1 2 1 contains the 6 (=3!) permutations of {1,2,3} and no string with less than 7 digits contains all the six permutations. Note that a given permutation, such as 1 2 3, does not have to be consecutive but must be from left to right in the string.We shall first give a rule for constructing a string of {1,2,…,n} of infinite length and the show that the leftmost n²?2n+4 digits of the string contain all the n! permutations (for n≥3). We conjecture that the number of digits f(n) = n²?2n+4 (for n≥3) is the minimum.Then we study a new function F(n,k) which is the minimum number of digits required for a string of n digits to contain all permutations of i digits, i≤k. We conjecture that F(n,k) = k(n?1) for 4≤k ≤n?1.     

Shortest paths with ordinal weights

We investigate the single-source-single-destination “shortest” path problem in directed, acyclic graphs with ordinal weighted arc costs. We define the concepts of ordinal dominance and efficiency for paths and their associated ordinal levels, respectively. Further, we show that the number of ordinally non-dominated path vectors from the source node to every other node in the graph is polynomially bounded and we propose a polynomial time labeling algorithm for solving the problem of finding the set of ordinally non-dominated path vectors from source to sink.     

On the Hardness of Equal Shortest Path Routing

In telecommunication networks packets are carried from a source s to a destination t on a path that is determined by the underlying routing protocol. Most routing protocols belong to the class of shortest path routing protocols. In such protocols, the network operator assigns a length to each link. A packet going from s to t follows a shortest path according to these lengths. For better protection and efficiency, one wishes to use multiple (shortest) paths between two nodes. Therefore the routing protocol must determine how the traffic from s to t is distributed among the shortest paths. In the protocol called OSPF-ECMP (for Open Shortest Path First-Equal Cost Multiple Path) the traffic incoming at every node is uniformly balanced on all outgoing links that are on shortest paths. In that context, the operator task is to determine the “best” link lengths, toward a goal such as maximizing the network throughput for given link capacities.In this work, we show that the problem of maximizing even a single commodity flow for the OSPF-ECMP protocol cannot be approximated within any constant factor ratio. Besides this main theorem, we derive some positive results which include polynomial-time approximations and an exponential-time exact algorithm. We also prove that despite their weakness, our approximation and exact algorithms are, in a sense, the best possible.     

Shortest string containing all permutations

In this paper we have constructed strings of 1,2,…,n of lenghts n²?2n+4, n?3, which contain all the n! permutations as subsequences. We have shown that all the strings constructed earlier in [2] and [4] can be obtained from our construction as particular cases. Moreover our proofs that the strings so constructed give all the n! permutations. Contribute new techniques and insights.     

最短距离与费马点

本文讨论到两个定点和一条定直线距离之和最短问题,证明了该点的存在性并给出该点的具体做法.     

Shortest curves on convex hypersurfaces

We give a survey of results of the author on the geometry of geodesics and shortest curves on general convex hypersurfaces in spaces with constant curvature. We present qualitatively new theorems, which unite and generalize the main classical results; we give applications to the solution of a number of actual problems of geometry of convex surfaces in the large. We give generalizations of some well-known theorems on geodesics and shortest curves to Riemannian manifolds and nonregular multidimensional convex metrics.Translated from Itogi Nauki i Tekhniki, Seriya Problemy Geometrii, Vol. 16, pp. 155–194, 1984.     

Solving the Shortest Path Problem with Interval Arcs

This paper presents an algorithm for the shortest path problem when the connected arcs in a transportation network are represented as interval numbers. The methodology proposed in this paper considers fuzzy preference ordering of intervals (Sengupta and Pal (2000), European Journal of Operational Research 127, 28–43) from pessimistic and optimistic decision maker’s point of view.