Search

In this work we investigate the problem of estimating the percolation centrality of all vertices in a weighted graph. The percolation centrality measure quantifies the importance of a vertex in a graph that is going through a contagious process. The fastest exact algorithm for the computation of this measure in a graph G with n vertices and m edges runs in O ( n 3 ) . Let Diam V ( G ) be the maximum number of vertices in a shortest path in G . In this paper we present an expected O ( m log n log Diam V ( G ) ) time approximation algorithm for the estimation of the percolation centrality for all vertices of G . We show in our experimental analysis that in the case of real-world complex networks, the output produced by our algorithm returns approximations that are even closer to the exact values than its guarantee in terms of theoretical worst case analysis.

A set of vertices S of a graph G is a (geodesically) convex set, if S contains all the vertices belonging to any shortest path connecting two vertices of S . The cardinality of a maximum proper convex set of G is called the convexity number, con ( G ) , of G . The complementary prism G G ¯ of G is obtained from the disjoint union of G and its complement G ¯ by adding the edges of a perfect matching between them. In this work, we examine the convex sets of the complementary prism of a tree and derive formulas for the convexity numbers of the complementary prisms of all trees.

Given a set X ⊆ V ( G ) , let [ X ] G denote the set of all vertices of G lying on some shortest path between two vertices of X . If [ X ] G = X , then X is a convex set of G . The convex hull of X , denoted by 〈 X 〉 G , is the smallest convex set containing X . We say that X is a hull set of G if 〈 X 〉 G = V ( G ) and that X is a geodetic set of G if [ X ] G = V ( G ) . The hull number h ( G ) of G is the minimum cardinality of a hull set of G ; and the geodetic number g ( G ) of G is the minimum cardinality of a geodetic set of G . The shadow graph of G , denoted by S ( G ) , is the graph obtained from G by adding a new vertex v ′ for each vertex v of G and joining v ′ to the neighbors of v in G . In this paper, we present sharp bounds for the geodetic and the hull numbers of shadow graphs. We characterize the classes of graphs for which some of these bounds are attained. We also prove for a fixed integer k , that the problem of deciding whether g ( S ( G ) ) ≤ n − k is NP -complete even if the diameter of G is 2; and that the problem of deciding whether h ( S ( G ) ) ≤ n − 1 belongs to P .

We consider a constrained version of the shortest path problem on the complete graphs whose edges have independent random lengths and costs. We establish the asymptotic value of the minimum length as a function of the cost-budget within a wide range.

Finite metric spaces are an essential tool in discrete mathematics and have applications in several areas including computational biology, image analysis, speech recognition, and information retrieval. Given any such metric D on a finite set X , an important problem is to find appropriate ways to realize D by weighting the edges in some graph G containing X in its vertex set such that D ( x , y ) equals the length of a shortest path from x to y in G for all x , y ∈ X . Here we focus on realizations with minimum total edge weight, called optimal realizations. By considering the 2-connected components and bridges in any optimal realization G of D we obtain an additive decomposition of D into simpler metrics. We show that this decomposition, called the block decomposition, is canonical in that it only depends on D and not on G , and that the decomposition can be computed in O ( | X | 3 ) time. As well as providing a fundamental new way to decompose any finite metric space, we expect that the block decomposition will provide a useful preprocessing tool for deriving metric realizations.

We study robust solutions for combinatorial optimization problems with budgeted uncertainty sets in the min–max–min setting, where the decision maker is allowed to choose a set of k different solutions from which one can be chosen after the uncertain scenario has been revealed. We first show how the problem can be decomposed into polynomially many subproblems if k is fixed. We then consider the special case where k = 2 , i.e., one is allowed to choose two different solutions to hedge against the uncertainty. Using the decomposition, we provide polynomial-time algorithms for the unconstrained combinatorial optimization problem, the matroid maximization problem, the selection problem, and the shortest path problem on series–parallel graphs. The shortest path problem on general graphs turns out to be NP -hard. We show how to transform approximation algorithms for minimization subproblems to approximation algorithms for the robust problem and study the knapsack problem to show that this does not hold for maximization problems in general. We present a PTAS for the corresponding subproblem and prove that the min–max–min knapsack problem with k = 2 is not approximable at all.

