Search

During the past years, network dynamics has been widely investigated in various disciplines. As a practical and convenient description for social networks, signed networks have also garnered significant attention. In this work, we study information spreading with relative attributes on signed networks, where edges are assigned positive or negative labels, describing friendly or hostile relationships. We define the attribute of information by a degree that can be either ‘good’ or ‘bad’ and assume that the spreading willingness of the information receiver depends on not only its relation with others but also the attribute of information. A pair-wise potential relation identification algorithm is designed based on the shortest path approach and structural balance theory. Both simulations on randomly signed networks and empirical experiments on real datasets show that the proposed information spreading could be approximately investigated within a local 2-order neighborhood. In addition, the ratio of potential friendly nodes with a target node is consist with network content. Finally, the propagation speed of ‘good’ information would unexpectedly slow down when the ratio of positive edges is larger than an estimated threshold. The presented model could be referred to in real social scenarios, such as product promotion, advertisement media, and rumor mongering.

The single-pair all-shortest-path problem is to find all possible shortest paths, given a single source-destination pair in a graph. Due to the lack of efficient algorithms for single-pair all-shortest-path problem, many applications used diverse types of modifications to the existing shortest-path algorithms such as Dijkstra’s algorithm. Such approaches can facilitate the analysis of medium-sized static networks, but the heavy computational cost impedes their use for massive and dynamic real-world networks. In this paper, we present a novel single-pair all-shortest-path algorithm, which performs well on massive networks as well as dynamic networks. The efficiency of our algorithm stems from novel 2-hop label-based query processing on large-size networks. For dynamic networks, we also demonstrate how to incrementally maintain all shortest paths in 2-hop labels, which allows our algorithm to handle the topological changes of dynamic networks such as insertion or deletion of edges. We carried out experiments on real-world large datasets, and the results confirms the effectiveness of our algorithms for the single-pair all-shortest-path computation and the incremental maintenance of 2-hop labels.

The Shortest Path in networks is an important problem incombinatorial optimization and has many applications in areas like telecommunications and transportation. It is known that this problem is easy to solve in its classic deterministic version, but it is also known that it is an NP-Hard problem for several generalizations. The Shortest Path Problem consists in finding a simple path connecting a source node and a terminal node in an arc-weighted directed network. In some real-world situations the weights are not completely known and then this problem is transformed into an optimization one under uncertainty. It is assumed that an interval estimate is given for each arc length and no further information about the statistical distribution of the weights is known. Uncertainty has been modeled in different ways in optimization. Our aim in this paper is to study the Minmax Regret path with interval data problem by presenting a new exact branch and cut algorithm and, additionally, new heuristics. A set of difficult and large size instances are defined and computational experiments are conducted for the analysis of the different approaches designed to solve the problem. The main contribution of our paper is to provide an assessment of the performance of the proposed algorithms and an empirical evidence of the superiority of a simulated annealing approach based on a new neighborhood over the other heuristics proposed.

With the fast development of social networks, privacy protection on social network data has already attracted more and more research attention. If an adversary has collected enough information by intentionally querying a social network, the privacy of social network data might be successfully inferred based on the previous query results, which is seldom investigated by most existing approaches. In this paper, we first formulate the correlated query results as the non-zero prior knowledge, then propose a novel differential privacy approach to enhance privacy of social network data from being inferred. The corresponding c-difference is re-formulated as well as the calculation of the sensitivity between two "neighboring" social graphs. Particularly, the calculation of sensitivity is proposed for three widely adopted queries on social networks, i.e., node degree distribution query, cut set query and the shortest path query. To evaluate our approach, rigorous experiments have been performed on three real world data sets. The promising experimental results have demonstrated that the proposed approach is superior to the state-of-the-art privacy protection approaches with respect to data privacy and data utility. (C) 2018 Elsevier Inc. All rights reserved.

