An optimal algorithm for the maximum-density path in a tree

We studied the problem of finding the maximum-density path in a tree. By spine decomposition and a linear-time algorithm for the maximum density segment problem, we developed an O(nlogn) time algorithm, which improves the previously best result of O(nlog²n) by using centroid decomposition. We also show the time complexity is optimal in the algebraic computation tree model.     

A linear algorithm for the number of degree constrained subforests of a tree

Recent work of Farrell is concerned with determining the total number of ways in which one can cover the vertices of a tree T with vertex disjoint paths. Such path covers are spanning subforests in which each vertex is restricted to have degree at most two. If b: V(T)→N is a positive integer-valued function, then finding a b-matching is equivalent to finding a spanning subgraph in which the degree of each vertex v is at most b(v). A linear-time algorithm for determining the number of b-matching in a tree is presented.     

Optimal one-page tree embeddings in linear time

In the minimum linear arrangement problem one wishes to assign distinct integers to the vertices of a given graph so that the sum of the differences (in absolute value) across the edges of the graph is minimized. This problem is known to be NP-complete for the class of all graphs, but polynomial for trees—algorithms of time complexity O(n^2.2) and O(n^1.6) were given by Shiloach [SIAM J. Comput. 8 (1979) 15-32] and Chung [Comput. Math. Appl. 10 (1984) 43-60], respectively. We present a linear-time algorithm for finding the optimal embedding (arrangement) in a restricted but important class of embeddings called one-page embeddings.¹     

On the red/blue spanning tree problem

A geometric spanning tree of a point set S is a tree whose vertex set is S and whose edge set is a set of non-crossing straight line segments with endpoints in S. Given a set of red points and a set of blue points in the plane, the red/blue spanning tree problem is to find a geometric spanning tree for red points and a geometric spanning tree for blue points such that the number of crossing points of the two trees is a minimum. If no three points are collinear, we show that the minimum number of crossing points is completely determined by the number of maximal red (or blue) chains on the convex hull of all red points and blue points. We design an optimal algorithm for constructing a geometric spanning tree of all the red points and a geometric spanning tree of all the blue points with the minimum number of crossing points. If collinear points are allowed, we prove that the problem of deciding whether there exists a geometric spanning path of all the red points and a geometric spanning path of all the blue points without crossing is NP-complete.     

Optimal edge ranking of trees in polynomial time

An edge ranking of a graph is a labeling of the edges using positive integers such that all paths between two edges with the same label contain an intermediate edge with a higher label. An edge ranking isoptimal if the highest label used is as small as possible. The edge-ranking problem has applications in scheduling the manufacture of complex multipart products; it is equivalent to finding the minimum height edge-separator tree. In this paper we give the first polynomial-time algorithm to find anoptimal edge ranking of a tree, placing the problem inP. An interesting feature of the algorithm is an unusual greedy procedure that allows us to narrow an exponential search space down to a polynomial search space containing an optimal solution. AnNC algorithm is presented that finds an optimal edge ranking for trees of constant degree. We also prove that a natural decision problem emerging from our sequential algorithm isP-complete.The research of P. de la Torre was partially supported by NSF Grant CCR-9010445. R. Greenlaw's research was partially supported by NSF Grant CCR-9209184. The research of A. A. Schäffer was partially supported by NSF Grant CCR-9010534.Subsequent to the acceptance of this paper, Zhou and Nishizeki found faster algorithms for optimal edge ranking of trees, first reducing the time toO(n²) [22] and then toO(n logn) [23].     

Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree

The vertex updating problem for a minimum spanning tree (MST) is defined as follows: Given a graphG=(V, E _G) and an MSTT forG, find a new MST forG to which a new vertexz has been added along with weighted edges that connectz with the vertices ofG. We present a set of rules that produce simple optimal parallel algorithms that run inO(lgn) time usingn/lgn EREW PRAM processors, wheren=¦V¦. These algorithms employ any valid tree-contraction schedule that can be produced within the stated resource bounds. These rules can also be used to derive simple linear-time sequential algorithms for the same problem. The previously best-known parallel result was a rather complicated algorithm that usedn processors in the more powerful CREW PRAM model. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem: Update a given MST whenk new vertices are introduced simultaneously. This problem is solved inO(lgk·lgn) parallel time using (k·n)/(lgk·lgn) EREW PRAM processors. This is optimal for graphs having (kn) edges.Part of this work was done while P. Metaxas was with the Department of Mathematics and Computer Science, Dartmouth College.     