Let G be a plane graph, and let S be the union of all edges and vertices of G , equipped with the standard Euclidean topology of the plane. A path between points x , y ∈ S is a minimal, with respect to inclusion, connected subset of S containing x and y (here x and y are not necessarily endpoints of an edge). The distance between points x , y ∈ S , denoted as d ( x , y ) , is the length of a shortest path between x and y in S . An l -covering of G is a finite set of points X ⊆ S such that for every point y ∈ S , there is a point x ∈ X , such that d ( x , y ) ≤ l . The l -covering number of G is the minimum size of an l -covering of G . Let α ( m , n ) be the l -covering number of the grid graph on m n vertices embedded in the plane so that the edges are either horizontal or vertical straight lines of length l . In this note we prove that α ( m , n ) = m n − 1 2 for m n > 1 .

For many classical combinatorial optimization problems such as, e.g., the shortest path problem or the spanning tree problem, the robust counterpart under general discrete, polytopal, or ellipsoidal uncertainty is known to be intractable. This implies that any algorithm solving the robust counterpart that can access the underlying certain problem only by an optimization oracle has to call this oracle more than polynomially many times, unless P = NP. In this short note, we show by a simple construction that, in fact, such an algorithm needs exponentially many oracle calls in the worst case even without assuming P ≠ NP. Moreover, we show that oracle-based pseudopolynomial or approximation algorithms cannot exist either.

Consider a situation in which individuals –the buyers –have different valuations for the products of a given set. An envy-free assignment of product items to buyers requires that the items obtained by every buyer be purchased at a price not larger than his/her valuation, and each buyer’s welfare (difference between product value and price) be the largest possible. Under this condition, the problem of finding prices maximizing the seller’s revenue is known to be APX -hard even for unit-demand bidders (with several other inapproximability results for different variants), that is, when each buyer wishes to buy at most one item. Here, we focus on Envy-free Complete Allocation , the special case where a fixed number of copies of each product is available, each of the n buyers must get exactly one product item, and all the products must be sold. This case is known to be solvable in O ( n 4 ) time. We revisit a series of results on this problem and, answering a question found in Leonard (1983), show how to solve it in O ( n 3 ) time by connections to perfect matchings and shortest paths.

Distance between two vertices is the number of edges in a shortest path connecting them in a connected graph G . The transmission of a vertex v is the sum of distances from v to all the other vertices of G . If transmissions of all vertices are mutually distinct, then G is a transmission irregular graph. It is known that almost no graphs are transmission irregular. Infinite families of transmission irregular trees and 2-connected graphs were presented in Alizadeh and Klavžar (2018) and Dobrynin (2019) [8, 9]. The following problem was posed in Alizadeh and Klavžar (2018): do there exist infinite families of regular transmission irregular graphs? In this paper, an infinite family of 3-connected cubic transmission irregular graphs is constructed.

We study a facility location problem motivated by requirements pertaining to the distribution of charging stations for electric vehicles: Place a minimum number of battery charging stations at a subset of nodes of a network, so that battery-powered electric vehicles will be able to move between destinations using “ t -spanning” routes, of lengths within a factor t > 1 of the length of a shortest path, while having sufficient charging stations along the way. We give constant-factor approximation algorithms for minimizing the number of charging stations, subject to the t -spanning constraint. We study two versions of the problem, one in which the stations are required to support a single ride (to a single destination), and one in which the stations are to support multiple rides through a sequence of destinations, where the destinations are revealed one at a time.

