A linear time and space algorithm for finding isomorphic subtrees of a binary tree

This paper shows that it is possible to find all isomorphic subtrees of a binary tree in linear time and space.     

A new parallel algorithm for rooting a tree

When an undirected tree,T, and a vertex,r, in the tree are given, the problem to transformT into a rooted tree withr as its root is considered. Using Euler tour and prefix sum, an optimal algorithm has been developed [2, 3]. We will present another parallel algorithm which is optimal also on EREW PRAM. Our approach reduces the given tree step by step by pruning and pointer jumping. That is, the tree structure is retained during algorithm processing such that another tree computations can be carried out in parallel.     

A computational study of the cutting plane tree algorithm for general mixed-integer linear programs

The cutting plane tree algorithm provides a finite procedure for solving general mixed-integer linear programs with bounded integer variables. The computational evidence provided in this work illustrates that this algorithm is powerful enough to close a significant fraction of the integrality gap for moderately sized MIPLIB instances.     

A polynomial-time algorithm for a class of linear complementarity problems

Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x 0,y 0,x _i y _i = 0 (i = 1, 2,,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n ³ L) arithmetic operations by tracing the path of centers,{(x, y) S: x _i y _i = (i = 1, 2,,n) for some > 0} of the feasible regionS = {(x, y) 0:y = Mx + q}, whereL denotes the size of the input data of the problem.     

A linear evolution equation without a common dense core for the generators

There exists a family{A(t);t≥0} of unbounded operators in a Banach spaceX such that the initial value problem

$u\text{'}(t)=A(t)\mathit{u}(t),\mathit{u}(0)=?(\text{'}=d/\mathit{d}\mathit{t})$

has a unique solution on [0, ∞) for each θ in a dense subset ofX, withu depending continuously on θ, and such that the intersection of the domain ofA(s) andA(t) is nowhere dense whenevers ≠ t.     

A linear algorithm for the domination number of a series-parallel graph

A vertex u in an undirected graph G = (V, E) is said to dominate all its adjacent vertices and itself. A subset D of V is a dominating set in G if every vertex in G is dominated by a vertex in D, and is a minimum dominating set in G if no other dominating set in G has fewer vertices than D. The domination number of G is the cardinality of a minimum dominating set in G.The problem of determining, for a given positive integer k and an undirected graph G, whether G has a dominating set D in G satisfying ¦D¦ ≤ k, is a well-known NP-complete problem. Cockayne have presented a linear time algorithm for finding a minimum dominating set in a tree. In this paper, we will present a linear time algorithm for finding a minimum dominating set in a series-parallel graph.     

A search tree algorithm for plant location problems

This paper deals with the classical plant location problem, by introducing a new algorithm based on a ranking procedure of all the possible combinations of plant locations. The ranking is obtained by introducing a properly defined search tree and by exploiting its structural properties, so that the algorithm suitably combines a search procedure on the tree with a ranking method. The number of subproblems to be examined is greatly reduced by the use of a stopping rule and a lower bound. The lower bound is given by the value of the objective function of a dual feasible solution for the transportation problem associated to each combination. Computational results for a set of real size problems with different data structures are finally discussed.     

A greedy algorithm for solving a certain class of linear programmes

If is a collection of subsets ofS andw is a nonnegative weight function onS, the problem of selecting a subset belonging to which has maximum weight is solved by a greedy-type algorithm forall w if and only if is the set of independent sets of a matroid. This result is then generalised to show that greedy-type algorithms select an optimum forall linear functionsc·x; x in some compact set andc > 0 if and only if the convex closure ofU is essentially a polymatroid. A byproduct of this is a new characterization of polymatroids.     

A one-phase algorithm for semi-infinite linear programming

