Narrow Results

For a pair $u,v$ of vertices and an edge $e$ of graph $G$, we say that $u$ and $v$ can monitor $e$ if removing $e$ would change the distance between $u$ and $v$. A monitoring edge-geodetic (MEG for short) set can monitor all edges of $G$ and the minimum size of an MEG set is the monitoring edge-geodetic number and is written $\mathrm{\text{meg}}(G)$. In this paper, we obtain the MEG numbers of small world networks, hexagonal networks, hex-derived networks, enhanced mesh networks, and hexagonal star networks.

We discuss the three-dimensional Apollonian network introduced by Andrade et al.¹ for the two-dimensional case. These networks are simultaneously scale-free, small world, Euclidean, space-filling and matching graphs and have a wide range of applications going from the description of force chains in polydisperse granular packings to the geometry of fully fragmented porous media. Some of the properties of these networks, namely, the connectivity exponent, the clustering coefficient, the shortest path, and vertex betweenness are calculated and found to be particularly rich.

To accelerate the execution of advanced computing tasks, in-memory computing with resistive memory provides a promising solution. In this context, networks of memristors could be used as parallel computing medium for the solution of complex optimization problems. Lately, the solution of the shortest-path problem (SPP) in a two-dimensional memristive grid has been given wide consideration. Some still open problems in such computing approach concern the time required for the grid to reach to a steady state, and the time required to read the result, stored in the state of a subset of memristors that represent the solution. This paper presents a circuit simulation-based performance assessment of memristor networks as SPP solvers. A previous methodology was extended to support weighted directed graphs. We tried memristor device models with fundamentally different switching behavior to check their suitability for such applications and the impact on the timely detection of the solution. Furthermore, the requirement of binary vs. analog operation of memristors was evaluated. Finally, the memristor network-based computing approach was compared to known algorithmic solutions to the SPP over a large set of random graphs of different sizes and topologies. Our results contribute to the proper development of bio-inspired memristor network-based SPP solvers.

Recently a new least-squares primal-dual (LSPD) algorithm, that is impervious to degeneracy, has effectively been applied to solving linear programming problems by Barnes et al., 2002. In this paper, we show an application of LSPD to shortest path problems with nonnegative arc length is equivalent to the Dijkstra's algorithm. We also compare the LSPD algorithm with the conventional primal-dual algorithm in solving shortest path problems and show their difference due to degeneracy in solving the 1-1 shortest path problems.

Many networked systems involve multiple modes of transport. Such systems are called multimodal, and examples include logistic networks, biomedical phenomena and telecommunication networks. Existing techniques for determining minimal paths in multimodal networks have either required heuristics or else application-specific constraints to obtain tractable problems, removing the multimodal traits of the network during analysis. In this paper weighted colored-edge graphs are introduced for modeling multimodal networks, where colors represent the modes of transportation. Minimal paths are selected using a partial order that compares the weights in each color, resulting in a Pareto set of minimal paths. Although the computation of minimal paths is theoretically intractable and ${𝒩}{𝒫}$-complete, the approach is shown to be tractable through experimental analyses without the need to apply heuristics or constraints.

Breast cancer is one of the most mediated malignant diseases, because of its high incidence and prevalence, but principally due to its physical and psychological invasiveness. The study of this disease using computer science tools resorts often to the image segmentation operation. Image segmentation, although having been extensively studied, is still an open problem. Shortest path algorithms are extensively used to tackle this problem. There are, however, applications where the starting and ending positions of the shortest path need to be constrained, defining a closed contour enclosing a previously detected seed. Mass and calcification segmentation in mammograms and areola segmentation in digital images are two particular examples of interest within the field of breast cancer research. Usually the closed contour computation is addressed by transforming the image into polar coordinates, where the closed contour is transformed into an open contour between two opposite margins. In this work, after illustrating some of the limitations of this approach, we show how to compute the closed contour in the original coordinate space. After defining a directed acyclic graph appropriate for this task, we address the main difficulty in operating in the original coordinate space. Since small paths collapsing in the seed point are naturally favored, we modulate the cost of the edges to counterbalance this bias. A thorough evaluation is conducted with datasets from the breast cancer field. The algorithm is shown to be fast and reliable and suffers no loss in resolution.

The need of effective packet transmission to deliver advanced performance in wireless networks creates the need to find shortest network paths efficiently and quickly. This paper addresses a reduced uncertainty-based hybrid evolutionary algorithm (RUBHEA) to solve dynamic shortest path routing problem (DSPRP) effectively and rapidly. Genetic algorithm (GA) and particle swarm optimization (PSO) are integrated as a hybrid algorithm to find the best solution within the search space of dynamically changing networks. Both GA and PSO share context of individuals to reduce uncertainty in RUBHEA. Various regions of search space are explored and learned by RUBHEA. By employing a modified priority encoding method, each individual in both GA and PSO are represented as a potential solution for DSPRP. A complete statistical analysis has been performed to compare the performance of RUBHEA with various state-of-the-art algorithms. It shows that RUBHEA is considerably superior (reducing the failure rate by up to 50%) to similar approaches with increasing number of nodes encountered in the networks.