Map matching is the process of matching a series of recorded geographic coordinates (e.g., a GPS trajectory) to a road network. Due to GPS positioning errors and the sampling constraints, the GPS data collected by the GPS devices are not precise, and the location of a user cannot always be correctly shown on the map. Therefore, map matching is an important preprocessing step for many applications such as navigation systems, traffic flow analysis, and autonomous cars. Unfortunately, most current map-matching algorithms only consider the distance between the GPS points and the road segments, the topology of the road network, and the speed constraint of the road segment to determine the matching results. Moreover, most current map-matching algorithms cannot handle the matching errors at junctions. In this paper, we propose a spatio-temporal based matching algorithm (STD-matching) for low-sampling-rate GPS trajectories. STD-matching considers (1) the spatial features such as the distance information and topology of the road network, (2) the speed constraints of the road network, and (3) the real-time moving direction which shows the movement of the user. Moreover, we also reduce the running time by performing GPS clustering, GPS smoothing, and the A * shortest path algorithms . In our experiments, we compare STD-matching with three existing algorithms, the ST-matching algorithm, the stMM algorithm, and the HMM-RCM algorithm, using a real data set . The experiment results show that our STD-matching algorithm outperforms the three existing algorithms in terms of matching accuracy.

In todays Internet, the shortest path tree (SPT) construction is an important issue in data exchange. To forward a data packet, each router uses routing protocols and link state information to identify the shortest paths from itself to other routers, which yields the shortest path tree. In reality, the network topology often varies over time. In existing studies, the locally affected nodes are identified and the shortest paths are recomputed so as to update the SPT. However, when the network size becomes large, the process of reconstructing the shortest paths for the affected nodes is very time consuming. Herein, we propose an adaptive amoeba method to build SPT in dynamic graphs. The proposed method is illustrated using a three-step procedure. First, we generalize the original Physarum model to enable it to have the ability to find the shortest paths in directed graphs. Secondly, the Physarum model is further extended to construct the shortest path tree when there are multiple sink nodes. Finally, we demonstrate that the developed method is capable of reconstructing the SPT by adapting the tube flow when link weight changes occur. Different from previous methods, the proposed algorithm is capable of identifying and recomputing the shortest paths for the affected nodes as well as maintaining the original paths for the unaffected vertices spontaneously. We demonstrate the performance of the proposed algorithm by comparing it with the Label Setting algorithm and Dijkstra algorithm in four randomly generated graphs. The computational results suggest the most appropriate algorithms to be used in different scenarios.

Existing journey planners and route recommenders mainly focus on calculating the shortest path with minimum distance or travel time. However, elderly people and those with special needs (i.e. those in wheelchairs or walking with sticks) often prefer a safer and more gentle journey. Given that their route options are affected by accessibility issues such as climbing a steep slope, it is important to design a journey planner that takes in to account the accessibility of the route, as well as the standard metrics, such as travel time and distance. Accessibility has not been explored widely in path finding problems. There are two key challenges for computing accessibility. First, the accessibility of a route is not well-defined. Second, the accessibility of a route varies from user to user. In this paper, a new algorithm is designed to tackle the above two challenges. Two metrics are defined to reflect the accessibility of a route, in terms of the total vertical distance and the maximum slope. Then, a multi-objective A* search algorithm is designed to obtain a set of Pareto-optimal routes in terms of the total distance covered and the two accessibility metrics. The user can then choose from the routes provided by the new algorithm, the most suitable one according to their own preferences. The experimental results show that the proposed algorithm is able to provide a diverse set of routes with different accessibility options, including the shortest path which does not consider any accessibility metrics. In other words, the new journey planner can satisfy the preferences of a wide range of users including both the healthy and those with special needs.

The persistent alternation of the internet world is changing networks rapidly. Shortest path discovery, especially over dynamic networks such as web page links, telephone or route networks, and ontologies, has received intense attention because of its importance for services in IoT. For example, when a new road is newly opened or becomes unavailable for any unexpected reason, the shortest paths must be recomputed. The system should respond promptly to its users with the updated recommended paths. In this paper, we propose a disk-based shortest path method that updates the shortest paths in a very large dynamic graph efficiently. The proposed method uses partial shortest paths as indices for efficient shortest path discovery. We classify the changes in the graph into four cases, such as the insertion or deletion of edges and the increase or decrease of edge weights. Our proposed strategy considers updating only the corresponding parts of the indices for each case. Our experiments on real-world dynamic datasets verify that the proposed framework updates the shortest paths 4 to 50 times faster than the existing type of framework.