We present an algorithm for solving a large class of semi-infinite linear programming problems. This algorithm has several advantages: it handles feasibility and optimality together; it has very weak restrictions on the constraints; it allows cuts that are not near the most violated cut; and it solves the primal and the dual problems simultaneously. We prove the convergence of this algorithm in two steps. First, we show that the algorithm can find an-optimal solution after finitely many iterations. Then, we use this result to show that it can find an optimal solution in the limit. We also estimate how good an-optimal solution is compared to an optimal solution and give an upper bound on the total number of iterations needed for finding an-optimal solution under some assumptions. This algorithm is generalized to solve a class of nonlinear semi-infinite programming problems. Applications to convex programming are discussed.     

A randomized algorithm for fixed-dimensional linear programming

We give a (Las Vegas) randomized algorithm for linear programming in a fixed dimensiond for which the expected computation time is , where lim _{d d} = 0. This improves the corresponding worst-case complexity, . The method is based on a recent idea of Clarkson. Two variations on the algorithm are examined briefly.     

A direct heuristic algorithm for linear programming

AnO(n ³) mathematically non-iterative heuristic procedure that needs no artificial variable is presented for solving linear programming problems. An optimality test is included. Numerical experiments depict the utility/scope of such a procedure.     

A new polynomial-time algorithm for linear programming

We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n ^3.5 L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n ^2.5). We prove that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property. The ratio of the radius of the smallest sphere with center a′, containingP′ to the radius of the largest sphere with center a′ contained inP′ isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time. This is a substantially revised version of the paper presented at the Symposium on Theory of Computing, Washington D. C., April 1984.     

A linear algorithm for computing the visibility polygon from a point

The hidden-line problem in two dimensions is a recurrent problem in computer graphics. In this paper a linear, and thus optimal, algorithm is exhibited for solving this problem.     

A linear algorithm for nonhomogeneous spectra of numbers

Given a sequence of integers [a_i]_i=1ⁿ, an O(n) iterative algorithm is presented which decides whether there exist real numbers α and β such that a_i = [iα + β] (1 ? i ? n). In fact, the linear algorithm computes the partial quotients of the continued fraction expansions of $\text{d}$ and $\text{d}$ such that $\text{d < α <}\text{d}$ if and only if a_i = [iα + β] (1 ? i ? n) for suitable β = β(α).     

A strongly polynomial algorithm for linear systems having a binary solution

This paper proposes a strongly polynomial algorithm which either finds a solution of a linear system Ax?=?b, 0 ≤?x?≤?1, or correctly decides that the system has no 0,1-solutions. The algorithm can be used as the basis for the construction of a polynomial algorithm for linear programming.     

A tree search algorithm for the multi-commodity location problem

The multi-commodity location problem is an extension of the simple plant location problem. The problem is to decide on locations of facilities to meet customer demands for several commodities in such a way that total fixed plus variable costs are minimized. Only one commodity may be supplied from any location.In this paper a primal and a dual heuristic for producing good bounds are presented. A method of improving these bounds by using a new Lagrangean relaxation for the problem is also presented. Computational results with problems taken from the literature are provided.     

A dynamic programming algorithm for the tree mapping problem

In the graph mapping problem two graphs and a cost function are given as input and the goal is to find a minimum cost mapping of the vertex set of one graph into the vertex set of the other graph. In this paper we introduce a dynamic programming algorithm for the tree mapping problem (i.e., the variant of the problem in which the input graphs are trees), which is still NP-hard, and evaluate its performance with computational experiments.     

A subexponential algorithm for the coloured tree partition problem

Given a tree of n vertices and a list of feasible colours for each vertex, the coloured tree partition problem (CTPP) consists in partitioning the tree into p vertex-disjoint subtrees of minimum total cost, and assigning to each subtree a different colour, which must be feasible for all of its vertices. The problem is strongly NP-hard on general graphs, as well as on grid and bipartite graphs. This paper deals with the previously open case of tree graphs, showing that it is strongly NP-complete to determine whether a feasible solution exists. It presents reduction, decomposition and bounding procedures to simplify the problem and an exact algorithm of complexity (with ) for the special case in which a vertex of each subtree is given.