Evolutionary data has been traditionally modeled via phylogenetic trees; however, branching alone cannot model conflicting phylogenetic signals, so networks are used instead. Ancestral recombination graphs (ARGs) are used to model the evolution of incompatible sets of SNP data, allowing each site to mutate only once. The model often aims to minimize the number of recombinations. Similarly, incompatible cluster data can be represented by a reticulation network that minimizes reticulation events. The ARG literature has traditionally been disjoint from the reticulation network literature. By building on results from the reticulation network literature, we resolve an open question of interest to the ARG community. We explicitly prove that the History Bound, a lower bound on the number of recombinations in an ARG for a binary matrix, which was previously only defined procedurally, is equal to the minimum number of reticulation nodes in a network for the corresponding cluster data. To facilitate the proof, we give an algorithm that constructs this network using intermediate values from the procedural History Bound definition. We then develop a top-down algorithm for computing the History Bound, which has the same worst-case runtime as the known dynamic program, and show that it is likely to run faster in typical cases.

Chordal graphs have been extensively studied and have applications in various fields, including computational biology, sparse matrix computation, and graphical models. They are characterized by the existence of clique trees, whose vertices correspond to the maximal cliques of a chordal graph. In many applications, it is the clique tree of the chordal graph that is of greatest utility. In general, the number of clique trees can grow exponentially with the size of the chordal graph, and in some applications, particular clique trees have greater utility; we want additional criteria to select the most useful clique tree(s). A natural criterion in phylogenetics (and perhaps elsewhere) is that of compactness. In this paper, we formalize this criterion as the average distance between nodes, and present a characterization of clique trees that satisfies this criterion. We also develop a polynomial-time algorithm to find such a clique tree, and show that any minimum average-distance clique tree of a chordal graph can be constructed by our algorithm.

We study the three-state perfect phylogeny problem and show that there is a three-state perfect phylogeny for a set of input sequences if and only if there is a perfect phylogeny for every subset of three characters. In establishing these results, we prove fundamental structural features of the perfect phylogeny problem on three-state characters and completely characterize the minimal obstruction sets that must occur in input sequences that do not have a perfect phylogeny. We also give a proof for a stated lower bound involved in the conjectured generalization of our main result to any number of states.

The multistate perfect phylogeny problem is a classic problem in computational biology. When no perfect phylogeny exists, it is of interest to find a set of characters to remove in order to obtain a perfect phylogeny in the remaining data. This is known as the character removal problem. We show how to use chordal graphs and triangulations to solve the character removal problem for an arbitrary number of states, which was previously unsolved. We outline a preprocessing technique that speeds up the computation of the minimal separators of a graph. Minimal separators are used in our solution to the missing data character removal problem and to Gusfield's solution of the perfect phylogeny problem with missing data.

A tanglegram is a pair of trees on the same set of leaves with matching leaves in the two trees joined by an edge. Tanglegrams are widely used in biology--to compare evolutionary histories of host and parasite species and to analyze genes of species in the same geographical area. We consider optimization problems in tanglegram drawings. We show a linear time algorithm to decide if a tanglegram admits a planar embedding by a reduction to the planar graph drawing problem. This problem was also studied by Fernau et al. A similar reduction to a graph crossing problem also helps to solve an open problem they posed, showing a fixed-parameter tractable algorithm for minimizing the number of crossings over all d-ary trees. For the case where one tree is fixed, we show an O(n log n) algorithm to determine the drawing of the second tree that minimizes the number of crossings. This improves the bound from earlier methods. We introduce a new optimization criterion using Spearman's footrule distance and give an O(n²) algorithm. We also show integer programming formulations to quickly obtain tanglegram drawings that minimize the two optimization measures discussed. We prove lower bounds on the maximum gap between the optimal solution and the heuristic of Dwyer and Schreiber to minimize crossings.