We propose an orientation-guided geodesic weighting (OGGW) strategy for local stereo matching.We propose a method of cost volume filtering combining a multipoint LPA method with our OGGW strategy.We propose a PatchMatch filter with curved surface fitting (PMF-CS) to obtain a disparity map with sub-pixel accuracy. Recently, PatchMatch-based methods for local stereo matching are experiencing great progress with the use of compact and over-segmented regions that have similar intensities or colors. Using patches as support regions, this paper proposes an orientation-guided geodesic weighting (OGGW) strategy to search for an approximate shortest path from a support pixel in the patch to a pixel of interest along a guided orientation. The OGGW is computed by accumulating intensity differences or color dissimilarities between connected pixels along the path. After obtaining matching cost updates by model fitting, the OGGW is used for weighted averaging on the updated costs to obtain a filtered cost volume. In addition, a new filtering method that combines the PatchMatch filter with curved surface fitting (PMF-CS) is presented in this paper. Curved surface fitting along with outliers removal is carried out to seek for a reliable regression model for estimating the disparities on a patch and to achieve a disparity map with sub-pixel accuracy. We conduct a number of experiments to evaluate the performances of OGGW and PMF-CS on cost volume filtering and disparity estimation. Experimental results show that our algorithm produces accurate stereo matching results and outperforms the current state-of-the-art PatchMatch-based methods.

To address the challenge of logistics routing decision under uncertain environment, this paper studies a fourth party logistics routing problem (4PLRP) with uncertain delivery time (4PLRPU). A novel 4PLRPU model based on uncertainty theory is proposed by describing the delivery time of a third party logistics (3PL) provider as an uncertain variable. After that, the model is transformed into an equivalent deterministic model, and several improved genetic algorithms are designed to get solutions. To handle the problem of infeasible solutions in the proposed 4PLRPU, an improved node-based genetic algorithm (INGA) and an improved distance-based genetic algorithm (IDGA) are developed to reduce the computing time required to repair infeasible solutions, and an improved genetic algorithm based on the simple graph and Dijkstra algorithm (SDGA) is proposed to avoid the generation of infeasible solutions. Numerical experiments are conducted to investigate the performance of the proposed algorithms and verify the effectiveness of the proposed 4PLRPU model. The results show that INGA and SDGA are more effective than the standard genetic algorithm and IDGA at solving large-scale problems. Additionally, compared with the expected value model, the 4PLRPU model is more robust.

In this paper, we study a new form of reverse nearest neighbor (RNN) queries, i.e., obstructed reverse nearest neighbor (ORNN) search. It considers the impact of obstacles on the distance between objects, which is ignored by the existing work on RNN retrieval. Given a data set P, an obstacle set O, and a query point q in a two-dimensional space, an ORNN query finds from P, all the points/objects that have q as their nearest neighbor, according to the obstructed distance metric, i.e., the length of the shortest path between two points without crossing any obstacle. We formalize ORNN search, develop effective pruning heuristics (via introducing a novel concept of boundary region), and propose efficient algorithms for ORNN query processing assuming that both P and O are indexed by traditional data-partitioning indexes (e.g., R-trees). In addition, several interesting variations of ORNN queries, namely, obstructed reverse k-nearest neighbor (ORkNN) search, ORkNN search with maximum obstructed distance ? (?-ORkNN), and constrained ORkNN (CORkNN) search, have been introduced, and they can be tackled by extending the ORNN query techniques, which demonstrates the flexibility of the proposed ORNN query algorithm. Extensive experimental evaluation using both real and synthetic data sets verifies the effectiveness of pruning heuristics and the performance of algorithms, respectively.

Although various efficient indexing techniques have been proposed to improve the performance in distributing road data to mobile clients to perform shortest path searches on road networks, how to minimize the tune-in and path searching costs are still important performance goals since the clients usually have limited processing capability and energy supply. In this paper, based on the Next Region (NR) approach, we propose a new method called Approximate Path Searching (APS) for constructing the broadcast index at mobile clients with soft arrival times to destinations. APS adopts an approximation technique in calculating the sets of required regions for each region pair in a road network to reduce the index generation cost at the road server and the tune-in and path searching costs at the clients. Different from NR, which only provides one set of required regions containing the shortest path from a client's start region to its destination region, APS generates n-sets of required regions for a client to choose. Each set of required regions contains different numbers of regions. Although choosing a smaller region set may give a slightly longer delay in arrival, the tune-in and path searching costs could be significantly reduced. Theoretical analysis and extensive simulation experiments have been performed to demonstrate the effectiveness of APS in improving the system performance with just a few percentages delay in arrival time on average comparing with NR using data sets from real road networks.

Shortest path (or least travel time path) identification has been actively studied for direct application to road networks. In addition, the processing of time-dependent shortest-path queries, which use past traffic data to compute the speed variations of road segments, has been investigated in order to incorporate speed variations over time. However, speed information pre-computed from static past traffic data is often invalid because road traffic is inherently dynamic. This paper addresses a new problem in processing a Dynamic Time-Dependent Shortest Path (DTDSP) query, which considers the current road status without assuming pre-determined speed patterns on roads. By dynamically adjusting the speed patterns of roads instead of fixing them based on past traffic data, the recommended paths, which reflect the current road status, are more effective in distributing the road traffic and thus reducing the travel time. To process DTDSP queries, we first propose a Continuous Piece-wise Linear Speed Pattern (CPLSP) model to compute the vehicle speed patterns, which is more flexible and realistic than previously adopted piece-wise constant speed pattern models. Using dynamically computed CPLSPs, we process a DTDSP query in two phases: (1) the least travel time path is found for the query and (2) the speed patterns of the following vehicles, which are affected by the participation of the new vehicle on the road network, are updated. We propose efficient algorithms for finding the least travel time path of a new query (vehicle) and for updating the speed patterns of the existing vehicles. Experiments on real data sets show that our query processing algorithms effectively distribute road traffic, and thus, significantly reduce both global and individual travel times.

The n-dimensional folded hypercube FQ"n is an important variant of the n-dimensional hypercube Q"n, which is obtained from Q"n by adding an edge between any pair of vertices with complementary addresses. The diameter of FQ"n is @?n/2@?, about half the diameter of Q"n. A set of k(>=2) spanning trees rooted at the same vertex r in a graph G is said to be independent if for each vertex x other than r, the k paths from r to x, with one path in each spanning tree, are internally disjoint. By using independent spanning trees (ISTs) one can design fault-tolerant broadcasting schemes and increase message security in a network. Recently, Yang et al. proposed an algorithm, which can be parallelized, for constructing n+1 ISTs on FQ"n with the height of each spanning tree being n. In this paper, we propose an algorithm for constructing n+1 optimal ISTs on FQ"n in the sense that there is a shortest path between the only child of the root r and any other vertex in each spanning tree (therefore, the height of each spanning tree is @?n/2@?+1). Moreover, the algorithm runs in time O((n+1)N) and can be parallelized to run by using N=2^n processors on FQ"n in time O(n).

A solution to the shortest path enumeration problem can find numerous applications in studying issues related to interconnection networks. In this paper, we enumerate the number of shortest paths between any two vertices in an arrangement graph by establishing a bijection between these shortest paths and a collection of ordered forests of certain bi-colored trees, via minimum factorizations of permutations corresponding to such vertices in terms of so-called arrangement transpositions, and then count the number of these forests with the help of an existing result on the enumeration of such bi-colored trees. Our result generalizes previous ones and can be applied to solve the same problem for other related graphs such as the alternating group graph. On the other hand, the techniques applied to derive such an enumeration result further extend the ongoing work of counting the number of minimum factorizations of a permutation in terms of a certain type of transposition, a rather interesting problem in the area of algebraic combinatorics.

This paper proposes a model for a robust shortest path problem with random edge costs. The proposed model is formulated as a bicriteria optimization problem to minimize the total cost of the path from a start node to an end node as well as to maximize the range of the confidence interval satisfying the condition that the total cost of any path in the region is less than a target value in terms of robustness. It is not always the case that a solution that simultaneously optimizes all of the objectives exists when the objectives conflict with each other. In this paper, fuzzy goals for both objectives and the aggregation function are introduced in a solution approach that considers the decision maker's preference and the subjectivity of her or his judgment in multicriteria decision making. The fuzzy bicriteria problem is transformed into a constrained shortest path problem. Furthermore, an exact algorithm based on Dijkstra's algorithm and a heuristic algorithm based on the Lagrange relaxation-based algorithm are developed for the constrained shortest path problem.

The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. An n-dimensional twisted cube, TQ"n, is an important variation of the hypercube Q"n and preserves many of its desirable properties. The problem of embedding linear arrays and cycles into a host graph has attracted substantial attention in recent years. The geodesic cycle embedding problem is for any two distinct vertices, to find all the possible lengths of cycles that include a shortest path joining them. In this paper, we prove that TQ"n is geodesic 2-pancyclic for each odd integer n>=3. This result implies that TQ"n is edge-pancyclic for each odd integer n>=3. Moreover, TQ"nxK"2 is also demonstrated to be geodesic 4-pancyclic.