Due to the proliferation of online social networking, a large number of personal data are publicly available. As such, personal attacks, reputational, financial, or family losses might occur once this personal and sensitive information falls into the hands of malicious hackers. Research on Privacy-Preserving Network Publishing has attracted much attention in recent years. But most work focus on node de-identification and link protection. In academic social networks, business transaction networks, and transportation networks, etc, node identities and link structures are public knowledge but weights and shortest paths are sensitive. In this work, we study the problem of k-anonymous path privacy. A published network graph with k-anonymous path privacy has at least k indistinguishable shortest paths between the source and destination vertices [21]. In order to achieve such privacy, three different strategies of modification on edge weights of directed graphs are proposed. Numerical comparisons show that weight-proportional-based strategy is more efficient than PageRank-based and degree-based strategies. In addition, it is also more efficient and causes less information loss than running on un-directed graphs.

We address the problem of continuously transforming or morphing one simple polyline into another so that every point p of the initial polyline moves to a point q of the final polyline using the geodesic shortest path from p to q. We optimize the width of the morphing, that is, the longest path made by a point on the polyline. We present an algorithm for finding the minimum width morphing in O(n²) time using O(n) space, where n is the total number of vertices of polylines. This improves the previous algorithm⁷ by a factor of log² n.

We present a new approach, called topological peeling, for traversing a portion A_R of the arrangement formed by n lines within a convex region R on the plane. Topological peeling visits the cells of A_R in a fashion of propagating a "wave" of a special shape (called a double-wriggle curve) starting at a single source point. This special traversal fashion enables us to solve several problems (e.g., computing shortest paths) on planar arrangements to which previously best known arrangement traversal techniques such as topological sweep and topological walk may not be directly applicable. Our topological peeling algorithm takes O(K + n log(n + r)) time and O(n + r) space, where K is the number of cells in A_R and r is the number of boundary vertices of R. Comparing with topological walk, topological peeling uses a simpler and more efficient way to sweep different types of lines, and relies heavily on exploring small local structures, rather than a much larger global structure. Experiments show that, on average, topological peeling outperforms topological walk by 10–25% in execution time.

We consider the problem of continuously transforming or morphing one simple polyline into another polyline so that every point p of the initial polyline moves to a point q of the final polyline using the geodesic shortest path from p to q. The width of a morphing is defined as the longest geodesic path between corresponding points of the polylines. The optimization problem is to compute a morphing that minimizes the width. We present a linear-time algorithm for finding a morphing with width guaranteed to be at most two times the minimum width of a morphing. This improves the previous algorithm¹⁰ by a factor of log n. We develop a linear-time algorithm for computing a medial axis separator. We also show that the approximation factor is less than two for κ-straight polylines.

This paper investigates geometric and algorithmic properties of the Voronoi diagram for a transportation network on the Euclidean plane. In the presence of a transportation network, the distance is measured as the length of the shortest (time) path. In doing so, we introduce a needle, a generalized Voronoi site. We present an O(nm² + m³ + nm log n) algorithm to compute the Voronoi diagram for a transportation network on the Euclidean plane, where n is the number of given sites and m is the complexity of the given transportation network. Moreover, in the case that the roads in a transportation network have only a constant number of directions and speeds, we propose two algorithms; one needs O(nm + m² + n log n) time with O(m(n + m)) space and the other O(nm log n + m²log m) time with O(n + m) space.

An open question in Exact Geometric Computation is whether there are transcendental computations that can be made "geometrically exact". Perhaps the simplest such problem in computational geometry is that of computing the shortest obstacle-avoiding path between two points p,q in the plane, where the obstacles are a collection of n discs.

This problem can be solved in O(n²log n) time in the Real RAM model, but nothing was known about its computability in the standard (Turing) model of computation. We first give a direct proof of the Turing-computability of this problem, provided the radii of the discs are rationally related. We make the usual assumption that the numerical input data are real algebraic numbers. By appealing to effective bounds from transcendental number theory, we further show a single-exponential time upper bound when the input numbers are rational.

Our result appears to be the first example of a non-algebraic combinatorial problem which is shown computable. It is also a rare example of transcendental number theory yielding positive computational results.