A 2-approximation NC algorithm for connected vertex cover and tree cover

The connected vertex cover problem is a variant of the vertex cover problem, in which a vertex cover is additional required to induce a connected subgraph in a given connected graph. The problem is known to be NP-hard and to be at least as hard to approximate as the vertex cover problem is. While several 2-approximation NC algorithms are known for vertex cover, whether unweighted or weighted, no parallel algorithm with guaranteed approximation is known for connected vertex cover. Moreover, converting the existing sequential 2-approximation algorithms for connected vertex cover to parallel ones results in RNC algorithms of rather high complexity at best.In this paper we present a 2-approximation NC (and RNC) algorithm for connected vertex cover (and tree cover). The NC algorithm runs in O(log²n) time using O(Δ²(m+n)/logn) processors on an EREW-PRAM, while the RNC algorithm runs in O(logn) expected time using O(m+n) processors on a CRCW-PRAM, when a given graph has n vertices and m edges with maximum vertex degree of Δ.     

On exact solutions to the Euclidean bottleneck Steiner tree problem

We study the Euclidean bottleneck Steiner tree problem: given a set P of n points in the Euclidean plane and a positive integer k, find a Steiner tree with at most k Steiner points such that the length of the longest edge in the tree is minimized. This problem is known to be NP-hard even to approximate within ratio and there was no known exact algorithm even for k=1 prior to this work. In this paper, we focus on finding exact solutions to the problem for a small constant k. Based on geometric properties of optimal location of Steiner points, we present an optimal -time exact algorithm for k=1 and an O(n²)-time algorithm for k=2. Also, we present an optimal -time exact algorithm for any constant k for a special case where there is no edge between Steiner points.     

Efficient Parallel Algorithms for Permutation Graphs

In this paper, we present optimal O(log n) time, O(n/log n) processor EREW PRAM parallel algorithms for finding the connected components, cut vertices, and bridges of a permutation graph. We also present an O(log n) time, O(n) processor, CREW PRAM model parallel algorithm for finding a Breadth First Search (BFS) spanning tree of a permutation graph rooted at vertex 1 and use the same to derive an efficient parallel algorithm for the All Pairs Shortest Path problem on permutation graphs.     

Algorithms for path medi-centers of a tree

We consider the problem of finding an optimal location of a path on a tree, using combinations of minisum and minimax criteria (which are respectively maximal distance and average distance from the path to customers situated at the vertices). The case of linear combination of the two criteria and the case where one criterion is optimized subject to a restriction on the value of the other are considered and linear-time algorithms for these problems are presented. It is proved that the representation of the set of Pareto-optimal paths in the space of criteria has cardinality not greater than n−1, where n is the number of vertices of the tree, and can be obtained in O(n log n) time, although the number of Pareto-optimal paths can be O(n²)     

Improving on-line construction of two-dimensional suffix trees for square matrices

The two-dimensional (2-D) suffix tree of an n×n square matrix A is a compacted trie that represents all square submatrices of A. We consider constructing 2-D suffix trees on-line, which means, instead of giving the whole matrix A in advance, A is separated and each part of A is given at different time as algorithms proceed. In general, developing an on-line algorithm is more difficult than developing an off-line algorithm. Moreover, the smaller the input grain size is, the harder it is to develop an on-line algorithm. In the case of 2-D suffix tree construction, dealing with a character at a time is harder than dealing with a row or a column at a time.In this paper we propose a randomized linear-time algorithm for constructing 2-D suffix trees on-line. This algorithm is superior to previous algorithms in two ways: (1) This is the first linear-time algorithm for constructing 2-D suffix trees on-line. Although there have been some linear-time algorithms for off-line construction, there were no linear-time algorithms for on-line construction. (2) We deal with the most fine-grain on-line case, i.e., our algorithm can construct a 2-D suffix tree even though only one character of A is given at a time, while previous on-line algorithms require at least a row and/or a column at a time.     

