An efficient pram algorithm for maximum-weight independent set on permutation graphs

An efficient parallel algorithm is presented to find a maximum weight independent set of a permutation graph which takesO (logn) time usingO (n ²/logn) processors on an EREW PRAM, provided the graph has at mostO (n) maximal independent sets. The best known parallel algorithm takesO (log² n) time andO (n ³/logn) processors on a CREW PRAM.     

An optimal pram algorithm for a spanning tree on trapezoid graphs

LetG be a graph withn vertices andm edges. The problem of constructing a spanning tree is to find a connected subgraph ofG withn vertices andn?1 edges. In this paper, we propose anO(logn) time parallel algorithm withO(n/logn), processors on an EREW PRAM for constructing a spanning tree on trapezoid graphs.     

An efficient algorithm to solve connectivity problem on trapezoid graphs

The connectivity problem is a fundamental problem in graph theory. The best known algorithm to solve the connectivity problem on general graphs withn vertices andm edges takesO(K(G)mn ^1.5) time, whereK(G) is the vertex connectivity ofG. In this paper, an efficient algorithm is designed to solve vertex connectivity problem, which takesO(n ²) time andO(n) space for a trapezoid graph.     

The Hamiltonian problem on distance-hereditary graphs

In this paper, we first present an O(n+m)-time sequential algorithm to solve the Hamiltonian problem on a distance-hereditary graph G, where n and m are the number of vertices and edges of G, respectively. This algorithm is faster than the previous best known algorithm for the problem which takes O(n²) time. We also give an efficient parallel implementation of our sequential algorithm. Moreover, if G is represented by its decomposition tree form, the problem can be solved optimally in O(logn) time using O((n+m)/logn) processors on an EREW PRAM.     

A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ^*/logΔ^*) of the optimum in O(mnlogn)-time, where Δ^* is the minimum k such that there is a spanning tree of the graph with maximum degree k.     

Finding a minimum independent dominating set in a permutation graph

We give a linear time reduction of the problem of finding a minimum independent dominating set in a permutation graph, into that of finding a shortest maximal increasing subsequence. We then give an O(n log²n)-time algorithm for solving the second (and hence the first) problem. This improves on the O(n³)-time algorithm given in [4] for solving the problem of finding a minimum independent dominating set in a permutation graph.     

A trust region method for solving the decentralized static output feedback design problem

The shortest-paths problem is a fundamental problem in graph theory and finds diverse applications in various fields. This is why shortest path algorithms have been designed more thoroughly than any other algorithm in graph theory. A large number of optimization problems are mathematically equivalent to the problem of finding shortest paths in a graph. The shortest-path between a pair of vertices is defined as the path with shortest length between the pair of vertices. The shortest path from one vertex to another often gives the best way to route a message between the vertices. This paper presents anO(n ²) time sequential algorithm and anO(n ²/p+logn) time parallel algorithm on EREW PRAM model for solving all pairs shortest paths problem on circular-arc graphs, wherep andn represent respectively the number of processors and the number of vertices of the circular-arc graph.     

An optimal parallel connectivity algorithm

A synchronized parallel algorithm of depth O(n²/p) for p (≤n²/log²n) processors is given for the problem of computing connected components of an undirected graph. The speed-up of this algorithm is optimal in the sense that the depth of the algorithm is of the order of the running time of the fastest known sequential algorithm over the number of processors used.     

On-line coloringk-colorable graphs

We show that for anyk, there exists an on-line algorithm that will color anyk-colorable graph onn vertices withO(n ^1−1/k! ) colors. This improves the previous best upper bound ofO(nlog^(2k−3) n/log^(2k−4) n) due to Lovász, Saks, and Trotter. In the special casesk=3 andk=4 we obtain on-line algorithms that useO(n ^2/3log^1/3 n) andO(n ^5/6log^1/6 n) colors, respectively.     

A new strongly polynomial dual network simplex algorithm