A new generalized Voronoi diagram, called a boat-sail Voronoi diagram, is defined on the basis of the time necessary for a boat to reach on water surface with flow. A new concept called a boat-sail distance is introduced on the surface of water with flow, and it is used to define a generalized Voronoi diagram, in such a way that the water surface is partitioned into regions belonging to the nearest harbors with respect to this distance. The problem of computing this Voronoi diagram is reduced to a boundary value problem of a partial differential equation, and a numerical method for solving this problem is constructed. The method is a modification of a so-called fast marching method originally proposed for the eikonal equation. Computational experiments show the efficiency and the stableness of the proposal method. We also apply our equation to the shortest path problem and the simulation of the forest fire.

Many algorithms for applications such as pattern recognition, computer vision, and computer graphics seek to compute actual optimal paths in weighted directed graphs. The standard approach for reporting an actual optimal path is based on building a single-source optimal path tree. A technique by Chen et al.² was given for a class of problems such that a single actual optimal path can be reported without maintaining any single-source optimal path tree, thus significantly reducing the space bound of those problems with no or little increase in their running time. In this paper, we extend the technique by Chen et al.² to the generalized problem of reporting many actual optimal paths with different starting and ending vertices in certain directed graphs, and show how this new technique yields improved results on several application problems, such as reconstructing a 3-D surface band bounded by two simple closed curves, finding various constrained segmentation of 2-D medical images, and circular string-to-string correction. We also correct an error in the time/space complexity for the well-cited circular string-to-string correction algorithm¹² and give an improved result for this problem. Although the generalized many-path problem seems more difficult than the single-path cases, our algorithms have nearly the same space and time bounds as those of the single-path cases. Our technique is likely to help improve many other optimal paths or dynamic programming algorithms.

We study a problem about shortest paths in Delaunay triangulations. Given two nodes s, t in the Delaunay triangulation of a point set S, we look for a new point p ∉ S that can be added, such that the shortest path from s to t, in the Delaunay triangulation of S∪{p}, improves as much as possible. We study several properties of the problem, and give efficient algorithms to find such a point when the graph-distance used is Euclidean and for the link-distance. Several other variations of the problem are also discussed.

A path P between two points s and t in a polygonal subdivision with obstacles and weighted regions defines a class of paths that can be deformed to P without passing over any obstacle. We present the first algorithm that, given P and a relative error tolerance ε ϵ (0, 1), computes a path from this class with cost at most 1 + ε times the optimum. The running time is , where k is the number of segments in P and h and n are the numbers of obstacles and vertices in , respectively. The constant in the running time of our algorithm depends on some geometric parameters and the ratio of the maximum region weight to the minimum region weight.

CAT(0) metric spaces and hyperbolic spaces play an important role in combinatorial and geometric group theory. In this paper, we present efficient algorithms for distance problems in CAT(0) planar complexes. First of all, we present an algorithm for answering single-point distance queries in a CAT(0) planar complex. Namely, we show that for a CAT(0) planar complex with n vertices, one can construct in O(n²log n) time a data structure of size O(n²) so that, given a point , the shortest path γ(x, y) between x and the query point y can be computed in linear time. Our second algorithm computes the convex hull of a finite set of points in a CAT(0) planar complex. This algorithm is based on Toussaint's algorithm for computing the convex hull of a finite set of points in a simple polygon and it constructs the convex hull of a set of k points in O(n²log n + nk log k) time, using a data structure of size O(n² + k).

Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the input polygon, the intrinsic complexity of the problems these algorithms solve is often related to the reflex vertices of the polygon. In this paper, we give an easy-to-describe linear-time method to replace an input polygon by a polygon such that (1) contains , (2) has its reflex vertices at the same positions as , and (3) the number of vertices of is linear in the number of reflex vertices. Since the solutions of numerous problems on polygons (including shortest paths, geodesic hulls, separating point sets, and Voronoi diagrams) are equivalent for both and , our algorithm can be used as a preprocessing step for several algorithms and makes their running time dependent on the number of reflex vertices rather than on the size of . We describe several of these applications (including linear-time post-processing steps that might be necessary).

We propose an algorithm for finding a $(1+𝜀)$-approximate shortest path through a weighted 3D simplicial complex ${𝒯}$. The weights are integers from the range $[1,W]$ and the vertices have integral coordinates. Let $N$ be the largest vertex coordinate magnitude, and let $n$ be the number of tetrahedra in ${𝒯}$. Let $\rho$ be some arbitrary constant. Let $\kappa$ be the size of the largest connected component of tetrahedra whose aspect ratios exceed $\rho$. There exists a constant $C$ dependent on $\rho$ but independent of ${𝒯}$ such that if $\kappa \le \frac{1}{C}loglogn+O(1)$, the running time of our algorithm is polynomial in $n$, $1/𝜀$ and $log(NW)$. If $\kappa =O(1)$, the running time reduces to $O(n{𝜀}^{-O(1)}{(log(NW))}^{O(1)})$.