We address the problem of computing distances between rankings that take into account similarities between candidates. The need for evaluating such distances is governed by applications as diverse as rank aggregation, bioinformatics, social sciences and data storage. The problem may be summarized as follows: Given two rankings and a positive cost function on transpositions that depends on the similarity of the candidates involved, find a smallest cost sequence of transpositions that converts one ranking into another. Our focus is on costs that may be described via special metric-tree structures and on complete rankings modeled as permutations. The presented results include a quadratic-time algorithm for finding a minimum cost decomposition for simple cycles, and a quadratic-time, $4/3$-approximation algorithm for permutations that contain multiple cycles. The proposed methods rely on investigating a newly introduced balancing property of cycles embedded in trees, cycle-merging methods, and shortest path optimization techniques., 32 pages, 14 figures. Corrected proof of unbalanced case

Given an arbitrary directed graph G = ( V , E ) with non-negative edge lengths, we present an algorithm that computes all pairs shortest paths in time O ( m ∗ n + m lg n + n T ψ ( m ∗ , n ) ) , where m ∗ is the number of different edges contained in shortest paths and T ψ ( m ∗ , n ) is the running time of an algorithm ψ solving the single-source shortest path problem (SSSP). This is a substantial improvement over a trivial n times application of ψ that runs in O ( n T ψ ( m , n ) ) . In our algorithm we use ψ as a black box and hence any improvement on ψ results also in improvement of our algorithm. A combination of our method, Johnson’s reweighting technique and topological sorting results in an O ( m ∗ n + m lg n ) all-pairs shortest path algorithm for directed acyclic graphs with arbitrary edge lengths. We also point out a connection between the complexity of a certain sorting problem defined on shortest paths and SSSP. Finally, we show how to improve the performance of the proposed algorithm in practice. We then empirically measure the running times of various all-pairs shortest path algorithms on randomly generated graph instances and obtain very promising results.

Considering an integer k and a directed, weighted graph with two distinct nodes s and t, the Hop-Constrained Shortest Path Problem looks for a shortest (s,t)-path using at most k arcs. In this paper, we study the polytope of the convex hull of incidence vectors of (s,t)-paths using at most k arcs. We present valid inequalities and adaptations of known concepts such as cloning and a unique representation of facets. The main focus will be on one particular family of valid inequalities, the family of Jump Inequalities. Thereby, the main contribution will be a characterization of the members of the family inducing facets. Furthermore, all possibilities to lift the remaining inequalities will be defined. The analysis of Jump Inequalities will be concluded by further results concerning the equivalence of inequalities as well as their Chvtal rank.

In this work we address a game theoretic variant of the shortest path problem, in which two decision makers (players) move together along the edges of a graph from a given starting vertex to a given destination. The two players take turns in deciding in each vertex which edge to traverse next. The decider in each vertex also has to pay the cost of the chosen edge. We want to determine the path where each player minimizes its costs taking into account that also the other player acts in a selfish and rational way. Such a solution is a subgame perfect equilibrium and can be determined by backward induction in the game tree of the associated finite game in extensive form.We show that the decision problem associated with such a path is PSPACE-complete even for bipartite graphs both for the directed and the undirected version. The latter result is a surprising deviation from the complexity status of the closely related game Geography.On the other hand, we can give polynomial time algorithms for directed acyclic graphs and for cactus graphs even in the undirected case. The latter is based on a decomposition of the graph into components and their resolution by a number of fairly involved dynamic programming arrays. Finally, we give some arguments about closing the gap of the complexity status for graphs of bounded treewidth.

In this paper communication in hexagonal network is analyzed. Every vertex of the network has direct connections to its neighbors. They communicate with neighborhood sequences varying the used neighborhood relations in each step. Theoretical results, such as algorithm to provide a shortest path and properties of B -distances are shown. Applications for broadcasting information and for two-way communications are presented and discussed.

Let D be a digraph. A path partition of D is called k-optimal if the sum of the k-norms of its paths is minimal. The k-norm of a path P is min(|V(P)|,k). Berges path partition conjecture claims that for every k-optimal path partition P there are k disjoint stable sets orthogonal to P. For general digraphs the conjecture has been proven for k=1,2,1,, where is the length of a longest path in the digraph. In this paper we prove the conjecture for 2 and 3.