This paper presents a new dual network simplex algorithm for the minimum cost network flow problem. The algorithm works directly on the original capacitated network and runs in O(mn(m +n logn) logn) time for the network withn nodes andm arcs. This complexity is better than the complexity of Orlin, Plotkin and Tardos’ (1993) dual network simplex algorithm by a factor ofm/n.     

About strongly polynomial time algorithms for quadratic optimization over submodular constraints

We present new strongly polynomial algorithms for special cases of convex separable quadratic minimization over submodular constraints. The main results are: an O(NM log(N ²/M)) algorithm for the problemNetwork defined on a network onM arcs andN nodes; an O(n logn) algorithm for thetree problem onn variables; an O(n logn) algorithm for theNested problem, and a linear time algorithm for theGeneralized Upper Bound problem. These algorithms are the best known so far for these problems. The status of the general problem and open questions are presented as well.This research has been supported in part by ONR grant N00014-91-J-1241.Corresponding author.     

A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm

Recently, É. Tardos gave a strongly polynomial algorithm for the minimum-cost circulation problem and solved the open problem posed in 1972 by J. Edmonds and R.M. Karp. Her algorithm runs in O(m ² T(m, n) logm) time, wherem is the number of arcs,n is the number of vertices, andT(m, n) is the time required for solving a maximum flow problem in a network withm arcs andn vertices. In the present paper, taking an approach that is a dual of Tardos's, we also give a strongly polynomial algorithm for the minimum-cost circulation problem. Our algorithm runs in O(m ² S(m, n) logm) time and reduces the computational complexity, whereS(m, n) is the time required for solving a shortest path problem with a fixed origin in a network withm arcs,n vertices, and a nonnegative arc length function. The complexity is the same as that of Orlin's algorithm, recently developed by efficiently implementing the Edmonds-Karp scaling algorithm.     

A parallel search algorithm for directed acyclic graphs

A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for therpostorder traversal of an ordered tree. Each of these traversal algorithms has a time complexity ofO(logn) whenO(n) processors are used,n being the number of vertices in the tree. The parallel depth-first search algorithm for a directed acyclic graphG withn vertices has a time complexity ofO((logn)²) whenO(n ^2.81/logn) processors are used.     

An O(mlog logD) algorithm for shortest paths

A technique for implementing Dijkstra's shortest paths algorithm is proposed. This method runs in O(mlog logD) time in the worst case, where m is the number of edges and D the length of the longest edge in the graph.     

Efficient parallel recognition of cographs

In this paper, we establish structural properties for the class of complement reducible graphs or cographs, which enable us to describe efficient parallel algorithms for recognizing cographs and for constructing the cotree of a graph if it is a cograph; if the input graph is not a cograph, both algorithms return an induced P₄. For a graph on n vertices and m edges, both our cograph recognition and cotree construction algorithms run in time and require O((n+m)/logn) processors on the EREW PRAM model of computation. Our algorithms are motivated by the work of Dahlhaus (Discrete Appl. Math. 57 (1995) 29–44) and take advantage of the optimal O(logn)-time computation of the co-connected components of a general graph (Theory Comput. Systems 37 (2004) 527–546) and of an optimal O(logn)-time parallel algorithm for computing the connected components of a cograph, which we present. Our results improve upon the previously known linear-processor parallel algorithms for the problems (Discrete Appl. Math. 57 (1995) 29–44; J. Algorithms 15 (1993) 284–313): we achieve a better time-processor product using a weaker model of computation and we provide a certificate (an induced P₄) whenever our algorithms decide that the input graphs are not cographs.     

A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs

1.IntroductionLetG=(V,E,W)beaconnected,weightedandundirectedgraph,VeEE,w(e)(相似文献   

Stability in circular arc graphs

An algorithm is presented which finds a maximum stable set of a family of n arcs on a circle in O(nlogn) time given the arcs as an unordered list of their endpoints or in O(n) time if they are already sorted. If we are given only the circular arc graph without a circular arc representation for it, then a maximum stable set can be found in O(n + δe) time where n, e, and δ are the number of vertices, edges, and minimum vertex degree, respectively. Our algorithms are based on a simple neighborhood reduction theorem which allows one to reduce any circular arc graph to a special canonical form.     

The analysis of a nested dissection algorithm

Summary Nested dissection is an algorithm invented by Alan George for preserving sparsity in Gaussian elimination on symmetric positive definite matrices. Nested dissection can be viewed as a recursive divide-and-conquer algorithm on an undirected graph; it usesseparators in the graph, which are small sets of vertices whose removal divides the graph approximately in half. George and Liu gave an implementation of nested dissection that used a heuristic to find separators. Lipton and Tarjan gave an algorithm to findn ^1/2-separators in planar graphs and two-dimensional finite element graphs, and Lipton, Rose, and Tarjan used these separators in a modified version of nested dissection, guaranteeing bounds ofO (n logn) on fill andO(n ^3/2) on operation count. We analyze the combination of the original George-Liu nested dissection algorithm and the Lipton-Tarjan planar separator algorithm. This combination is interesting because it is easier to implement than the Lipton-Rose-Tarjan version, especially in the framework of existïng sparse matrix software. Using some topological graph theory, we proveO(n logn) fill andO(n ^3/2) operation count bounds for planar graphs, twodimensional finite element graphs, graphs of bounded genus, and graphs of bounded degree withn ^1/2-separators. For planar and finite element graphs, the leading constant factor is smaller than that in the Lipton-Rose-Tarjan analysis. We also construct a class of graphs withn ^1/2-separators for which our algorithm does not achieve anO(n logn) bound on fill.The work of this author was supported in part by the Hertz Foundation under a graduate fellowship and by the National Science Foundation under Grant MCS 82-02948The work of this author was supported in part by the National Science Foundation under Grant MCS 78-26858 and by the Office of Naval Research under Contract N00014-76-C-0688     

On the parallel computation of the biconnected and strongly connected co-components of graphs

In this paper, we consider the problems of co-biconnectivity and strong co-connectivity, i.e., computing the biconnected components and the strongly connected components of the complement of a given graph. We describe simple sequential algorithms for these problems, which work on the input graph and not on its complement, and which for a graph on n vertices and m edges both run in optimal O(n+m) time. Our algorithms are not data structure-based and they employ neither breadth-first-search nor depth-first-search.Unlike previous linear co-biconnectivity and strong co-connectivity sequential algorithms, both algorithms admit efficient parallelization. The co-biconnectivity algorithm can be parallelized resulting in an optimal parallel algorithm that runs in time using processors. The strong co-connectivity algorithm can also be parallelized to yield an -time and O(m^1.188/logn)-processor solution. As a byproduct, we obtain a simple optimal O(logn)-time parallel co-connectivity algorithm.Our results show that, in a parallel process environment, the problems of computing the biconnected components and the strongly connected components can be solved with better time-processor complexity on the complement of a graph rather than on the graph itself.     

A Near-Quadratic Algorithm for Fence Design

A part feeder is a mechanism that receives a stream of identical parts in arbitrary orientations and outputs them oriented the same way. Various sensorless part feeders have been proposed in the literature. The feeder we consider consists of a sequence of fences that extend partway across a conveyor belt; a polygonal part P carried by the belt is reoriented by each fence it encounters. We present an O(m + n² log³n)-time algorithm to compute a sequence of fences that uniquely orients P, if one exists, where m is the total number of vertices and n is the number of stable edges of P. We reduce the problem to searching for a path in a state graph that has O(n³) edges. By exploiting various geometric properties of this graph, we show that it can be represented implicitly and that a desired path can be computed in O(m + n² log³n) time. We believe that our technique is quite general and could be applicable to other part-manipulation problems as well.