The use of multiple independent spanning trees (ISTs) for data broadcasting in networks provides a number of advantages, including the increase of fault-tolerance and bandwidth. Thus, the designs of multiple ISTs on several classes of networks have been widely investigated. In this paper, we give an algorithm to construct ISTs on even networks, and show that these ISTs are optimal for height and path lengths, and each path in the ISTs has length at most the length of the shortest path+4 in the even network.

A graph G is panconnected if each pair of distinct vertices u,v@?V(G) are joined by a path of length l for all d"G(u,v)=

This paper studies the issue of assigning orientations to all links of an undirected network, which is called the link-orientation problem (LOP). First, we describe some practical variations and address some complexity analysis in LOPs for general networks. Then, we design efficient algorithms to solve these LOPs issues. The proposed approach employs the recursive shortest path rules and the efficient cost cores scheme to resolve the LOP issues for some weighted network systems. These classes of networks include multi-square, convex-bipartite, and convex-split networks. Next, we use the cost core algorithm for adjusting LOP and obtain the more efficient LOP for the weighted convex-bipartite and convex-split networks. In general, the LOP scheme can support the actual applications requirements to realize a WFQ (weighted fair queuing) task for multicast routing in real networks. Finally, the findings of this paper can be mainly applied to some network applications, including efficient revision of load balancing in a ATM switch network, quick selection of a firm's PCS (Proxy Cache Server) on the Web, and dynamic adjusting of link's changing conditions in a workflow system on the Internet.

Usually each vertex of the ( s +1)-dimensional hypercube is labeled with a unique integer k with 0⩽ k ⩽2 s +1 −1. The supercube S N of N nodes with 2 s N ⩽2 s +1 is constructed by merging nodes u and u −2 s , with N ⩽ u ⩽2 s +1 −1, in the ( s +1)-dimensional hypercube into a single node labeled as u −2 s and leaving other nodes in the ( s +1)-dimensional hypercube unchanged. In this paper, we give the exact distance between any two nodes of supercube and present a new shortest path routing algorithm on S N . Then we show how to construct κ ( S N ) disjoint paths between any two nodes of the supercube, where κ ( S N ) is the connectivity of S N . Finally, we compute the wide diameter and the fault diameter of S N . We show that both the wide diameter and the fault diameter are equal to s +2 if N ∈{2 s +1 −2 i +1∣0⩽ i ⩽ s −1} and s +1 otherwise.

Many network services, such as video conferencing and video on demand, have popularly used the multimedia communications. The attached hosts/routers are required to transmit data as multicasting in most multimedia applications. In order to provide an efficient data routing, routers must provide multicast capability. In this paper, a new cooling schedule in Hopfield neural network with annealing strategy is proposed to calculate the shortest path (SP) tree for multicast open shortest path first (MOSPF) protocol. The SP tree in multicast is built on demand and is rooted at the source node. To facilitate the hardware implementation, the annealed Hopfield neural network could be a good candidate to deal with SP problems in packet switching computer networks. In addition, it is proved that the proposed new cooling schedule is more suitable in all range of fixed temperature than the other demonstrated cooling schedules in the experimental results.

Two nodes in a pebbled graph are said to be mutually visible if there exists a shortest path (a “geodesic”) between them which is unpebbled. In an earlier paper we studied this concept for node-pebbled graphs, and characterized various types of pebbled graphs that are geodesically “convex”, i.e., any two of their unpebbled nodes are mutually visible. In this paper we consider arc pebblings as well as node pebblings. We show that the visibility relations defined by arc and node pebblings are incomparable, and we give general characterizations of the visibility relations that can be defined by the two types of pebblings. We also show that in any arc-pebbled (node-pebbled) graph having n nodes, there exists a set of at most n /2 ( n /3 + 1) nodes from which every (unpebbled) node is visible.

Let V(G) be the vertex set of a graph G = (V,E), and let G - u be the subgraph induced by the vertex set V(G) - {u}. A vertex u @e V(G) is said to be a hinge vertex of G if and only if there exist two vertices x, y @e V(G-u) such that d"G" "-" "u(x,y) > d"G(x,y), where d"G(x, y) is the distance (the length of a shortest path) between x and y in G. In this paper, based on the breadth-first search technique, an O(n+e) time algorithm is proposed for finding the set of all hinge vertices of a strongly chordal graph when a strong elimination ordering is given.