We describe the clique-width of path powers by an exact formula, depending only on the number of vertices and the clique number. As a consequence, the clique-width of path powers can be computed in linear time. Path powers are a graph class of unbounded clique-width. Prior to our result, square grids constituted the only known graph class of unbounded clique-width with a similar result. We also show that clique-width and linear clique-width coincide on path powers.

International audience; We study the shortest-path broadcast problem in graphs and digraphs, where a message has to be transmitted from a source node s to all the nodes along shortest paths, in the classical telephone model. For both graphs and digraphs, we show that the problem is equivalent to the broadcast problem in layered directed graphs. We then prove that this latter problem is NP-hard, and therefore that the shortest-path broadcast problem is NP-hard in graphs as well as in digraphs. Nevertheless, we prove that a simple polynomial-time algorithm, called MDST-broadcast, based on min-degree spanning trees, approximates the optimal broadcast time within a multiplicative factor 3/2 in 3-layer digraphs, and O(log n/loglog n) in arbitrary multi-layer digraphs. As a consequence, one can approximate the optimal shortest-path broadcast time in polynomial time within a multiplicative factor 3/2 whenever the source has eccentricity at most 2, and within a multiplicative factor O(log n/\log\log n) in the general case, for both graphs and digraphs. The analysis of MDST-broadcast is tight, as we prove that this algorithm cannot approximate the optimal broadcast time within a factor smaller than Omega(log n/log\log n).

We introduce the Minimum Flow Cost Hamiltonian Cycle Problem (FCHCP). Given a graph and positive flow between pairs of vertices, the FCHCP consists of finding a Hamiltonian cycle that minimizes the total flow cost between pairs of vertices through the shortest path on the cycle. We prove that the FCHCP is NP-hard and we study the polyhedral structure of its set of feasible solutions. In particular, we present five different mixed integer programming formulations which are theoretically and computationally compared. We also propose several families of valid inequalities for one of the formulations and perform some computational experiments to assess the performance of these inequalities.

Routing traffic on the internet efficiently has become an important research topic over the past decade. In this article we consider a generalization of the shortest path problem, the path-trading problem, which has applications in inter-domain traffic routing. When traffic is forwarded between autonomous systems (ASes), such as competing internet providers, each AS selfishly routes the traffic inside its own network. Efficient solutions to the path trading problem can lead to higher global performance in such systems, while maintaining the objectives and costs of the individual ASes. First, we extend a previous hardness result for the path trading problem. Moreover, we provide an algorithm that finds all Pareto-optimal path trades for a pair of two ASes. While in principal the number of Pareto-optimal path trades can be exponential, in our experiments this number was typically small. We use the framework of smoothed analysis to give a theoretical explanation for that fact. The computational results show that our algorithm yields far superior running times and can solve considerably larger instances than a previously known algorithm.

In the Switching Tower of Hanoi interpretation of Sierpinski graphs S p n , the P2 decision problem is to find out whether the largest moving disc has to be transferred once or twice in a shortest path between two given states/vertices. We construct an essentially optimal algorithm thus extending Romik’s approach for p = 3 to the general case. The algorithm makes use of three automata and the underlying theory includes a simple argument for the fact that there are at most two shortest paths between any two vertices. The total number of pairs leading to non-unique solutions is determined and employing a Markov chain argument it is shown that the number of input pairs needed for the decision is bounded above by a number independent of n . Elementary algorithms for the length of the shortest path(s) and the best first move/edge are also presented.

Multiobjective combinatorial optimization deals with problems considering more than one viewpoint or scenario. The problem of aggregating multiple criteria to obtain a globalizing objective function is of special interest when the number of Pareto solutions becomes considerably large or when a single, meaningful solution is required. Ordered weighted average or ordered median operators are very useful when preferential information is available and objectives are comparable since they assign importance weights not to specific objectives but to their sorted values. In this paper, ordered weighted average optimization problems are studied from a modeling point of view. Alternative integer programming formulations for such problems are presented and their respective domains studied and compared. In addition, their associated polyhedra are studied and some families of facets and new families of valid inequalities presented. The proposed formulations are particularized for two well-known combinatorial optimization problems, namely, shortest path and minimum cost perfect matching, and the results of computational experiments presented and analyzed. These results indicate that the new formulations reinforced with appropriate constraints can be effective for efficiently solving medium to large size instances.

In 23], Klav?ar and Milutinovic (1997) proved that there exist at most two different shortest paths between any two vertices in Sierpinski graphs S k n , and showed that the number of shortest paths between any fixed pair of vertices of S k n can be computed in O ( n ) . An almost-extreme vertex of S k n , which was introduced in Klav?ar and Zemljic (2013) 27], is a vertex that is either adjacent to an extreme vertex or incident to an edge between two subgraphs of S k n isomorphic to S k n - 1 . In this paper, we completely determine the set S u = { v ? V ( S k n ) : there?exist?two?shortest? u , v -paths?in? S k n } , where u is any almost-extreme vertex of S k n .

Given a set of n open rectangles that represent obstacles in the Euclidean plane, we consider the problem of finding a shortest rectilinear path between two given points such that each segment of the path has a certain minimum length. A rectilinear path consists of horizontal and vertical segments only and may not intersect with an obstacle. We show how to solve the resulting shortest path problem with minimum segment lengths in polynomial time by constructing an extended Hanan grid of the instance first, and then run an adapted shortest path algorithm to find a respective solution. While the extended Hanan grid as basic underlying structure can be stored in O(n^2) space, the approach yields an O(n^4logn) time and O(n^4) space algorithm. The problem at hand typically arises in the area of VLSI design, where rectilinear paths are utilized to create wiring interconnects. There, the lithographic production process dictates certain minimum run lengths for the wires in order to avoid infeasible patterns. Another application arises in robot motion planning when acceleration and breaking distances need to be obeyed.

In practice, it is important to construct node-disjoint paths in networks, because they can be used to increase the transmission rate and enhance the transmission reliability. The hyper-star networks HS(2n,n) were introduced to be a competitive model for both the hypercubes and the star graphs. In this paper, one-to-many node-disjoint paths are constructed between a fixed node and n other nodes of HS(2n,n) such that each of these paths has length at most 4 more than the shortest path to that node. Moreover, their maximum length is not greater than the diameter+2.

Recently, Chan et?al. introduced geodesic-pancyclic graphs H.C. Chan, J.M. Chang, Y.L.?Wang, S.J. Horng, Geodesic-pancyclic graphs, Discrete Applied Mathematics 155 (15) (2007) 1971-1978] and weakly geodesic pancyclicity H.C. Chan, J.M. Chang, Y.L.?Wang, S.J. Horng, Geodesic-pancyclicity and fault-tolerant panconnectivity of augmented cubes, Applied Mathematics and Computation 207 (2009) 333-339]. Hsu et?al. proposed a new cycle-embedding property called balanced pancyclicity H.C. Hsu, P.L. Lai, C.H.?Tsai, Geodesic pancyclicity and balanced pancyclicity of augmented cubes, Information Processing Letters 101 (2007) 227-232]. For a graph G ( V , E ) and any two vertices x and y of V , a cycle R containing x and y can be divided into two paths, P t 1 and P t 2 , joining x and y such that len ( P t 1 ) ? len ( P t 2 ) , where len ( λ ) denotes the length of the path λ . A geodesic cycle contains P t 1 , which is the shortest path joining x and y in G , whereas, in a balanced cycle of an even (respectively, odd) length, len ( P t 1 ) = len ( P t 2 ) (respectively, len ( P t 1 ) = len ( P t 2 ) - 1 ). A graph is weakly geodesic pancyclic (respectively, balanced pancyclic) if every two vertices x and y are contained in a geodesic cycle (respectively, balanced cycle) from Max ( 3 , 2 Dist ( x , y ) ) to N , where N is the order of the graph. The interconnection network considered in this paper is the generalized base- b hypercube, which is an attractive variant of the well-known hypercube. In fact, the generalized base- b hypercube is the Cartesian product of complete graphs with b vertices. The generalized base- b hypercube is superior to the hypercube in many criteria, such as diameter, connectivity, and fault diameter. In this paper, we study weakly geodesic pancyclicity and balanced pancyclicity of the generalized base- b hypercube. We show that the generalized base- b hypercube is weakly geodesic pancyclic for b ? 3 and balanced pancyclic for b ? 4 .

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints. We prove that the minimum spanning tree problem is strongly NP -hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP -hard for conflict graphs where every connected component is a single edge. Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.

We study a new two-stage version of an s-t path problem, which we call adaptable robust connection path (ARCP). Given an undirected graph G=(V,E), two vertices s,t@?V and two integers f,r@?Z"+, ARCP asks to find a set S@?E of minimum cardinality which connects s and t, such that for any 'failure set' F@?E with |F|@?f, the set of edges S@?F can be completed to a set which connects s and t by adding at most r edges from E@?F. We show the problem is NP-hard, and there is no polynomial-time @a-approximation algorithm for the problem for @a

This paper concerns the reverse 2-median problem on trees and the reverse 1-median problem on graphs that contain exactly one cycle. It is shown that both models under investigation can be transformed to an equivalent reverse 2-median problem on a path. For this new problem an O(nlogn) algorithm is proposed, where n is the number of vertices of the path. It is also shown that there exists an integral solution if the input data are integral.

An induced subgraph H of a graph G is gated if for every vertex x outside H there exists a vertex x^' inside H such that each vertex y of H is connected with x by a shortest path passing through x^'. The gated amalgam of graphs G"1 and G"2 is obtained from G"1 and G"2 by identifying their isomorphic gated subgraphs H"1 and H"2. Two theorems on Hosoya polynomials of gated amalgams are provided. As their applications, explicit expressions for Hosoya polynomials of hexagonal chains are obtained.

New efficient algorithms for solving infinite-duration two-person adversary games with the decision problem inNP∩coNP, based on linear programming (LP), LP-representations, combinatorial LP, linear complementarity problem (LCP), controlled LP are surveyed.

We suggest the first strongly subexponential and purely combinatorial algorithm for solving the mean payoff games problem. It is based on iteratively improving the longest shortest distances to a sink in a possibly cyclic directed graph. We identify a new ''controlled'' version of the shortest paths problem. By selecting exactly one outgoing edge in each of the controlled vertices we want to make the shortest distances from all vertices to the unique sink as long as possible. The decision version of the problem (whether the shortest distance from a given vertex can be made bigger than a given bound?) belongs to the complexity class NP@?CONP. Mean payoff games are easily reducible to this problem. We suggest an algorithm for computing longest shortest paths. Player MAX selects a strategy (one edge from each controlled vertex) and player MIN responds by evaluating shortest paths to the sink in the remaining graph. Then MAX locally changes choices in controlled vertices looking at attractive switches that seem to increase shortest paths lengths (under the current evaluation). We show that this is a monotonic strategy improvement, and every locally optimal strategy is globally optimal. This allows us to construct a randomized algorithm of complexity min(poly.W,2^O^(^n^l^o^g^n^)), which is simultaneously pseudopolynomial (W is the maximal absolute edge weight) and subexponential in the number of vertices n. All previous algorithms for mean payoff games were either exponential or pseudopolynomial (which is purely exponential for exponentially large edge weights).

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.

We investigate the applicability of spanners as substructures that offer both low cost and low delay for broadcast and multicast. A k-spanner has the potential to offer lower delay than shared multicast trees because it limits the distance between any two nodes in the network to a multiplicative factor k of the shortest-path distance. Using simulation over random topologies, we compare k-spanners to single-source minimum-distance spanning trees and show that a k-spanner can have similar cost and lower delay. We illustrate that by varying the value of k a spanner can be made to gradually favor cost over delay. These results indicate the spanner can reduce the cost of flooding, which is a basic mechanism used in multicast routing protocols.

We present deterministic algorithms to search for an item s contained in a node of a network, without prior knowledge of its exact location. Each node of the network has a database that will answer queries of the form “how do I get to s ?” by responding with the first edge on a shortest path to the node containing s . It may happen that some nodes, called liars , give bad advice. If the number of liars k is bounded, we show different strategies to find the item depending on the topology of the network. In particular we consider the complete graph, ring, torus, hypercube and bounded degree trees.

Given a simple polygon P with n vertices and a starting point s on its boundary, the watchman route problem asks for a shortest route in P through s such that each point in the interior of the polygon can be seen from at least one point along the route. In this paper, we present a simple, linear-time algorithm for computing a watchman route of length at most 2 times that of the shortest watchman route. The best known algorithm for computing the shortest watchman route through s takes O(n4) time. In addition, it is too complicated to be suitable in practice. Moreover, our approximation scheme can be applied to the zookeeper’s problem, which is a variant of the watchman route problem.

In their seminal paper, Frank and Jordán show that a large class of optimization problems including certain directed edge augmentation ones fall into the class of covering supermodular functions over pairs of sets. They also give an algorithm for such problems, however, that relies on the ellipsoid method.Our main result is a combinatorial algorithm for the restricted covering problem when the supermodular function is 0–1 valued; the problem includes directed vertex or S−T connectivity augmentation by one. Our algorithm uses an approach completely different from that of an independent recent result of Frank. It finds covers of partially ordered sets that satisfy natural abstract properties slightly extending those in Frank and Jordán. The algorithm resembles primal–dual augmenting path algorithms: For an initial (possibly greedy) cover the algorithm searches for witnesses for the necessity of each element in the cover. If no two witness have a common cover, the solution is optimal. As long as this is not the case, the witnesses are gradually exchanged by smaller ones (PUSHDOWN step). Each witness change defines an appropriate change in the solution; these changes are finally unwound in a shortest path manner to obtain a solution of size one less (REDUCE step).

The maximum mean weight cycle problem is well-known: given a digraph G with weights c:E(G)→R, find a directed circuit in G whose mean weight is maximum. Closely related is the minimum balance problem: Find a potential π:V(G)→R such that the numbers slack(e)≔π(w)−π(v)−c((v,w))(e=(v,w)∈E(G)) are optimally balanced: for any subset of vertices, the minimum slack on an entering edge should equal the minimum slack on a leaving edge. Both problems can be solved by a parametric shortest path algorithm.We describe an application of these problems to the design of logic chips. In the simplest model, optimizing the clock schedule of a chip to minimize the cycle time is equivalent to a maximum mean weight cycle problem. It is very important to find a solution with well-balanced slacks; this problem, in the simple model, is a minimum balance problem.However, in practical situations many constraints have to be taken into account. Therefore minimizing the cycle time and finding the optimum slack distribution are more general problems. We show how a parametric shortest path algorithm can be extended to solve these problems efficiently.Computational results with recent IBM processor chips show that the cycle time reduces considerably. Moreover, the number of critical paths (with small slack) decreases dramatically. As a result we obtain significantly faster chips. The running time of our algorithm is reasonable even for very large designs.

The problem of finding the optimal paths in network games with p players, which generalizes the well-known combinatorial problem on the shortest path in a network and which arose as an auxiliary one when studying cyclic games, is studied. Polynomial-time algorithms for finding the optimal paths as well as the optimal by Nash strategies of the players in network games are proposed.

Given a network modeled by a probabilistic graph G=(V,E) with bounds on the operation probabilities of edges and of pairs of edges, the second order two-terminal reliability problem is to find best possible bounds on the probability of an operating path between two given nodes s and t without assuming independence of failures. An exact column generation method is proposed to solve this problem as well as several variants of it. The auxiliary problem is to find an optimum (s−t)-connected (or (s−t)-disconnected) subgraph and is strongly NP-hard. This is also the case for the quadratic shortest path problem and for the quadratic minimum cut problem considered by Assous (Networks 16(1986) 319–329) in heuristics for the second order two-terminal reliability problem. Tabu search heuristics and row generation integer programming algorithms are proposed for solving the auxiliary problem. Computational results are provided for examples from the literature.