This special issue contains the papers accepted for presentation at the 2009 ISMB/ECCB Conference (http://www.iscb.org/ismbeccb2009/); the joint conference of ‘Intelligent Systems for Molecular Biology’ and ‘European Conference on Computational Biology’ to be held in Stockholm, Sweden from June 27 to July 2, 2009. The papers contained in this volume are a selection of the 242 papers submitted to the conference. The papers were submitted to 11 distinct areas, with two co-chairs for most areas, who selected their area committees and oversaw the reviewing process. Several of the area chairs were new, and this year ‘Population Genomics’ was added to the 10 areas that made up the ISMB Conference in 2008. The areas, co-chairs and submission/acceptance information are listed in the following table. The area chairs were responsible for selecting the members of the Program Committee that consisted of more than 300 reviewers, assisted by a sizeable number of sub-reviewers. Most papers received three reviews and several received four or more reports. There was an intense discussion between referees and the area chairs. In a first round of evaluation, during a long phone discussion of area chairs, 37 papers were selected for acceptance, with another 16 papers selected to undergo a further evaluation by a broad range of area chairs; from those 16 papers, another 9 were accepted for the conference after a second phone discussion. For all the papers where the referee comments might have confused the authors, particularly for rejected papers, additional comments were added by the area chairs. In total, 46 papers were accepted (formally, conditionally accepted pending revision). After acceptance notices were sent, the authors had 2 weeks to modify their papers, incorporating suggestions from the reviews and responding to reviewers comments. These modified papers and the authors' responses were examined during the next week to spot any additional problems and to check how each paper was modified in response to the reviewers comments. Any modified paper that did not incorporate reviewers suggestions or defend that omission in the author's explanation could have been rejected at this point. We are happy to say that all 46 conditionally accepted papers were finally accepted for the conference. The final acceptance rate was 19%, a bit higher than in previous years, reflecting a lower number of submissions this year (242 submissions compared with 287 submissions, and 17.1% acceptance rate in 2008; 15.8% acceptance rate in 2007). The corresponding authors of submitted papers came from 29 countries, including 450 from North America, 271 from Europe and Israel, 164 from Asia and Australia and 14 from South America. We would like to thank the area chairs and reviewers for their efforts, dedication and quality of their professional work; all authors of submitted papers; Alfonso Valencia for sharing his experience from ISMB08; Andrei Voronkov for technical support with the EasyChair system; the team at Oxford University Press for type-setting the papers; the Conference Chairs, Gene Myers and Marie-France Sagot for their continuous support; and Steven Leard for helping us to deal with the all kinds of issues.

Reviews the first year of publication and outlines plans for the second year.

A phylogenetic network is a generalization of a phylogenetic tree, allowing properties that are not tree-like. With the growth of genomic data, much of which does not fit ideal tree models, there is greater need to understand the algorithmics and combinatorics of phylogenetic networks (Posada and Crandall 2001, Schierup and Hein 2000). Wang et al. (2001) studied the problem of constructing a phylogenetic network for a set of n binary sequences derived from the all-zero ancestral sequence, when each site in the sequence can mutate from zero to one at most once in the network, and recombination between sequences is allowed. They showed that the problem of minimizing the number of recombinations in such networks is NP-hard, but introduced a special case of the problem, i.e., to determine whether the sequences could be derived on a phylogenetic network where the recombination cycles are node-disjoint. Wang et al. (2001) provide a sufficient, but not a necessary test, for such solutions. Gusfield et al. (2003, 2004) gave a polynomial-time algorithm that is both a necessary and sufficient test. In this paper, we study in much more detail the fine combinatorial structure of node-disjoint cycles in phylogenetic networks, both for purposes of insight into phylogenetic networks and to speed up parts of the previous algorithm. We explicitly characterize all the ways in which mutations can be arranged on a disjoint cycle, and prove a strong necessary condition for a set of mutations to be on a disjoint cycle. The main contribution here is to show how structure in the phylogenetic network is reflected in the structure of an efficiently-computable graph, called the conflict graph. The success of this approach suggests that additional insight into the structure of phylogenetic networks can be obtained by exploring structural properties of the conflict graph.

Abstract Summary: We have developed an efficient program, the Perfect Phylogeny Haplotyper (PPH) that takes in unphased population genotype data, and determines if that data can be explained by haplotype pairs that could have evolved on a perfect phylogeny. Availability: Executable code for four common platforms is available at: http://wwwcsif.cs.ucdavis.edu/~gusfield Contact: [email protected] * To whom correspondence should be addressed.

The next high-priority phase of human genomics will involve the development of a full Haplotype Map of the human genome [12]. It will be used in large-scale screens of populations to associate specific haplotypes with specific complex genetic-influenced diseases. A prototype Haplotype Mapping strategy is presently being finalized by an NIH working-group. The biological key to that strategy is the surprising fact that genomic DNA can be partitioned into long where genetic recombination has been rare, leading to strikingly fewer distinct haplotypes in the population than previously expected [12, 6, 21, 7].In this paper we explore the algorithmic implications of the key (and now realistic) in long blocks observation, for the problem of inferring haplotypes in populations. We observe that the no-recombination assumption is very powerful. This assumption, along with the standard population-genetic assumption of infinite sites [23, 14] imposes severe combinatorial constraints on the permitted solutions to the haplotype inference problem, leading to an efficient deterministic algorithm to deduce all features of the permitted haplotype solution(s) that can be known with certainty. The technical key is to view haplotype data as disguised information about paths in an unknown tree, and the haplotype deduction problem as a problem of reconstructing the tree from that path information. This formulation allows us to exploit deep theorems and algorithms from graph and matroid theory to efficiently find one permitted solution to the haplotype problem; it gives a simple test to determine if it is the unique solution; if not, we can implicitly represent the set of all permitted solutions so that each can be efficiently created.

There are many critical situations when one needs to rapidly identify an unidentified pathogen from among a given set of previously sequenced pathogens. DNA or RNA hybridization chips can be designed for such identifications. Each cell in the chip can report the presence or absence of a specific substring of DNA in the unidentified pathogen. Properly designed, the collection of reports obtained from the cells can uniquely identify any pathogen in the set, or determine that the unidentified pathogen is not in the set. There is a limit to the number of cells on a chip, and a range of substring lengths that a cell can handle. So, given the full sequences of a set of pathogens, the problem is to design the chip by selecting the smallest set of substrings of the appropriate lengths, so that each pathogen in the set has a unique set of cells that report a substring. For any given pathogen, the set of reporting cells is its signature, and hence the entire system is a "barcode" system for the pathogens.Previous work addressed this problem [1], but focused on pathogens of bacterial size, and hence had to make many compromises for the sake of efficiency. The substrings lengths were severely restricted, and no optimality or near-optimality was guaranteed. In this paper, we focus on viral-size pathogens. We show that for genomes of this size, it is practical to solve the barcode design problem optimally, or near-optimally, without artificially constraining the problem. We also efficiently find barcodes that provide a level of redundancy, tolerating a number of errors or mutations. The key technical ideas are the use of suffix trees to identify the critical substrings, integer-linear programming (ILP) to express the minimization problem, and a simple idea that dramatically reduces the size of the ILP, allowing it to be solved efficiently by the commercial ILP solver CPLEX. We report extensive tests of our approach on various collections of virus DNA and RNA sequences.

We present a new polynomial time approximation scheme (PTAS) for tree alignment, which is an important variant of multiple sequence alignment. As in the existing PTASs in the literature, the basic approach of our algorithm is to partition the given tree into overlapping components of a constant size and then apply local optimization on each such component. But the new algorithm uses a clever partitioning strategy and achieves a better efficiency for the same performance ratio. For example, to achieve approximation ratios 1.6 and 1.5, the best existing PTAS has to spend time O(kdn 5 ) and O(kdn 9 ), respectively, where n is the length of each leaf sequence and d,k are the depth and number of leaves of the tree, while the new PTAS only has to spend time O(kdn 4 ) and O(kdn 5 ). Moreover, the performance of the PTAS is more sensitive to the size of the components, which basically determines the running time, and we obtain an improved approximation ratio for each size. Some experiments of the algorithm on simulated and real data are also given.

Article A more efficient approximation scheme for tree alignment Share on Authors: Lusheng Wang City U. of HK City U. of HKView Profile , Tao Jiang McMaster U./U. of Washington McMaster U./U. of WashingtonView Profile , Dan Gusfield U.C. Davis U.C. DavisView Profile Authors Info & Claims RECOMB '97: Proceedings of the first annual international conference on Computational molecular biologyJanuary 1997 Pages 310–319https://doi.org/10.1145/267521.267890Online:19 January 1997Publication History 3citation376DownloadsMetricsTotal Citations3Total Downloads376Last 12 Months1Last 6 weeks0 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 SiteGet Access

Let G=(V,E) be an undirected, unweighted graph with n nodes, m edges and edge connectivity $\lambda$. Given an input parameter $\delta$, the edge augmentation problem is to find the smallest set of edges to add to G so that its edge connectivity is increased by $\delta$. In this paper, we present a solution to this problem which runs in $O(\delta ^2 nm + \delta^3 n^2 + n F(G))$, where F(G) is the time to perform one maximum flow on G. In fact, our solution gives the optimal augmentation for every $\delta '$, $1 \le \delta ' \le \delta$, in the same time bound. By introducing minor modifications to the solution, we can solve the problem without knowing $\delta$ in advance, and we can also solve the node-weighted version and the degree-constrained version of the problem. If $\delta =1$, then our solution is particularly simple; it runs in O(nm) time, and it is a natural generalization of the algorithm in [K. Eswaran and R. E. Tarjan, SIAM J. Comput., 5 (1976), pp. 653--665] for the case where $\lambda+\delta =2$. We also solve the converse problem in the same time bound: given an input number k, increase the connectivity of G as much as possible by adding at most k edges. Our solution makes extensive use of the structure of particular sets of cuts.

To protect sensitive information in a cross tabulated table, it is a common practice to suppress some of the cells in the table. A linear combination of suppressed cells is called a linear invariant if the combination has a unique feasible value. Intuitively, the information contained in an invariant is not protected even though the values of the suppressed cells are not disclosed. This paper gives a surprisingly efficient algorithm for testing whether a linear combination of suppressed cells is an invariant. In sequential computation, the algorithm runs in optimal linear time. In parallel computation, the algorithm runs in polylogarithmic time using a polynomial number of processors on a parallel random access machine. The algorithm exploits a linear algebraic structure of directed and undirected cycles in a mixed graph induced by a given table. This new structure also plays a crucial role in subsequent papers on other aspects of detecting and protecting sensitive information in a cross tabulated table.

Abstract In this paper, we examine two related problems of inferring the evolutionary history of n objects, either from present characters of the objects or from several partial estimates of their evolutionary history. The first problem is called the Phylogeny problem, and second is the Tree Compatibility problem. Both of these problems are central in algorithmic approaches to the study of evolution and in other problems of historical reconstruction. In this paper, we show that both of these problems can be solved by graph theoretic methods in linear time, which is time optimal, and which is a significant improvement over existing methods.

Abstract The Gomory–Hu cut tree is a compact and efficiently computed representation of selected minimum edge cuts in a weighted undirected graph G = (V, E) with n nodes. It represents ( ) minimum cuts, one for each pair of nodes in G, and can be constructed with only n − 1 flow computations. In this article, we generalize the types of cut‐trees that can be efficiently constructed. We solve the open problem, posed by Hu [9], of constructing with n − 1 flows a cut‐tree for minimum node weighted cuts in an undirected graph. We then show how to build cut‐trees that compactly represent the minimum edge cuts in directed graphs, partially solving the open problem of constructing cut‐trees for weighted edge cuts in directed graphs.

The strength of a graph is a measure of its vulnerability, strictly generalizing the edge connectivity of a weighted graph. Cunningham [J. Assoc. Comput. Mach., 32 (1985), pp. 549–562] showed how to compute the strength of a graph in $O(| V |^4 | E |)$ time, using ideas from polymatroids and network flow. In this paper, his polymatroid approach is modified, a modified version of the Goldberg-Tarjan network flow algorithm [J Assoc. Comput. Mach., 4 (1988), pp. 136-146] is used. Then, using ideas developed by Gallo, Grigoriadis, and Tarjan [SIAM J. Comput., 18 (1989), pp. 30–55], and by Gusfield, Martel, and Fernandez-Baca in [SIAM J. Comput.,16 (1987), pp. 237–251], it is shown that the solution runs in $O(| V |^3 | E |)$ time. Analogous speedups for sparse-case bounds are also obtainable.

An undirected, unweighted graph G=(V, E with n nodes, m edges, and connectivity lambda ) is considered. Given an input parameter delta , the edge augmentation problem is to find the smallest set of edges to add to G so that its edge-connectivity is increased by delta . A solution to this problem that runs in time O( delta /sup 2/nm+nF(n)), where F(n) is the time to perform one maximum flow on G, is given. The solution gives the optimal augmentation for every delta ', 1>

A reexamination is made of the problem of protecting sensitive data in an n by n table of integer statistics, when the nonsensitive data are made public along with the row and column sums for the table. Consideration is given to the problem of computing the tightest upper bounds on the values of sensitive (undisclosed) cells. These bounds, together with tightest lower bounds (which can be efficiently computed), define precisely the smallest intervals that an adversary can deduce for the missing sensitive cell values. Small intervals compromise the security of the undisclosed data, and in some cases violate laws on public data disclosure. It is observed that the number of initial needed bounds can be reduced from O(n log n) to 2n-1 by exploiting a recent result of C.K. Cheung and T.C. Hu (1988).>

A very simple algorithm for the classical problem of computing the maximum network flow value between every pair of nodes in an undirected, capacitated n node graph is presented; as in the well-known Gomory–Hu method, the method given here uses only $n - 1$ maximum flow computations. Our algorithm is implemented by adding only five simple lines of code to any program that produces a minimum cut; a program to produce an equivalent flow tree, which is a compact representation of the flow values, is obtained by adding only three simple lines of code to any program producing a minimum cut. A very simple version of the Gomory–Hu cut tree method that finds one minimum cut for every pair of nodes is also derived, and it is shown that the seemingly fundamental operation of that method, node contraction, is not needed, nor must crossing cuts be avoided. As a result, this version of the Gomory–Hu method is implemented by adding less than ten simple lines of code to any program that produces a minimum cut. The algorithms in this paper demonstrate that a cut tree of graph G can be computed with $n - 1$ calls to an oracle that alone knows G, and that, when given two nodes s and t, returns any arbitrary minimum $(s, t)$ cut and its value.

In this paper we study the problem of protecting sensitive data in an n by n two-dimensional table of statistics, when the nonsensitive data are made public along with the row and column sums for the table. A sensitive cell is considered unprotected if its exact value can be deduced from the nonsensitive cell values and the row and column sums. We give an efficient algorithm to identify all unprotected cells in a table. The algorithm runs in linear time if the sensitive values are known, and in $O(n^3 )$ time if they are not known. We then consider the problem of suppressing the fewest additional cell values to protect all the sensitive cells, when some cells are initially unprotected. We give a linear time algorithm for this problem in the useful special case that all cell values are strictly positive. We next consider the problem of computing the tightest upper and lower bounds on the values of sensitive cells. We show that each cell bound can be computed in $O(n^3 )$ time, but all $\Theta (n^2 )$ values can be computed in $O(n^4 )$ total time. In the case that all the cells are sensitive, we show that trivial methods compute the tightest bounds, and in fact, the $n^2 $ lower bounds can be computed in $O(n)$ arithmetic and comparison operations. Although these problems at first appear to be problems in integer linear algebra, the solutions are based on computational graph theory, and the worst case times are significantly faster than for approaches based on linear algebraic computations.

The stable roommates problem is a well-known problem of matching $2n$ people into disjoint pairs to achieve a certain type of stability. The problem strictly generalizes the better-known stable marriage problem. It has been previously shown [Irving and Leather, SIAM J. Comput., 15 (1986), pp. 655–667], that the set of stable marriages, for a given instance, can be compactly represented and this representation has been exploited to yield a number of very efficient algorithms concerned with stable marriage [Irving, Leather, and Gusfield, J. Assoc. Comput. Mach., 34 (1987), pp. 532–543], [Gusfield, SIAM J. Comput., 16 (1987), pp. 111–128], [Gusfield et al., J. Combin. Theory, Ser A., (1987), pp. 304–309]. In this paper, we generalize the structure of the stable marriages to obtain two efficiently computed, small, implicit representations of the set of all stable roommate assignments, for any given instance. One representation is a partial order $\Pi $ on $O(n^2 )$ elements such that the stable assignments are in one-one correspondence with certain easily recognized subsets of $\Pi $. Partial order $\Pi $ is a strict generalization of the stable marriage representation of [Irving and Leather, SIAM J. Comput., 15 (1986), pp. 655–667]. The second representation is an efficiently constructed, undirected graph G with $O(n^2 )$ nodes, such that there exists a one-one correspondence between the maximal (not maximum) independent sets of G and the stable roommate assignments. In either representation, G or $\Pi $, given a set representing a stable assignment, the assignment itself can be constructed in $O(n^2 )$ time. We also give an algorithm to generate each stable assignment for any given instance in $O(n^2 )$ time per assignment. The efficiency of this method depends heavily on special properties of the stable assignment problem developed in this paper. Finally, we give a succinct characterization of the set of all “stable pairs,” those pairs of people who are roommates in at least one stable assignment, and we give an $O(n^3 \log n)$ time algorithm to find them all.

In an instance of size n of the stable marriage problem, each of n men and n women ranks the members of the opposite sex in order of preference. A stable matching is a complete matching of men and women such that no man and woman who are not partners both prefer each other to their actual partners under the matching. It is well known [2] that at least one stable matching exists for every stable marriage instance. However, the classical Gale-Shapley algorithm produces a marriage that greatly favors the men at the expense of the women, or vice versa. The problem arises of finding a stable matching that is optimal under some more equitable or egalitarian criterion of optimality. This problem was posed by Knuth [6] and has remained unsolved for some time. Here, the objective of maximizing the average (or, equivalently, the total) “satisfaction” of all people is used. This objective is achieved when a person's satisfaction is measured by the position of his/her partner in his/her preference list. By exploiting the structure of the set of all stable matchings, and using graph-theoretic methods, an O ( n 4 ) algorithm for this problem is derived.

The stable marriage problem is a well-known problem of matching n men to n women to achieve a certain type of “stability;” the $O(n^2 )$ time Gale-Shapley [GS] algorithm for finding two particular, but extreme, stable marriages (out of a possibly exponential number of stable marriages) is also well known. In this paper we consider four problems concerned with finding information about the set of all stable marriages, and with finding stable marriages other than those obtained by the Gale-Shapley algorithm. In particular, we give an $O(n^2 )$ time algorithm which, for any problem instance of n men and n women, finds every man–woman pair that is contained in at least one stable marriage; we show that the same algorithm finds all the “rotations” for the problem instance in $O(n^2 )$ time; we give an $O(n^2 + n|S|)$ time and $O(n^2 )$ space bounded algorithm (which is time and space optimal) to enumerate all stable marriages, where S is the set of them; and we give an $O(n^2 )$ time algorithm to find the minimum regret stable marriage (the best marriage, as measured by the person who is worst off in it). We believe the previous best time bounds for these problems are respectively $O(n^4 )$ (from a related problem in [K]), $O(n^3 )$ [ILG], $O(n^3 |S|)$ [K] and $O(n^4)$ [K]. The basic idea leading to the improved running times is to exploit theorems about the structure of stable marriages in order to avoid back-up and duplicated work inherent in earlier algorithms.

In this paper we consider an augmentation problem on mixed graphs that generalizes and unifies two augmentation problems considered by Eswaran and Tarjan [this Journal, 5 (1976), pp. 653–665]. The mixed augmentation problem has applications in the design of communication networks, and forms of the mixed augmentation problem are central in statistical data security problems discussed in [Yale Univ. Tech. Report, August 1984]. We solve the augmentation problem on mixed graphs in time linear in the number of edges of the graph, the same time bound obtained in [ET] for each of the two special cases.

We discuss network flow in a bipartite graph G with node sets S and T. We show that Karzanov’s algorithm runs in time $O(|S|^2 |T|)$ on G, and that the MPM algorithm can be modified to run in the same bound. For the common case that the degree of each node in T is bounded by a constant, we show that a modified version of the MPM algorithm runs in time $O(|S|^3 + |S||T|)$ on G. The importance of these results comes from the common occurrence of problems that can be modeled and solved using network flow on bipartite graphs where $|S| \ll |T|$. In many applications involving bounded degree on the nodes in T, $|T| = \theta (|S|^2 )$, and our results reduce the best bounds on bipartite flow from $O(|S|^6 )$ to $O(|S|^3 )$. We use our results on bipartite flow to obtain the fastest known bounds on several combinatorial problems, and mention several additional problems involving bipartite flow where $|S|$ is much smaller than $|T|$.

In parametnc computing some parts of a problem description are given as funcuons of one or more parameters which vary over a range of values Any fgxed values of the parameters specify a problem instance, and the goal of parametric computing ~s to solve all such problem instances efficiently as a funcUon of the parameter values.The output ~s either a partition of the parameter space into regions such that all instances m the same region have the same solution, or some other compact output permitting rapid solution to any given problem instance.A general parametnc computing method that works well for a large class of combinatorial problems ts presented The method is related to one for solving ratio optim~aUon problems developed by Megiddo The parametric method is illustrated by solvmg a problem of dmnbutmg modules of a computer program between two processors.Associated with each module are processing costs on each processor, and assocmted with each pair of modules is a communication cost recurred by d~stributing the modules on d~fferent processors The problem is to distribute the modules to mmunize the total cost of computauon.Stone has solved this problem for fixed costs, and for costs of one processor varying as a function of a single parameter representing the varying load on one processor.The general parametnc computing method is applied to solve the problem efficiently for costs of both processors varying as a funcuon of two independent parameters.

Abstract In the article “Arc Tolerances in Shortest‐Path and Network Flow Problems” by D. R. Shier and C. Witzgall, several methods were described to compute, relative to a given tree T, the “arc tolerance” of each arc in a graph G of n nodes and A arcs. One method, the “dead‐end retraction” method was shown to take O(n2) time and O(n2) space, and another method, the “cycle‐tracing” method was shown to take O(nA) time but only O(A) space. For the important case of large sparse graphs, these methods either require excessive time, or excessive space. In this note implementations of both of the above methods are described which require O(A) space and O(A) log n) time. In the cycle‐tracing method this is a strict improvement even for the dense case.

The multi-terminal network flow synthesis problem is one of the few nicely solved problems in network design, and is used widely in courses and texts on combinatorial optimization as an example of an elegantly solved problem. The solution used in these texts is due to R. E. Gomory and T. C. Hu. We present two simpler algorithms which improve the original method in speed, simplicity of the needed data structures and, most importantly, in the simplicity of the networks that are constructed. The networks constructed are planar and “uniformly optimal,” permit simple flow routing methods and simple solutions to many sensitivity and postoptimality questions, and have as few edges as any networks produced by the Gomory-Hu method. Further, one algorithm constructs networks with only one node of degree larger than three, while the other algorithm constructs networks in which no node has degree greater than four.