A pebbled graph is called “(geodesically) convex” if at least one shortest path between any two unpebbled nodes has no pebbles on any of its nodes. There exist conditions on the node neighborhoods in a pebbled graph that imply convexity, but no such conditions can be necessary for convexity. The convex pebblings can be characterized for various special types of graphs, such as cycles, trees, and cliques. For a graph L whose nodes are the lattice points in the plane under the relation of row or column adjacency, we show that a pebbling of L is convex iff the set of unpebbled nodes is connected and orthoconvex.

A hierarchical d-dimensional object representation called a linear hypertree is introduced. Its basic properties are briefly presented along with a procedure for encoding the node's rectangular coordinates into a hierarchical locational code. Two decoding techniques that transform the node locational codes into their rectangular coordinate format are presented. The first produces individual node coordinates as scalar values, whereas the second generates the node's rectangular coordinates in a vector form. The vectorial decoding method extracts the coordinates of given node from those of the universe vertices. Hence, all coordinate transformation operations need not be applied to every hypertree node but only to the universe vertices. Some adjacency concepts in a multi-dimensional environment are defined. A neighbor-finding algorithm that identifies the locational code of the adjacent hypertree node in a given direction is also presented. This algorithm does not convert the locational code to its rectangular coordinate form; instead, it operates directly on the node locational code in order to determine the neighbor's identification. In addition, procedures for computing the locational codes of larger and smaller size neighbors are also included. Finally, an algorithm for computing the shortest path between two hypervoxels is also described as an illustration of an application of the decoding formula and the neighbor identification algorithm.

Two generalizations of the classical Tower of Hanoi problem 0, i.e., to transfer n discs from one peg to another by a series of legal moves, are considered: In 1-type problems the initial configuration is any regular distribution of the n discs among the three pegs, whereas problems of type 2 deal with arbitrary initial and final states. The interest in measuring the distance, i.e., in finding shortest paths between regular states was reinforced by experiments in cognitive psychology and artificial intelligence. The question has, however, caused much confusion in the literature. Setting out from the well-known solution for 0, some mathematical background is developed to construct simple algorithms that solve problems 1 and 2 correctly and return the minimum number of moves as well as the instructions for the first move of a shortest path.

The { S , T }-route problem inside a polygon P with a set S of of sights (edge segments) and a set T of point threats is to find a route such that each point in S is visible from at least one point in the route and the route is not visible to any of the points in T [7]. The requirement that exposure to the threats is not allowed at all is usually too severe and solutions do not exist in many cases, especially those arising in typical applications where the sights and threats overlap (e.g., defense applications). An alternative way to model the risk posed by the threats is to enclose each threat location in a polygonal envelope (within which the risk is unacceptably high) resulting in the zookeeper route problem. We are given a polygon P and a collection P ′ of convex polygons inside P and we want to find a shortest route that visits (without entering) the polygons in P ′ (e.g., design a route for a zookeeper that wants to feed animals in enclosures). We show that the general zookeeper route problem is NP-hard, we present necessary and sufficient conditions for the existence of a zookeeper route and give an O( n 2 ) algorithm for the case where P is a simple polygon and the polygons in P ′ are attached to the boundary of P .

An analysis of paths and distances in n dimensions is carried out using variable neighborhood sequences. A symbolic expression for the distance function between any two points in this quantized space is derived. An algorithm for finding the shortest path is presented. The necessary and sufficient condition for such distance functions to satisfy the properties of a metric has been derived. Certain practical and efficient methods to check for metric properties are also presented.

A generalized distance measure called m-neighbor distance in n-D quantized space is presented. Its properties as a metric are examined. It is shown to give the shortest path length between two points in n-D digital space. An algorithm for finding such a shortest path between two points is presented. It is shown that lower dimension (2-D and 3-D) distance measures presently used in digital geometry can easily be derived as special cases. Other properties of m-neighbor distance are also examined.

Let an n-configuration be an arrangement of n discs on 3 pegs. A simple recursive algorithm for the generalized Towers of Hanoi contest with arbitrary starting and ending n-configurations is presented. This algorithm always finds a shortest path between a pair of n-configurations, and is therefore optimal.