The disjoint shortest paths problem is defined as follows. Given a graph G and k pairs of distinct vertices ( s i , t i ), 1 ⩽ i ⩽ k , find whether there exist k pairwise disjoint shortest paths P i , between s i and t i for all 1 ⩽ i ⩽ k . We may consider directed or undirected graphs and the paths may be vertex or edge disjoint. We show that these four problems are NP-complete when k is part of the input even for planar graphs with unit edge-lengths. We give a polynomial algorithm for the two disjoint shortest paths problem (vertex and edge disjoint paths) in undirected graphs with positive edge-lengths. We also consider the following variation of the problem. Given a graph and two distinct pairs of vertices, find whether there exist two disjoint paths P 1 , P 2 between them such that P 1 is a shortest path. We show that this problem is NP-complete for undirected graphs with unit edge-lengths. This result is surprising in view of the existence of polynomial algorithms for both the two disjoint paths problem and the two disjoint shortest paths problem for undirected graphs.

We evaluate the mean internodal distance and the saturation throughput of the Manhattan Street network in the general case, and present a simple shortest path routing algorithm for this topology. We also propose efficient routing algorithms to execute generic communication tasks, such as the total exchange and the multinode broadcast, in a Manhattan Street network of processors. The proposed algorithms execute these tasks in an optimal number of steps, while achieving full (equal to 100%) utilization of the network links. Finally, we construct edge-disjoint Hamiltonian cycles for the Manhattan Street network.

In this paper an inverse problem of the weighted shortest arborescence problem is discussed. That is, given a directed graph G and a set of nonnegative costs on its arcs, we need to modify those costs as little as possible to ensure that T, a given v1 -arborescence of G, is the shortest one. It is found that only the cost of T needs modifying. An O(n3) combinatorial algorithm is then proposed. This algorithm also gives an optimal solution to the inverse weighted shortest path problem.

In this paper, we study the problem of homomorphisms of a general class of line digraphs. We show that the homomorphisms can always be defined using a partial binary operation on the alphabet whose letters form labels of the vertices. We apply these results to de Bruijn and Kautz (in short B/K) digraphs to characterize their uniform homomorphisms. For d non-prime, we describe algorithms for constructing non-trivial uniform homomorphisms of d -ary B/K digraphs of diameter D onto d -ary B/K digraphs of diameter D − 1. Using the properties of the uniform homomorphisms and shortest-path spanning trees of B/K digraphs, we also describe optimal emulations of Divide&Conquer computations on B/K digraphs.

For a fixed positive integer k, the k-path partition problem is to partition the vertex set of a graph into the smallest number of paths such that each path has at most k vertices. The 2-path partition problem is equivalent to the edge-cover problem. This paper presents a linear-time algorithm for the k-path partition problem in trees. The algorithm is applicable to the problem of finding the minimum number of message originators necessary to broadcast a message to all vertices in a tree network in one or two time units.

The objective of this paper is to advance the view that solving the all-pairs shortest path (APSP) problem for a chordal graph G is a two-step process: the first step is determining vertex pairs at distance two (i.e., computing G 2 ) and the second step is finding the vertex pairs at distance three or more. The main technical result here is that the APSP problem for a chordal graph can be solved in O ( n 2 ) time (optimally), if G 2 is already known. It can be shown that computing G 2 for chordal graphs is as hard as for general graphs. We then show certain subclasses of chordal graphs for which G 2 can be computed more efficiently. This leads to optimal APSP algorithms for these classes of graphs in a more natural way than previously known results. Finally, we present an optimal parallel algorithm for the APSP problem on chordal graphs by exploiting new structural properties of shortest paths. Our parallel algorithm uses O ( M ( n )) operations where M ( n ) is the time needed for the fastest known algorithm for multiplying two n × n matrices over a ring.