Embedding Graphs with Bounded Treewidth into Optimal Hypercubes (2008)
Nachdruck auch auszugsweise verboten
Embedding Graphs with Bounded Treewidth into Optimal Hypercubes (2008)
Methodenundwerkzeugefurdienutzung Parallelerrechnerarchitekturen Sonderforschungsbereich, Boundedtreewidthinto Embeddinggraphswith, Sprecher Sfb, ...
Nachdruck auch auszugsweise verboten
Network Implementations of the DTEP Algorithm (2007)
Ernst W. Mayr, C. Greg Plaxton
The dynamic tree expression problem (DTEP) was defined in [Ma87]. In this paper, efficient implementations of the DTEP algorithm are developed for the hypercube, butterfly, perfect shuffle and...
Counting Minimum Weight Spanning Trees (2007)
Andrei Broder Ernst, Andrei Z. Broder, Ernst W. Mayr
.37> i); 0 otherwise. Then the generating function for the number of spanning trees by weight is the determinant of the matrix DG = ~ A(x) \Theta ~ A T (1) where ~ A is obtained from A by the...
Optimal Implementation of General Divide-and-Conquer on the Hypercube and Related Networks (2007)
. We show how to implement divide-and-conquer algorithms without undue overhead on a wide class of networks. We give an optimal generic divide-and-conquer implementation on hypercubes for the class...
Counting Minimum Weight Spanning Trees (2007)
Andrei Z. Broder, Ernst W. Mayr
.37> i); 0 otherwise. Then the generating function for the number of spanning trees by weight is the determinant of the matrix DG = ~ A(x) \Theta ~ A T (1) where ~ A is obtained from A by the...
Optimal Grobner Base Algorithms for (2007)
Nachdruck auch auszugsweise verboten
Computing the Dimension of a Polynomial Ideal (2007)
Anna Bernasconi, Ernst W. Mayr, Michal Mnuk, Martin Raab
Following ideas from [Hei83, DFGS91, MT97] and applying the techniques proposed in [May89, KM96, Kuh98], we present a deterministic algorithm for computing the dimension of a polynomial ideal...
At M Unchen, Ernst W. Mayr, Ernst W. Mayr
Nachdruck auch auszugsweise verboten
The diamond operator - Implementation of exact real algebraic numbers (2005)
Schmitt, Susanne, Ganzha, Victor G., Mayr, Ernst W., Vorozhtsov, Evgenii V.
The LEDA number type real is extended by the diamond operator, which allows to compute exactly with real algebraic numbers given as roots of polynomials. The coefficients of these polynomials can be...
A Descartes algorithm for polynomials with bit-stream coefficients (2005)
Eigenwillig, Arno, Kettner, Lutz, Krandick, Werner, Mehlhorn, Kurt, Schmitt, Susanne, Wolpert, Nicola, ...
Exploring New Frontiers of Theoretical Informatics (2004)
Levy, Jean-Jacques, Mayr, Ernst W., Mitchell, John C.
In recent years, IT application scenarios have evolved in very innovative ways. Highly distributed networks have now become a common platform for large-scale distributed programming, high bandwidth...
Engineering an External Memory Minimum Spanning Tree Algorithm (2004)
Dementiev, Roman, Sanders, Peter, Schultes, Dominik, Sibeyn, Jop F., Lévy, Jean-Jacques, Mayr, Ernst W., ...
We develop an external memory algorithm for computing minimum spanning trees. The algorithm is considerably simpler than previously known external memory algorithms for this problem and needs a...
Engineering an External Memory Minimum Spanning Tree Algorithm (2004)
Dementiev, Roman, Sanders, Peter, Schultes, Dominik, Sibeyn, Jop F., Lévy, Jean-Jacques, Mayr, Ernst W., ...
We develop an external memory algorithm for computing minimum spanning trees. The algorithm is considerably simpler than previously known external memory algorithms for this problem and needs a...
Simulation of an Ultracomputer with Several 'Hot Spots'. (2002)
Rosenblum,David S., Mayr,Ernst W.
This report describes the design and results of a time-driven simulation of an Ultracomputer-like multiprocessor in the presence of several hot spots, or memory modules which are frequent targets of...
Applications of Parallel Scheduling to Perfect Graphs. (2002)
The authors combine a parallel algorithm for the two processor scheduling problem, which runs in polylog time on a polynomial number of processors, with an algorithm to find transitive orientations...
Computing the Dimension of a Polynomial Ideal (2002)
Anna Bernasconi, Ernst W. Mayr, Michal Mnuk, Martin Raab
Following ideas from [Hei83, DFGS91, MT97] and applying the techniques proposed in [May89, KM96, Küh98], we present a deterministic algorithm for computing the dimension of a polynomial ideal...
Parallel continuous randomized load balancing (1998)
Petra Berenbrink, Tom Friedetzky, Ernst W. Mayr
Recently, the subject of allocating tasks to servers has attracted much attention. There are several ways of distinguishing load balancing problems. There are sequential and parallel strategies, that...
On-line scheduling of parallel jobs with runtime restrictions (1998)
Anforderungen Prof, Dr. A. Bode, Sprecher Sfb, Stefan Bischof, Stefan Bischof, ...
Nachdruck auch auszugsweise verboten
Optimal Dynamic Embeddings of Complete Binary Trees into Hypercubes (1998)
Into Hypercubes, Volker Heun, Ernst W. Mayr
The double-rooted complete binary tree is a complete binary tree where the root is replaced by an edge. It is folklore that the double-rooted complete binary tree is a spanning tree of the hypercube...
Efficient Dynamic Embeddings of Binary Trees into Hypercubes (1998)
In this paper, a deterministic algorithm for dynamically embedding binary trees into hypercubes is presented. Because of a known lower bound, any such algorithm must use either randomization or...
On-Line Scheduling of Parallel Jobs with Runtime Restrictions (1998)
Consider the execution of a parallel application that dynamically generates parallel jobs with specified resource requirements during its execution. We assume that there is not sufficient knowledge...
The Dynamic Tree Expression Problem, (1997)
We present a uniform method for obtaining efficient parallel algorithms for a rather large class of problems. The method is based on a logic programming model, and it derives its efficiency from fast...
Some Complexity Results for Polynomial Ideals (1997)
In this paper, we survey some of our new results on the complexity of a number of problems related to polynomial ideals. We consider multivariate polynomials over some ring, like the integers or the...
The complexity of the equivalence problem for commutative semigroups (1996)
At M Unchen, Ernst W. Mayr, Ernst W. Mayr
In this paper, optimal decision procedures for the equivalence, subword, and finite enumeration problems for commutative semigroups are obtained. These procedures require at most space 2 c\Deltan,...
An Optimal Algorithm for Constructing the Reduced Grobner Basis of Binomial Ideals (1996)
At M Unchen, Ernst W. Mayr, Ernst W. Mayr
Nachdruck auch auszugsweise verboten
The Complexity of the Equivalence Problem for Commutative Semigroups (1996)
Ulla Koppenhagen, At M Unchen, Ernst W. Mayr, Ernst W. Mayr
In this paper, optimal decision procedures for the equivalence, subword, and finite enumeration problems for commutative semigroups are obtained. These procedures require at most space 2 c\Deltan ,...
A General Method for Efficient Embeddings of Graphs into Optimal Hypercubes (1996)
Embeddings of several graph classes into hypercubes have been widely studied. Unfortunately, almost all investigated graph classes are regular graphs such as meshes, complete trees, pyramids. In this...
Optimal Dynamic Edge-Disjoint Embeddings of Complete Binary Trees into Hypercubes (1996)
Sprecher Sfb, Volker Heun, ...
The double-rooted complete binary tree is a complete binary tree where the path (of 2 length2) between the children of the root is replaced by a path of length3. It is folklore that the double-rooted...
Exponential space computation of Gröbner bases (1996)
Klaus Kühnle, Klaus Kuhnle, Ernst W. Mayr, Ernst W. Mayr
Given a polynomial ideal and a term order, there is a unique reduced Grobner basis and, for each polynomial, a unique normal form, namely the smallest (w.r.t. the term order) polynomial in the same...
Optimal Dynamic Edge-Disjoint Embeddings of Complete Binary Trees into Hypercubes (1996)
Nachdruck auch auszugsweise verboten
Optimal Parallel Algorithms for Two Processor Scheduling with Tree Precedence Constraints (1995)
At M Unchen, Ernst W. Mayr, Ernst W. Mayr, Hans Stadtherr, ...
Consider the problem of finding a minimum length schedule for n unit execution time tasks on m processors with tree-like precedence constraints. A sequential algorithm can solve this problem in...
Optimal Routing of Parentheses on the Hypercube (1995)
We consider a new class of routing requests, or partial permutations, for which we give optimal on-line routing algorithms on the hypercube and shuffle-exchange network. For well-formed words of...
Optimal Tree Contraction and Term Matching (1995)
At M Unchen, Ernst W. Mayr, Ernst W. Mayr, Ralph Werchner, ...
An optimal tree contraction algorithm for the boolean hypercube and the constant degree hypercubic networks, such as the shuffle exchange or the butterfly network, is presented. The algorithm is...
Counting Minimum Weight Spanning Trees (1995)
Andrei Z. Broder, Ernst W. Mayr
heorem (see e.g. Theorem 2.10 in [2]). 2 4 3 1 5 3 3 1 1 1 1 2 2 L L L L L L L L L L " " " " " " "" b b b b b b bb L L L L L L fi fi fi fi fi fi fi fi fi fi fi...
On Polynomial Ideals, Their Complexity, and Applications (1995)
A polynomial ideal membership problem is a (w+1)-tuple P = (f; g 1 ; g 2 ; : : : ; g w ) where f and the g i are multivariate polynomials over some ring, and the problem is to determine whether f is...
Optimal Routing of Parentheses on the Hypercube (1994)
We consider a new class of routing requests or partial permutations for which we give optimal on-line routing algorithms on the hypercube and shuffle-exchange network. For well-formed words of...
An optimal tree contraction algorithm for the boolean hypercube and the constant degree hypercubic networks, such as the shuffle exchange or the butterfly network, is presented. The algorithm is...
Scheduling Interval Orders in Parallel (1994)
At M Unchen, Ernst W. Mayr, Ernst W. Mayr
Interval orders are partial orders defined by having interval representations. It is well known that a transitively oriented digraph G is an interval order iff its (undirected) complement G is...
Scheduling Interval Orders in Parallel (1994)
Our algorithm is based on a subroutine for computing so-called scheduling distances, i.e., the minimal number of time steps needed to schedule all those tasks succeeding some given task t and...
Pipelined parallel prefix computations and sorting on a pipelined hypercube (1993)
Ernst W. Mayr, C. Greg Plaxton
This paper brings together a number of previously known techniques in order to obtain practical and efficient implementations of the prefix operation for the complete binary tree, hypercube and...
Divide-and-Conquer Algorithms on the Hypercube (1993)
We show how to implement divide-and-conquer algorithms without undue overhead on a wide class of networks. We give an optimal generic divide-and-conquer implementation on hypercubes for the class of...
Pipelined Parallel Prefix Computations, and Sorting on a Pipelined Hypercube (1993)
Ernst W. Mayr, C. Greg Plaxton
This paper brings together a number of previously known techniques in order to obtain practical and efficient "pipelined" implementations of the prefix operation for the complete binary...
Divide-and-Conquer Algorithms on the Hypercube (1993)
Ernst W. Mayr, Ernst W. Mayr, Ralph Werchner, Ralph Werchner
We show how to implement divide-and-conquer algorithms without undue overhead on a wide class of networks. We give an optimal generic divide-and-conquer implementation on hypercubes for the class of...
A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube (1993)
Unch E N, At M Unchen, Volker Heun, Volker Heun, ...
The d-dimensional binary hypercube is a very popular model of parallel computation.
A New Efficient Algorithm for Embedding an Arbitrary Binary Tree into Its Optimal Hypercube (1993)
Nachdruck auch auszugsweise verboten c1993
On the spanning trees of weighted graphs (1992)
Ernst W. Mayr, C. Greg Plaxton
Given a weighted graph, let W 1; W 2; W 3; : : : denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of...
On the Spanning Trees of Weighted Graphs (1992)
Ernst W. Mayr, C. Greg Plaxton
Given a weighted graph, let W 1 ; W 2 ; W 3 ; : : : denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree...