An efficient certifying algorithm for the Hamiltonian cycle problem on circular-arc graphs

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is an evidence that can be used to authenticate the correctness of the answer. A Hamiltonian cycle in a graph is a simple cycle in which each vertex of the graph appears exactly once. The Hamiltonian cycle problem is to determine whether or not a graph contains a Hamiltonian cycle. The best result for the Hamiltonian cycle problem on circular-arc graphs is an O(n²logn)-time algorithm, where n is the number of vertices of the input graph. In fact, the O(n²logn)-time algorithm can be modified as a certifying algorithm although it was published before the term certifying algorithms appeared in the literature. However, whether there exists an algorithm whose time complexity is better than O(n²logn) for solving the Hamiltonian cycle problem on circular-arc graphs has been opened for two decades. In this paper, we present an O(Δn)-time certifying algorithm to solve this problem, where Δ represents the maximum degree of the input graph. The certificates provided by our algorithm can be authenticated in O(n) time.     

An efficient parallel algorithm for shortest paths in planar layered digraphs

Computing shortest paths in a directed graph has received considerable attention in the sequential RAM model of computation. However, developing a polylog-time parallel algorithm that is close to the sequential optimal in terms of the total work done remains an elusive goal. We present a first step in this direction by giving efficient parallel algorithms for shortest paths in planar layered digraphs.We show that these graphs admit special kinds of separators calledone- way separators which allow the paths in the graph to cross it only once. We use these separators to give divide- and -conquer solutions to the problem of finding the shortest paths between any two vertices. We first give a simple algorithm that works in the CREW model and computes the shortest path between any two vertices in ann-node planar layered digraph in timeO(log² n) usingn/logn processors. We then use results of Aggarwal and Park [1] and Atallah [4] to improve the time bound toO(log² n) in the CREW model andO(logn log logn) in the CREW model. The processor bounds still remain asn/logn for the CREW model andn/log logn for the CRCW model.Support for the first and third authors was provided in part by a National Science Foundation Presidential Young Investigator Award CCR-9047466 with matching funds from IBM, by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052, ARPA, Order 8225. Support for the second author was provided in part by NSF Research Grant CCR-9007851, by Army Research Office Grant DAAL03-91-G-0035, and by the Office of Naval Research and the Advanced Research Projects Agency under Contract N00014-91-J-4052 and ARPA Order 8225.     

A running time analysis of an Ant Colony Optimization algorithm for shortest paths in directed acyclic graphs

In this paper, we prove polynomial running time bounds for an Ant Colony Optimization (ACO) algorithm for the single-destination shortest path problem on directed acyclic graphs. More specifically, we show that the expected number of iterations required for an ACO-based algorithm with n ants is for graphs with n nodes and m edges, where ρ is an evaporation rate. This result can be modified to show that an ACO-based algorithm for One-Max with multiple ants converges in expected iterations, where n is the number of variables. This result stands in sharp contrast with that of Neumann and Witt, where a single-ant algorithm is shown to require an exponential running time if ρ=O(n−1−ε) for any ε>0.     

k best cuts for circular-arc graphs

Given a set ofn nonnegativeweighted circular arcs on a unit circle, and an integerk, thek Best Cust for Circular-Arcs problem, abbreviated as thek-BCCA problem, is to find a placement ofk points, calledcuts, on the circle such that the total weight of the arcs that contain at least one cut is maximized. We first solve a simpler version, thek Best Cuts for Intervals (k-BCI) problem, inO(kn+n logn) time andO(kn) space using dynamic programming. The algorithm is then extended to solve a variation, called thek-restricted BCI problem, and the space complexity of thek-BCI problem can be improved toO(n). Based on these results, we then show that thek-BCCA problem can be solved inO(I(k,n)+nlogn) time, whereI(k, n) is the time complexity of thek-BCI problem. As a by-product, thek Maximum Cliques Cover problem (k>1) for the circular-arc graphs can be solved inO(I(k,n)+nlogn) time. This work was supported in part by the National Science Foundation under Grants CCR-8901815, CCR-9309743, and INT-9207212, and by the Office of Naval Research under Grant No. N00014-93-1-0272.     

An optimal parallel algorithm for computing cut vertices and blocks on interval graphs

In this paper, a parallel algorithm is presented to find all cut-vertices and blocks of an interval graph. If the list of sorted end points of the intervals of an interval graph is given then the proposed algorithm takes O(log n) time and O(n/log n) processors on an EREW PRAM, if the sorted list is not given then the time and processors complexities are respectively O(log n) and O(n).     

Improved algorithm for all pairs shortest paths

We present an improved algorithm for all pairs shortest paths. For a graph of n vertices our algorithm runs in O(n³(loglogn/logn)^5/7) time. This improves the best previous result which runs in O(n³(loglogn/logn)^1/2) time.     

Improved algorithm for finding next-to-shortest paths

We study the problem of finding the next-to-shortest paths in a weighted undirected graph. A next-to-shortest (u,v)-path is a shortest (u,v)-path amongst (u,v)-paths with length strictly greater than the length of the shortest (u,v)-path. The first polynomial algorithm for this problem was presented in [I. Krasikov, S.D. Noble, Finding next-to-shortest paths in a graph, Inform. Process. Lett. 92 (2004) 117-119]. We improve the upper bound from O(n³m) to O(n³).     

Improved algorithms for the k simple shortest paths and the replacement paths problems

Given a directed, non-negatively weighted graph G=(V,E) and s,t∈V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want the shortest path from s to t that avoids e, for every edge e in the original shortest path from s to t. The best known algorithm for the k simple shortest paths problem has a running of O(k(mn+n²logn)). For the replacement paths problem the best known result is the trivial one running in time O(mn+n²logn).In this paper we present two simple algorithms for the replacement paths problem and the k simple shortest paths problem in weighted directed graphs (using a solution of the All Pairs Shortest Paths problem). The running time of our algorithm for the replacement paths problem is O(mn+n²loglogn). For the k simple shortest paths we will perform O(k) iterations of the second simple shortest path (each in O(mn+n²loglogn) running time) using a useful property of Roditty and Zwick [L. Roditty, U. Zwick, Replacement paths and k simple shortest paths in unweighted directed graphs, in: Proc. of International Conference on Automata, Languages and Programming (ICALP), 2005, pp. 249-260]. These running times immediately improve the best known results for both problems over sparse graphs.Moreover, we prove that both the replacement paths and the k simple shortest paths (for constant k) problems are not harder than APSP (All Pairs Shortest Paths) in weighted directed graphs.     

Efficient parallel algorithms for computing all pair shortest paths in directed graphs

We present parallel algorithms for computing all pair shortest paths in directed graphs. Our algorithm has time complexityO(f(n)/p+I(n)logn) on the PRAM usingp processors, whereI(n) is logn on the EREW PRAM, log logn on the CCRW PRAM,f(n) iso(n ³). On the randomized CRCW PRAM we are able to achieve time complexityO(n ³/p+logn) usingp processors. A preliminary version of this paper was presented at the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, June 1992. Support by NSF Grant CCR 90-20690 and PSC CUNY Awards #661340 and #662478.     

A linear time recognition algorithm for proper interval graphs

We propose a linear time recognition algorithm for proper interval graphs. The algorithm is based on certain ordering of vertices, called bicompatible elimination ordering (BCO). Given a BCO of a biconnected proper interval graph G, we also propose a linear time algorithm to construct a Hamiltonian cycle of G.     

A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs

In this paper, we first show how a certain ordering of vertices, called bicompatible elimination ordering (BCO), of a proper interval graph can be used to solve efficiently several problems in proper interval graphs. We, then, propose an NC parallel algorithm (i.e., polylogarithmic-time employing a polynomial number of processors) in SIMD CRCW PRAM (Single Instruction Stream Multiple Data Stream Concurrent Read Concurrent Write Parallel Random Access Machine) model of parallel computation to compute a BCO of a proper interval graph. To the best of our knowledge, this is the first NC parallel algorithm to compute a BCO of a proper interval graph.     

An improved algorithm for online coloring of intervals with bandwidth

We present an improved online algorithm for coloring interval graphs with bandwidth. This problem has recently been studied by Adamy and Erlebach and a 195-competitive online strategy has been presented. We improve this by presenting a 10-competitive strategy. To achieve this result, we use variants of an optimal online coloring algorithm due to Kierstead and Trotter.     

An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs

In this paper, a graph problem on connected, weighted, undirected graphs, called the searchlight guarding problem, is considered. Assume that there is a fugitive who moves along the edges of the graph at a random speed. The task involves placing a set of searchlights at vertices to search the edges of the graph and to spot the fugitive. Suppose that placing a searchlight at some vertex incurs some building cost. The searchlight guarding problem is to allocate a set S of searchlights at the vertices such that the total cost of the vertices in S is minimized. If there is more than one set of searchlights, each with a minimum building cost, then identify the set with the minimum search time, that is, where the time slots needed to spot the fugitive is the minimum. As is well established, the problem is NP-hard on weighted bipartite graphs but is linear-time solvable on weighted trees. In this paper, the design of a linear-time optimal algorithm for the searchlight guarding problem on weighted interval graphs is presented. It entails two phases. In the first phase, a set of searchlights with minimum guarding cost is identified and the search directions of all edges are assigned. To achieve this task, a new problem, called the edge-direction assignment problem, is first defined and the problem on weighted complete-split graphs is solved by the greedy strategy. Based on this computational result, the problem of finding the set of searchlights with minimum guarding cost and assigning the search directions of all edges is solved by the dynamic programming strategy. Then, in the second phase, the search time slots of each edge are determined on the basis of the results of the first phase and on some properties of interval graphs.     

An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs

We present a parallel algorithm for solving the minimum weighted completion time scheduling problem for transitive series parallel graphs. The algorithm takesO(log² n) time withO(n ³) processors on a CREW PRAM, wheren is the number of vertices of the input graph. This is the first NC algorithm for solving the problem.Research supported in part by NSF Grants CCR-9011214 and CCR-9205982.     

Approximation algorithm for coloring of dotted interval graphs

Dotted interval graphs were introduced by Aumann et al. [Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter, Z. Yakhini, Dotted interval graphs and high throughput genotyping, in: ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 339-348] as a generalization of interval graphs. The problem of coloring these graphs found application in high-throughput genotyping. Jiang [M. Jiang, Approximating minimum coloring and maximum independent set in dotted interval graphs, Information Processing Letters 98 (2006) 29-33] improves the approximation ratio of Aumann et al. [Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter, Z. Yakhini, Dotted interval graphs and high throughput genotyping, in: ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 339-348]. In this work we improve the approximation ratio of Jiang [M. Jiang, Approximating minimum coloring and maximum independent set in dotted interval graphs, Information Processing Letters 98 (2006) 29-33] and Aumann et al. [Y. Aumann, M. Lewenstein, O. Melamud, R. Pinter, Z. Yakhini, Dotted interval graphs and high throughput genotyping, in: ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pp. 339-348]. In the exposition we develop a generalization of the problem of finding the maximum number of non-attacking queens on a triangle.     

Solving shortest path problems with a weight constraint and replenishment arcs

This paper tackles a generalization of the weight constrained shortest path problem (WCSPP) in a directed network with replenishment arcs that reset the accumulated weight along the path to zero. Such situations arise, for example, in airline crew pairing applications, where the weight represents duty hours, and replenishment arcs represent crew overnight rests; and also in aircraft routing, where the weight represents time elapsed, or flight time, and replenishment arcs represent maintenance events. In this paper, we review the weight constrained shortest path problem with replenishment (WCSPP-R), develop preprocessing methods, extend existing WCSPP algorithms, and present new algorithms that exploit the inter-replenishment path structure. We present the results of computational experiments investigating the benefits of preprocessing and comparing several variants of each algorithm, on both randomly generated data, and data derived from airline crew scheduling applications.     

An optimal parallel algorithm for planar cycle separators

We present an optimal parallel algorithm for computing a cycle separator of ann-vertex embedded planar undirected graph inO(logn) time onn/logn processors. As a consequence, we also obtain an improved parallel algorithm for constructing a depth-first search tree rooted at any given vertex in a connected planar undirected graph in O(log² n) time on n/logn processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time complexities, but withn processors. Our algorithms run on a parallel random access machine that permits concurrent reads and concurrent writes in its shared memory and allows an arbitrary processor to succeed in case of a write conflict.A preliminary version of this paper appeared as Improved Parallel Depth-First Search in Undirected Planar Graphs in theProceedings of the Third Workshop on Algorithms and Data Structures, 1993, pp. 407–420.Supported in part by NSF Grant CCR-9101385.