Vertex rankings of chordal graphs and weighted trees

In this paper we consider the vertex ranking problem of weighted trees. We show that this problem is strongly NP-hard. We also give a polynomial-time reduction from the problem of vertex ranking of weighted trees to the vertex ranking of (simple) chordal graphs, which proves that the latter problem is NP-hard. In this way we solve an open problem of Aspvall and Heggernes. We use this reduction and the algorithm of Bodlaender et al.'s for vertex ranking of partial k-trees to give an exact polynomial-time algorithm for vertex ranking of a tree with bounded and integer valued weight functions. This algorithm serves as a procedure in designing a PTAS for weighted vertex ranking problem of trees with bounded weight functions.     

Rectilinear steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors

We study the application of the geographic nearest neighbor approach to two problems. The first problem is the construction of an approximately minimum length rectilinear Steiner tree for a set ofn points in the plane. For this problem, we introduce a variation of a subgraph of sizeO(n) used by YaO [31] for constructing minimum spanning trees. Using this subgraph, we improve the running times of the heuristics discussed by Bern [6] fromO(n ² log n) toO(n log² n). The second problem is the construction of a rectilinear minimum spanning tree for a set ofn noncrossing line segments in the plane. We present an optimalO(n logn) algorithm for this problem. The rectilinear minimum spanning tree for a set of points can thus be computed optimally without using the Voronoi diagram. This algorithm can also be extended to obtain a rectilinear minimum spanning tree for a set of nonintersecting simple polygons.The results in this paper are a part of Y. C. Yee's Ph.D. thesis done at SUNY at Albany. He was supported in part by NSF Grants IRI-8703430 and CCR-8805782. S. S. Ravi was supported in part by NSF Grants DCI-86-03318 and CCR-89-05296.     

An efficient algorithm for maxdominance,with applications

Given a planar setS ofn points,maxdominance problems consist of computing, for everyp εS, some function of the maxima of the subset ofS that is dominated byp. A number of geometric and graph-theoretic problems can be formulated as maxdominance problems, including the problem of computing a minimum independent dominating set in a permutation graph, the related problem of finding the shortest maximal increasing subsequence, the problem of enumerating restricted empty rectangles, and the related problem of computing the largest empty rectangle. We give an algorithm for optimally solving a class of maxdominance problems. A straightforward application of our algorithm yields improved time bounds for the above-mentioned problems. The techniques used in the algorithm are of independent interest, and include a linear-time tree computation that is likely to arise in other contexts.     

Variable neighborhood search for the cost constrained minimum label spanning tree and label constrained minimum spanning tree problems

Given an undirected graph whose edges are labeled or colored, edge weights indicating the cost of an edge, and a positive budget B, the goal of the cost constrained minimum label spanning tree (CCMLST) problem is to find a spanning tree that uses the minimum number of labels while ensuring its cost does not exceed B. The label constrained minimum spanning tree (LCMST) problem is closely related to the CCMLST problem. Here, we are given a threshold K on the number of labels. The goal is to find a minimum weight spanning tree that uses at most K distinct labels. Both of these problems are motivated from the design of telecommunication networks and are known to be NP-complete [15].In this paper, we present a variable neighborhood search (VNS) algorithm for the CCMLST problem. The VNS algorithm uses neighborhoods defined on the labels. We also adapt the VNS algorithm to the LCMST problem. We then test the VNS algorithm on existing data sets as well as a large-scale dataset based on TSPLIB [12] instances ranging in size from 500 to 1000 nodes. For the LCMST problem, we compare the VNS procedure to a genetic algorithm (GA) and two local search procedures suggested in [15]. For the CCMLST problem, the procedures suggested in [15] can be applied by means of a binary search procedure. Consequently, we compared our VNS algorithm to the GA and two local search procedures suggested in [15]. The overall results demonstrate that the proposed VNS algorithm is of high quality and computes solutions rapidly. On our test datasets, it obtains the optimal solution in all instances for which the optimal solution is known. Further, it significantly outperforms the GA and two local search procedures described in [15].     

