We consider the problem of scheduling tasks on multiprocessor architectures in the presence of communication delays. Given a set of dependent tasks, the scheduling problem is to allocate the tasks to processors such that the pre-specified precedence constraints among the tasks are obeyed and certain cost-measures (such as the computation time) are minimized. Several cases of the scheduling problem have been proven to be NP-complete. Nevertheless, there are polynomial time algorithms for interesting special cases of the general scheduling problem. Most of these results, however, do not take into consideration the delays due to message passing among processors. In this paper we study the increase in time complexity of scheduling problems due to the introduction of communication delays. In particular, we address the open problem of scheduling Out-forests (In-forests) in a multiprocessor system of m identical processors when communication delays are considered. The corresponding problem of scheduling Out-forests (In-forests) without communication delays admits an elegant polynomial time solution as presented first by Hu in 1961; however, the problem in the presence of communication delays has remained unsolved. We present here first known polynomial time algorithms for the computation of the optimal schedule when the number of available processors is given and bounded and both computation and communication delays are assumed to take one unit of time. Furthermore, we present a linear-time algorithm for computing a near-optimal schedule for unit-delay out-forests. The schedule's length exceeds the optimum by no more than (m-2) time units, where m is the number of processors. Hence for two processors the computed schedule is strictly optimum.

Article Free Access Share on Aligning sequences via an evolutionary tree: complexity and approximation Authors: Tao Jiang Department of Computer Science, McMaster University, Hamilton, Ont. L8S 4K1, Canada Department of Computer Science, McMaster University, Hamilton, Ont. L8S 4K1, CanadaView Profile , Eugene L. Lawler Computer Science Division, University of California, Berkeley, CA Computer Science Division, University of California, Berkeley, CAView Profile , Lusheng Wang McMaster University, Hamilton, Ontario L8S 4K1, Canada McMaster University, Hamilton, Ontario L8S 4K1, CanadaView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994 Pages 760–769https://doi.org/10.1145/195058.195454Online:23 May 1994Publication History 33citation291DownloadsMetricsTotal Citations33Total Downloads291Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The k differences approximate string matching problem specifies a text string of length n, a pattern string of length m, and the number k of differences (insertions, deletions, substitutions) allowed in a match, and asks for every location in the text where a match occurs. Previous algorithms required at least O(nk) time. When k is as large as a fraction of m, no substantial progress has been made over O(nm) dynamic programming. The authors have investigated much faster algorithms for restricted cases of the problem, such as when the text string is random and errors are not too frequent. They have devised an algorithm that, for k>

The problem of constructing makespan-optimal preemptive schedules for n independent jobs on m unrelated parallel processors is discussed. For the case of two processors, we present a linear time algorithm to construct optimal schedules. The schedules generated by our algorithm have at most two preemptions. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

A general problem in computational graph theory is that of finding an optimal subgraph H of a given weighted graph G. The matching problem (which is easy) and the traveling salesman problem (which is not) are well known examples of this general problem. In the literature one can also find a variety of ad hoc algorithms for solving certain special cases in linear time. We present a general methodology for constructing linear time algorithms in the case that the graph G is defined by certain rules of composition (as are trees, series parallel graphs, and outerplanar graphs) and the desired subgraph H satisfies a "regular" property (such as independence or matching). This methodology is applied to obtain a linear time algorithm for computing the irredundance number of a tree, a problem for which no polynomial time algorithm was previously known.

We present a linear-time algorithm to recognize the class of vertex series-parallel (VSP) digraphs. Our method is based on the relationship between VSP digraphs and the class of edge series-parallel multidigraphs. As a byproduct of our analysis, we obtain efficient methods to compute the transitive closure and transitive reduction of VSP digraphs, and to test isomorphism of minimal VSP digraphs.

Suppose that an independence system $(E,\mathcal {I})$ is characterized by a subroutine which indicates in unit time whether or not a given subset of E is independent. It is shown that there is no algorithm for generating all the K maximal independent sets of such an independence system in time polynomial in $|E|$ and K, unless $\mathcal {P} = \mathcal {NP}$. However, it is possible to apply ideas of Paull and Unger and of Tsukiyama et al. to obtain polynomial-time algorithms for a number of special cases, e.g. the efficient generation of all maximal feasible solutions to a knapsack problem. The algorithmic techniques bear an interesting relationship with those of Read for the enumeration of graphs and other combinatorial configurations.

