# Library

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
• 1
Electronic Resource
Springer
Algorithmica 11 (1994), S. 278-290
ISSN: 1432-0541
Keywords: Network flow ; Cuts ; Parametric cuts ; Graph algorithms ; Layout
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract Galloet al. [4] recently examined the problem of computing on line a sequence ofk maximum flows and minimum cuts in a network ofn nodes, where certain edge capacities change between each flow. They showed that for an important class of networks, thek maximum flows and minimum cuts can be computed simply in O(n3+kn2) total time, provided that the capacity changes are made “in order.” Using dynamic trees their time bound isO(nm log(n2/m)+km log(n2/m)). We show how to reduce the total time, using a simple algorithm, to O(n3+kn) for explicitly computing thek minimum cuts and implicitly representing thek flows. Using dynamic trees our bound is O(nm log(n2/m)+kn log(n2/m)). We further reduce the total time toO(n 2√m) ifk is at most O(n). We also apply the ideas from [10] to show that the faster bounds hold even when the capacity changes are not “in order,” provided we only need the minimum cuts; if the flows are required then the times are respectively O(n3+km) and O(n2√m). We illustrate the utility of these results by applying them to therectilinear layout problem.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 2
Electronic Resource
Springer
Algorithmica 7 (1992), S. 499-519
ISSN: 1432-0541
Keywords: Graph algorithms ; Combinatorial optimization ; Network flow ; Parametric optimization
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract Many combinatorial optimization problems are solved by a sequence of network flow computations on a network whose edge capacities are given as a function of a parameter λ. Recently Galloet al. [7] made a major advance in solving such parametric flow problems. They showed that for an important class of networks, calledmonotone parametric flow networks, a sequence ofO(n) flow computations could be solved in the same worst-case time bound as a single flow. However, these results require one of two special assumptions: either that the λ values are presented in increasing or decreasing order; or that the edge capacity functions are affine functions of λ. In this paper we show how to remove both of these assumptions while obtaining the same running times as in [7]. This observation generalizes and unifies the two major results of [7], and allows its ideas to be applied to many new combinatorial problems. Of greatest importance, it allows the efficient application of binary search and successive binary search to a sequence of network flow problems.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 3
Electronic Resource
Springer
Algorithmica 8 (1992), S. 103-117
ISSN: 1432-0541
Keywords: Satisfiability ; Combinatorial optimization ; Stable roommates problem ; Approximation algorithm
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract Given a satisfiable Boolean formula in 2-CNF, it is NP-hard to find a satisfying assignment that contains a minimum number of true variables. A polynomial-time approximation algorithm is given that finds an assignment with at most twice as many true variables as necessary. The algorithm also works for a weighted generalization of the problem. An application to the optimal stable roommates problem is given in detail, and other applications are mentioned.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 4
Electronic Resource
Springer
Algorithmica 10 (1993), S. 64-89
ISSN: 1432-0541
Keywords: Minimum cut ; Connectivity cut ; All-pairs max-flows ; Cut tree ; Equivalent flow tree ; DAG ; Edge-connectivity
Source: Springer Online Journal Archives 1860-2000
Topics: Computer Science , Mathematics
Notes: Abstract There are two well-known, elegant, compact, and efficiently computed representations of selected minimum edge cuts in a weighted, undirected graphG=(V, E) withn nodes andm edges: at one extreme, the Gomory-Hu cut tree [12] represents $$\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)$$ minimum cuts, one for each pair of nodes inG; at the other extreme, the Picard-Queyranne DAG [24] represents all the minimum cuts between a single pair of nodes inG. The GH cut tree is constructed with onlyn−1 max-flow computations, and the PQ DAG is constructed with one max-flow computation, plusO(m) additional time. In this paper we show how to marry these two representations, getting the best features of both. We first show that we can construct all $$\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array} } \right)$$ DAGs, one for each fixed pair of nodes, using onlyn−1 max-flow computations as in [12], plusO(m) time per DAG as in [24]. This speeds up the obvious approach by a factor ofn. We then apply this approach to an unweighted graphG, to find all the edge-connectivity cuts inG, i.e., cuts with capacity equal to the connectivity ofG. Matula [22] gave a method to find one connectivity cut inO(nm) time; we show thatO(nm) time suffices to represent all connectivity cuts compactly, and to list all of them explicitly. This improves the previous best time bound ofO(n 2 m) [3] for listing the connectivity cuts. The connectivity cuts are central in network reliability calculations. We then show how to find all pairs of nodes that are separated by at least one connectivity cut inO(nm) time.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 5
Electronic Resource
Springer
Bulletin of mathematical biology 55 (1993), S. 141-154
ISSN: 1522-9602
Source: Springer Online Journal Archives 1860-2000
Topics: Biology , Mathematics
Notes: Abstract Multiple string (sequence) alignment is a difficult and important problem in computational biology, where it is central in two related tasks: finding highly conserved subregions or embedded patterns of a set of biological sequences (strings of DNA, RNA or amino acids), and inferring the evolutionary history of a set of taxa from their associated biological sequences. Several precise measures have been proposed for evaluating the goodness of a multiple alignment, but no efficient methods are known which compute the optimal alignment for any of these measures in any but small cases. In this paper, we consider two previously proposed measures, and given two computationaly efficient multiple alignment methods (one for each measure) whose deviation from the optimal value isguaranteed to be less than a factor of two. This is the novel feature of these methods, but the methods have additional virtues as well. For both methods, the guaranteed bounds are much smaller than two when the number of strings is small (1.33 for three strings of any length); for one of the methods we give a related randomized method which is much faster and which gives, with high probability, multiple alignments with fairly small error bounds; and for the other measure, the method given yields a non-obviouslower bound on the value of the optimal alignment.
Type of Medium: Electronic Resource
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 6
Book
Cambridge, MA u.a. :MIT Press,
Title: ¬The¬ stable marriage problem: structure and algorithms
Author: Gusfield, Dan
Publisher: Cambridge, MA u.a. :MIT Press,
Year of publication: 1989
Pages: 240 S.
Series Statement: Foundations of computing
Type of Medium: Book
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 7
Title: Sensitivity analysis for combinatorial optimization, Ph. D. Thesis, University of California, Berkeley, 1980
Author: Gusfield, Dan
Publisher: Ann Arbor :Univers. Microfilms Internat.,
Year of publication: 1980
Pages: 112 S.
Type of Medium: Book
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
• 8
Title: Algorithms on strings, trees, and sequences : computer science and computational biology
Author: Gusfield, Dan
Publisher: Cambridge :Cambridge Univ. Pr.,
Year of publication: 1997
Pages: 534 S.
Type of Medium: Book
Library Location Call Number Volume/Issue/Year Availability
Others were also interested in ...
Close ⊗