Computing an st-numbering

Lempel, Even and Cederbaum proved the following result: Given any edge {st} in a biconnected graph G with n vertices, the vertices of G can be numbered from 1 to n so that vertex s receives number 1, vertex t receives number n, and any vertex except s and t is adjacent both to a lower-numbered and to a higher-numbered vertex (we call such a numbering an st-numbering for G). They used this result in an efficient algorithm for planarity-testing. Here we provide a linear-time algorithm for computing an st-numbering for any biconnected graph. This algorithm can be combined with some new results by Booth and Lueker to provide a linear-time implementation of the Lempel-Even-Cederbaum planarity-testing algorithm.     

On vertex ranking of a starlike graph

A vertex coloring c:V→{1,2,…,t} of a graph G=(V,E) is a vertex t-ranking if for any two vertices of the same color every path between them contains a vertex of larger color. The vertex ranking number χ_r(G) is the smallest value of t such that G has a vertex t-ranking. A χ_r(G)-ranking of G is said to be an optimal vertex ranking. In this paper, we present an O(|V|+|E|) time algorithm for finding an optimal vertex ranking of a starlike graph G=(V,E). Our result implies that an optimal vertex ranking of a split graph can be computed in linear time.     

A Linear Time Algorithm for Computing Minmax Regret 1-Median on a Tree Network

In a model of facility location problem, the uncertainty in the weight of a vertex is represented by an interval of weights, and the objective is to minimize the maximum “regret.” The most efficient algorithm previously known for finding the minmax regret 1-median in a tree network with nonnegative vertex weights takes O(nlogn) time. We improve it to O(n), settling the open problem posed by Brodal et al. (Oper. Res. Lett. 36:14–18, 2008).     

The pos/neg-weighted 1-median problem on tree graphs with subtree-shaped customers

In this paper we consider the pos/neg-weighted median problem on a tree graph where the customers are modeled as continua subtrees. We address the discrete and continuous models, i.e., the subtrees’ boundary points are all vertices, or possibly inner points of an edge, respectively. We consider two different objective functions. If we minimize the overall sum of the minimum weighted distances of the subtrees from the facilities, there exists an optimal solution satisfying a generalized vertex optimality property, e.g., there is an optimal solution such that all facilities are located at vertices or the boundary points of the subtrees. Based on this property we devise a polynomial time algorithm for the pos/neg-weighted 1-median problem on a tree with subtree-shaped customers.     

Degree constrained minimum spanning tree problem: a learning automata approach

Degree-constrained minimum spanning tree problem is an NP-hard bicriteria combinatorial optimization problem seeking for the minimum weight spanning tree subject to an additional degree constraint on graph vertices. Due to the NP-hardness of the problem, heuristics are more promising approaches to find a near optimal solution in a reasonable time. This paper proposes a decentralized learning automata-based heuristic called LACT for approximating the DCMST problem. LACT is an iterative algorithm, and at each iteration a degree-constrained spanning tree is randomly constructed. Each vertex selects one of its incident edges and rewards it if its weight is not greater than the minimum weight seen so far and penalizes it otherwise. Therefore, the vertices learn how to locally connect them to the degree-constrained spanning tree through the minimum weight edge subject to the degree constraint. Based on the martingale theorem, the convergence of the proposed algorithm to the optimal solution is proved. Several simulation experiments are performed to examine the performance of the proposed algorithm on well-known Euclidean and non-Euclidean hard-to-solve problem instances. The obtained results are compared with those of best-known algorithms in terms of the solution quality and running time. From the results, it is observed that the proposed algorithm significantly outperforms the existing method.