Gerth Stølting Brodal

Gerth Stølting Brodal

Auto-generated profile, based on publicly available information

Gerth Stølting Brodal

Department of Computer Science, Aarhus University, Aarhus N, Denmark

Research Focus & Metrics

Academic Career Length

33Years (1994-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
20 March 2014 in Bioinformatics
Verified
Journal Article
Closed access
ASAndreas Sand
Andreas Sand
MHMorten K. Holt
Morten K. Holt
JJJens Johansen
Jens Johansen
GBGerth Stølting Brodal
Gerth Stølting Brodal
TMThomas Mailund
Thomas Mailund
CPChristian N. S. Pedersen
Christian N. S. Pedersen
Summary: tqDist is a software package for computing the triplet and quartet distances between general rooted or unrooted trees, respectively. The program is based on algorithms with running time for the triplet distance calculation and for the quartet distance calculation, where n is the number of leaves in the trees and d is the degree of the tree with minimum degree. These are currently the fastest algorithms both in theory and in practice.Availability and implementation: tqDist can be installed on Windows, Linux and Mac OS X. Doing this will install a set of command-line tools together with a Python module and an R package for scripting in Python or R. The software package is freely available under the GNU LGPL licence at http://birc.au.dk/software/tqDist .Contact: cstorm@birc.au.dkSupplementary information: Supplementary data are available at Bioinformatics online

26 June 2003
Verified
Conference Paper
Closed access
GBG.S. Brodal
G.S. Brodal
RJR. Jacob
R. Jacob
In this paper we determine the computational complexity of the dynamic convex hull problem in the planar case. We present a data structure that maintains a finite set of n points in the plane under insertion and deletion of points in amortized O(log n) time per operation. Thespace usage of the data structure is O(n). The data structure supports extreme point queries in a given direction, tangent queries through a given point, and queries for the neighboring points on the convex hull in O(log n) time. The extreme point queries can be used to decide whether or not a given line intersects the convex hull, and the tangent queries to determine whether a given point is inside the convex hull. We give a lower bound on the amortized asymptotic time complexity that matches the performance of this data structure.

8 November 2002
Verified
Conference Paper
Closed access
SAS. Alstrup
S. Alstrup
GBG. Stolting Brodal
G. Stolting Brodal
TRT. Rauhe
T. Rauhe

1 February 2004 in Electronic Notes in Theoretical Computer Science
Verified
Journal Article
Open access
GBGerth Stølting Brodal
Gerth Stølting Brodal
RJRiko Jacob
Riko Jacob
We consider efficient algorithms for exact time-table queries, i.e. algorithms that find optimal itineraries for travelers using a train system. We propose to use time-dependent networks as a model and show advantages of this approach over space-time networks as models

1 February 1998 in Journal of Parallel and Distributed Computing
Verified
Journal Article
Closed access
GBGerth Stølting Brodal
Gerth Stølting Brodal
JTJesper Larsson Träff
Jesper Larsson Träff
CZChristos D. Zaroliagis
Christos D. Zaroliagis

19 January 2006 in BMC Bioinformatics
Verified
Journal Article
Open access
PDF file
TMThomas Mailund
Thomas Mailund
GBGerth S Brodal
Gerth S Brodal
RFRolf Fagerberg
Rolf Fagerberg
CPChristian Ns Pedersen
Christian Ns Pedersen
DPDerek Phillips
Derek Phillips
Background: The neighbor-joining method by Saitou and Nei is a widely used method for constructing phylogenetic trees. The formulation of the method gives rise to a canonical Θ(n3) algorithm upon which all existing implementations are based.Results: In this paper we present techniques for speeding up the canonical neighbor-joining method. Our algorithms construct the same phylogenetic trees as the canonical neighbor-joining method. The best-case running time of our algorithms areO(n2) but the worst-case remainsO(n3). We empirically evaluate the performance of our algoritms on distance matrices obtained from the Pfam collection of alignments. The experiments indicate that the running time of our algorithms evolve as Θ(n2) on the examined instance collection. We also compare the running time with that of the QuickTree tool, a widely used efficient implementation of the canonical neighbor-joining method.Conclusion: The experiments show that our algorithms also yield a significant speed-up, already for medium sized instances.