We present an algorithm that recognizes the class of General Series Parallel digraphs and runs in time proportional to the size of its input. To perform this recognition task it is necessary to compute the transitive reduction and transitive closure of any General Series Parallel digraph. Our analysis is based on the relationship between General Series Parallel digraphs and a class of well known models of electrical networks.

It IS shown that certain problems of optimal preemptive scheduling of unrelated parallel processors can be formulated and solved as hnear programming problems As a by-product of the linear programming formulaUons of these problems, upper bounds are obtained on the number of preempuons required for optimal schedules In particular it is shown that no more than O(m 2) preemptions are necessary, m order to schedule n jobs on m unrelated processors so as to minimize makespan

Fully polynomial approximation algorithms for knapsack problems are presented. These algorithms are based on ideas of Ibarra and Kim, with modifications which yield better time and space bounds, and also tend to improve the practicality of the procedures. Among the principal improvements are the introduction of a more efficient method of scaling and the use of a median-finding routine to eliminate sorting. The 0-1 knapsack problem, for n items and accuracy ε ≫ 0, is solved in (n log(1/ε) + 1/ε4) time and 0(n + 1/ε3) space. The time bound is reduced to 0(n + 1/ε3) for the "unbounded" knapsack problem. For the "subset-sum" problem, 0(n + 1/ε3) time and 0(n + 1/ε2) space, or 0(n + 1/ε2 log (1/ε)) time and space, are achieved. The "multiple choice" problem, with m equivalence classes, is solved in 0(nm2/ε) time and space.

Abstract A hypergraph is a combinatorial structure with nodes and arcs, similar to an ordinary „linear”︁ graph, except that arcs are incident to arbitrary subsets of nodes, instead of pairs of nodes. Cutsets of hypergraphs are defined in a natural way, and it is shown that optimal cutsets can be found by means of a network flow computation. The optimal cutset computation can be used to generate a family of subsets of nodes, which we call LS sets. Intuitively, an LS set is a subset of nodes that are more strongly connected to each other than to nodes in the complementary set. LS sets are useful for constructing optimal or near‐optimal partitions of the nodes. A polynomial‐bounded partitioning algorithm is presented, and various applications are suggested.

Wiring schemes which exploit the potential of modern integrated circuit technology are likely to exhibit a high degree of " periodicity," as well as various other attributes. The first contribution of this paper is to formulate a precise definition of periodicity in terms of a graph-theoretic model originated by Yoeli. Roughly speaking, an infinite graph is said to be periodic if it can be generated from a finite template which is moved (periodically) from point to point in the plane. This definition is interesting and useful, and generalizes nicely to infinite graphs in n-space.

An important aspect of the packaging of digital networks is the allocation of logic gates to modules such that a predetermined objective function is minimized. In order to develop techniques for this partitioning of a logic network we have considered the following problem: Given an acyclic combinational network composed of various primitive blocks such as NOR gates, assume that a maximum of M gates can be "clustered" together into larger modules, and that a maximum of P pins can be accommodated in each larger module. Assume also that in a network composed of such larger modules, no delay is encountered on the interconnections linking two gates internal to a module and a delay of one time unit is encountered on interconnections linking two gates in different modules . Find an easily applied algorithm that will result in a network such that the maximum delay through the network is minimized.

An approach to the problem of multilevel Boolean minimization is described.The conventional prime implicant is generalized to the multilevel case, and the properties of multilevel prime implicants are investigated.A systematic procedure for computing multilevel prime implicants is described, and several examples are worked out.It is shown how ,'absolutely minimal" forms can be obtained by carrying out multilevel minimization to a sutSciently large number of levels.This constitutes a major revision of the paper, "Minimal Boolean Expressions with ~[ore than Two Levels of Sums and Products," presented at the Third Annual Symposium ~r~ Switching Circuit Theory and Logical Design, AIEE Fall General Meeting, Chicago, October 1962.The revision was supported by Air Force Contract 33(657)-7811.

A parenthesis-free notation is introduced for the representation of series-parallel switching networks. The notation facilitates the calculation of circuit parameters and permits an unambiguous characterization of the circuit topology. Given certain criteria for feasibility of a switching network related to the circuit parameter values, it is shown how an infeasible series-parallel network can be transformed into an equivalent feasible network by ``cascading'' operations applied to the two-terminal sub-networks of the original network. A systematic method is developed, resulting in an optimum choice of cascading operations such that the number of switching elements required to implement the transformed circuit is minimized relative to cascading.