2020-10-21T11:47:19Zhttp://edoc.mpg.de/ac_p_oai.ploai:edoc.mpg.de:2017852012-09-1987:931
Article
A theoretical and experimental study on the construction of suffix arrays in external memory
English
2002
2003-09-08
1
35
Algorithmica
32
The construction of full-text indexes on very large text collections
is nowadays a hot problem. The suffix array [Manber-Myers,~1993] is
one of the most attractive full-text indexing data structures due to
its simplicity, space efficiency and powerful/fast search operations
supported. In this paper we analyze, both theoretically and
experimentally, the I/O-complexity and the working space of six
algorithms for constructing large suffix arrays. Three of them are
the state-of-the-art, the other three algorithms are our new
proposals. We perform a set of experiments based on three different
data sets (English texts, Amino-acid sequences and random texts) and
give a precise hierarchy of these algorithms according to their
working-space vs. construction-time tradeoff. Given the current
trends in model design~\cite{Farach-et-al,Vitter} and disk
technology~\cite{quantum,Ruemmler-Wilkes}, we will pose particular
attention to differentiate between ``random'' and ``contiguous''
disk accesses, in order to reasonably explain some practical
I/O-phenomena which are related to the experimental behavior of
these algorithms and that would be otherwise meaningless in the
light of other simpler external-memory models.
At the best of our knowledge, this is the first study which provides
a wide spectrum of possible approaches to the construction of suffix
arrays in external memory, and thus it should be helpful to anyone
who is interested in building full-text indexes on very large text
collections.
Finally, we conclude our paper by addressing two other issues. The
former concerns with the problem of building word-indexes; we show
that our results can be successfully applied to this case too,
without any loss in efficiency and without compromising the
simplicity of programming so to achieve a uniform, simple and
efficient approach to both the two indexing models. The latter issue
is related to the intriguing and apparently counterintuitive
``contradiction'' between the effective practical performance of the
well-known BaezaYates-Gonnet-Snider's algorithm~\cite{book-info},
verified in our experiments, and its unappealing (i.e., cubic)
worst-case behavior. We devise a new external-memory algorithm that
follows the basic philosophy underlying that algorithm but in a
significantly different manner, thus resulting in a novel approach
which combines good worst-case bounds with efficient practical
performance.
No
expertsonly
published
joureview
A.
Crauser
Andreas
P.
Ferragina
Paolo
0178-4617
C1256428004B93B8-1FE0191E40BE5BBBC12569FC0056CAD2-Crauser-Ferragina2001
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2017882012-09-1987:931
Conference-Paper
Heuristics for Semi-External Depth First Search on Directed Graphs
English
ACM
New York, USA
2002
2003-08-27
282
292
Winnipeg, Canada
2002-08-10
SPAA 2002 : Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures
Computing the strong components of a directed graph is an essential
operation for a basic structural analysis of it. This problem can
be solved by twice running a depth-first search (DFS).
In an external setting, in which all data can no longer be stored in
the main memory, the DFS problem is unsolved so far. Assuming that
node-related data can be stored internally, semi-external computing
does not make the problem substantially easier. Considering the
definite need to analyze very large graphs, we have developed a set
of heuristics which together allow the performance of semi-external DFS for
directed graphs in practice. The heuristics have been applied to
graphs with very different graph properties, including ``web graphs''
as described in the most recent literature and some call graphs from
ATT. Depending on the graph structure, the program is between 10 and
200 times faster than the best alternative, a factor that will
further increase with future technological developments.
No
expertsonly
published
notspecified
J.F.
Sibeyn
Jop F.
J.
Abello
James
U.
Meyer
Ulrich
1-58113-529-7
C1256428004B93B8-31A8B545C99A2D37C1256C1A003DE57B-SiAbMe02
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2017892012-09-1987:931
Conference-Paper
Exact geometric computation
English
LEA
Athens, Greece
2002
2003-08-27
87
87
Athen, Griechenland
2001-09-20
HERCMA 2001 : proceedings of the 5th Hellenic-European Conference on Computer Mathematics and its Applications (HERCMA-01)
Hellenic-European Research on Computer Mathematics and its Applications
No
expertsonly
published
notspecified
K.
Mehlhorn
Kurt
E.A.
Lipitakis
Elias A.
960-85176-9-9
C1256428004B93B8-135A2711508AF90200256D110031DCD2-Mehlhorn02
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2017932012-09-1987:931
Conference-Paper
External-Memory Breadth-First Search with Sublinear I/O
English
Springer
Berlin, Germany
2002
2003-09-08
723
735
Rome, Italy
2002-09-17
Algorithms - ESA 2002 : 10th Annual European Symposium
Lecture Notes in Computer Science
Breadth-first search (BFS) is a basic graph exploration technique.
We give the first external-memory algorithm for sparse
undirected graphs with sublinear I/O. The best
previous algorithm requires O( n + sort(n+m) ) I/Os
on a graph with n nodes and m edges and a machine with
main-memory of size M, D parallel disks, and block size B.
We present two versions of a new algorithm which requires only
O( sqrt( n/m * (n+m)/(D*B) ) * log_{M/B} (n/B) + sort(n+m)) I/Os
(expected or worst-case, respectively).
Hence, for m = O(n), they improve upon the I/O-performance
of the best previous algorithm by nearly a factor of sqrt(D*B).
Our approach is fairly simple and we conjecture at least the
randomized version to be practical.
No
expertsonly
published
notspecified
K.
Mehlhorn
Kurt
U.
Meyer
Ulrich
R.
Möhring
Rolf
R.
Raman
Rajeev
3-540-44180-8
C1256428004B93B8-A255EBD0F85324E4C1256C3D004FE88A-MehMey2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2017962012-09-1987:931
Conference-Paper
Minimum Cost Flows Over Time without Intermediate Storage
English
ACM
New York, USA
2003
2004-08-02
66
75
Baltimore, USA
2003-01-12
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)
Flows over time (also called dynamic flows)
generalize standard network flows by introducing
an element of time. They naturally model problems where
travel and transmission are not instantaneous. Solving these problems
raises issues that do not arise in standard network flows.
One issue is the question of storage of flow at intermediate nodes.
In most applications
(such as, e.g., traffic routing, evacuation planning,
telecommunications etc.), intermediate storage is limited, undesired,
or prohibited.
The minimum cost flow over time problem is NP-hard. In this paper we
1)~prove that the minimum cost flow over time never requires storage;
2)~provide the first approximation scheme for minimum cost flows over
time that does not require storage; 3)~provide the first approximation
scheme for minimum cost flows over time that meets hard cost
constraints, while approximating only makespan.
Our approach is based on a condensed variant of time-expanded
networks. It also yields fast approximation schemes with simple
solutions for the quickest multicommodity flow problem.
Finally, using completely different techniques, we describe a very
simple capacity scaling FPAS for the minimum cost flow over time
problem when costs are proportional to transit times.
The algorithm builds upon our observation about the
structure of optimal solutions to this problem:
they are universally quickest flows. Again, the FPAS
does not use intermediate node storage.
In contrast to the preceding algorithms that use a
time-expanded network, this FPAS runs directly on the original
network.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9131&did=201796&ver=0
L.
Fleischer
Lisa
M.
Skutella
Martin
0-89871-538-5
C1256428004B93B8-D67F80DC0F3DFECEC1256E200042012C-FleischerSkutella2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018012012-09-1987:931
Article
Better Filtering with Gapped q-Grams
English
2003
2004-06-15
51
70
Fundamenta Informaticae
56
A popular and well-studied class of filters for approximate string
matching compares substrings of length $q$, \emph{the $q$-grams}, in
the pattern and the text to identify text areas that contain potential
matches. A generalization of the method that uses {\em gapped}
$q$-grams instead of contiguous substrings is mentioned a few times in
literature but has never been analyzed in any depth. In this paper,
we report the first results of a study on gapped $q$-grams. We show
that gapped $q$-grams can provide orders of magnitude faster and/or
more efficient filtering than contiguous $q$-grams. To achieve these
results the arrangement of the gaps in the $q$-gram and a filter
parameter called \emph{threshold} have to be optimized. Both of these
tasks are nontrivial combinatorial optimization problems for which we
present efficient solutions. We concentrate on the $k$~mismatches
problem, i.e, approximate string matching with the Hamming distance.
No
expertsonly
published
joureview
S.
Burkhardt
Stefan
J.
Kärkkäinen
Juha
0169-2968
C1256428004B93B8-97486D0D727E678AC1256D0900521D74-BurkhardtKarkkainen2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018062012-09-1987:931
Book
Algorithms for Memory Hierarchies
English
Springer
Berlin, Germany
2003
2625
No
expertsonly
428
published
U.
Meyer
Ulrich
P.
Sanders
Peter
J.F.
Sibeyn
Jop F.
3-540-00883-7
C1256428004B93B8-9B6D98DDAF2CC91FC1256D1F0036F1DF-MeySanSib2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018112012-09-1987:931
Conference-Paper
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm
English
IEEE
New York, USA
2003
2004-06-17
462
471
Cambridge, USA
2003-10-11
44th Annual Symposium on Foundations of Computer Science (FOCS-03)
In this paper we introduce the notion of smoothed competitive analysis of
online algorithms. Smoothed analysis has been proposed by Spielman and Teng
\cite{ST01} to explain the behaviour of algorithms that work well in practice
while performing very poorly from a worst case analysis point of view. We
apply this notion to analyze the Multi-Level Feedback (MLF) algorithm to
minimize the total flow time on a sequence of jobs released over time when the
processing time of a job is only known at time of completion.
The initial processing times are integers in the range $[1,2^K]$. We use a
partial bit randomization model, where the initial processing times are
smoothened by changing the $k$ least significant bits under a quite general
class of probability distributions. We show that MLF admits a smoothed
competitive ratio of $O((2^k/\sigma)^3 + (2^k/\sigma)^2 2^{K-k})$, where
$\sigma$ denotes the standard deviation of the distribution. In particular, we
obtain a competitive ratio of $O(2^{K-k})$ if $\sigma = \Theta(2^k)$. We also
prove an $\Omega(2^{K-k})$ lower bound for any deterministic algorithm that is
run on processing times smoothened according to the partial bit randomization
model. For various other smoothening models, including the additive symmetric
smoothening model used by Spielman and Teng \cite{ST01}, we give a higher
lower bound of $\Omega(2^K)$.
A direct consequence of our result is also the first average case analysis of
MLF. We show a constant expected ratio of the total flow time of MLF to the
optimum under several distributions including the uniform distribution.
No
expertsonly
published
L.
Becchetti
Luca
S.
Leonardi
Stefano
A.
Marchetti-Spaccamela
Alberto
G.
Schäfer
Guido
T.
Vredeveld
Tjark
C1256428004B93B8-3CAAB1E7A5E7A119C1256E150031087F-Schäfer2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018172012-09-1987:931
Article
The complexity of economic equilibria for house allocation markets
English
2003
2004-06-15
219
223
Information Processing Letters
88
We prove NP-completeness of deciding the existence of an economic equilibrium
in so-called house allocation markets. House allocation markets are markets
with indivisible goods in which every agent holds exactly one copy of some
good.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9135&did=201817&ver=0
S. P.
Fekete
Sandor P.
M.
Skutella
Martin
G. J.
Woeginger
Gerhard J.
0020-0190
C1256428004B93B8-07975F653CB5FC7CC1256E1C0051D142-Skutella2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018272012-09-1987:931
Conference-Paper
Algorithms and Experiments for the Webgraph
English
Springer
Berlin, Germany
2003
2004-06-14
703
714
Budapest
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
No
expertsonly
published
L.
Laura
Luigi
S.
Leonardi
Stefano
S.
Millozzi
Stefano
U.
Meyer
Ulrich
J.F.
Sibeyn
Jop F.
G.
Di Battista
Giuseppe
U.
Zwick
Uri
0302-9743
C1256428004B93B8-9905E27D2ECB3E7BC1256E150036B925-LLMMS2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018292012-09-1987:931
Article
Reconciling simplicity and realism in parallel disk models
English
2002
2003-09-08
705
723
Parallel Computing
28
For the design and analysis of algorithms that process huge data sets, a
machine model is needed that handles parallel disks. There seems to be
a dilemma between simple and flexible use of such a model and accurate
modelling of details of the hardware. This paper explains how many
aspects of this problem can be resolved. The programming model
implements one large logical disk allowing concurrent access to
arbitrary sets of variable size blocks. This model can
be implemented efficienctly on multiple
independent disks even if zones with different speed,
communication bottlenecks
and failed disks are allowed. These results not only provide useful
algorithmic tools but also imply a theoretical justification for
studying external memory algorithms using simple abstract models.
The algorithmic approach is random redundant placement of data and
optimal scheduling of accesses. The analysis generalizes a previous
analysis for simple abstract external memory models in several ways
(Higher efficiency, variable block sizes, more detailed disk model).
As a side effect, an apparently new Chernoff-Hoeffding bound for sums of
weighted 0-1 random variables is derived.
No
expertsonly
published
joureview
P.
Sanders
Peter
0167-8191
C1256428004B93B8-B35A8F649B98C47FC1256CBE00620418-Sanders2002f
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018342012-09-1987:931
Conference-Paper
Approximating Energy Efficient Paths in Wireless Multi-hop Networks
English
Springer
Berlin, Germany
2003
2004-06-15
230
241
Budapest, Hungary
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
Given the positions of $n$ sites in a radio network
we consider the problem of finding routes between any pair of sites
that minimize energy consumption and do not use more than some
constant number $k$ of hops. Known exact algorithms for this problem
required $\Omega(n \log n)$ per query pair $(p,q)$. In this paper we
relax the exactness requirement and only require approximate
$(1+\epsilon)$ solutions which allows us to derive schemes which
guarantee constant query time using linear space and
$O(n\log n)$ preprocessing time. The dependence on $\epsilon$ is
polynomial in $1/\epsilon$.
One tool used might be of independent interest:
For any pair of points $(p,q)\in P\subseteq\mathbb{Z}^2$
report in constant time the cluster pair $(A,B)$ representing $(p,q)$
in a well-separated pair decomposition of $P$.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9141&did=201834&ver=0
S.
Funke
Stefan
D.
Matijevic
Domagoj
P.
Sanders
Peter
G.
Di Battista
Giuseppe
U.
Zwick
Uri
3-540-20064-9
C1256428004B93B8-1EAC93284072E6C4C1256E150042DA25-Matijevic2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018352012-09-1987:931
Conference-Paper
On the Competitive Ratio for Online Facility Location
English
Springer
Berlin, Germany
2003
2004-06-15
637
652
Eindhoven, The Netherlands
2003-06-30
Automata, languages and programming : 30th International Colloquium, ICALP 2003
Lecture Notes in Computer Science
We consider the problem of Online Facility Location, where demands arrive
online and must be irrevocably assigned to an open facility upon arrival. The
objective is to minimize the sum of facility and assignment costs. We prove
that the competitive ratio for Online Facility Location is $\Theta(\frac{\log
n}{\log\log n})$. On the negative side, we show that no randomized algorithm
can achieve a competitive ratio better than $O(\frac{\log n}{\log\log n})$
against an oblivious adversary even if the demands lie on a line segment. On
the positive side, we present a deterministic algorithm achieving a competitive
ratio of $O(\frac{\log n}{\log\log n})$. The analysis is based on a
hierarchical decomposition of the optimal facility locations such that each
component either is relatively well-separated or has a relatively large
diameter, and a potential function argument which distinguishes between the two
kinds of components.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9142&did=201835&ver=0
D.
Fotakis
Dimitris
J.C.M.
Baeten
Jos C.M.
J.K.
Lenstra
Jan Karel
J.
Parrow
Joachim
G.J.
Woeginger
Gerhard J.
3-540-40493-7
C1256428004B93B8-6A9C56FA859349F5C1256D030043742D-Fot03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018442012-09-1987:931
Conference-Paper
Simple Linear Work Suffix Array Construction
English
Springer
Berlin, Germany
2003
2004-06-15
943
955
Eindhoven, The Netherlands
2003-06-30
Automata, languages and programming : 30th International Colloquium, ICALP 2003
Lecture Notes in Computer Science
A suffix array represents the suffixes of a string in sorted order.
Being a simpler and more compact alternative to suffix trees, it
is an important tool for full text indexing and other string
processing tasks. We introduce the \emph{skew algorithm}
for suffix array construction over integer alphabets that can be
implemented to run in linear time using integer sorting as its only
nontrivial subroutine:\\
1. recursively sort suffixes beginning at positions $i\bmod 3\neq 0$.\\
2. sort the remaining suffixes using the information
obtained in step one.\\
3. merge the two sorted sequences obtained in steps one and two.\\
The algorithm is much
simpler than previous linear time algorithms that
are all based on the more complicated suffix tree data structure.
Since sorting is a well studied problem, we obtain
optimal algorithms for several other models of computation,
e.g.\ external memory with parallel disks, cache oblivious,
and parallel. The adaptations for BSP and EREW-PRAM
are asymptotically faster than the best previously known algorithms.
No
expertsonly
published
J.
Kärkkäinen
Juha
P.
Sanders
Peter
J.C.M.
Baeten
Jos C.M.
J.K.
Lenstra
Jan Karel
J.
Parrow
Joachim
G.J.
Woeginger
Gerhard J.
3540404937
C1256428004B93B8-901BAE3BF9EE93A5C1256D090050B9C2-KarkkainenSanders2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018502012-09-1987:931
Conference-Paper
Certifying and Repairing Solutions to Large LPs - How Good are LP-Solvers?
English
ACM
New York, USA
2003
2004-06-15
255
256
Baltimore, USA
2003-01-12
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)
No
expertsonly
published
M.
Dhiflaoui
Marcel
S.
Funke
Stefan
C.
Kwappik
Carsten
K.
Mehlhorn
Kurt
M.
Seel
Michael
E.
Schömer
Elmar
R.
Schulte
Ralph
D.
Weber
Dennis
C1256428004B93B8-F01D6B673BC1A37AC1256CC200533255-dfkmsssw2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018512012-09-1987:931
Conference-Paper
Experimental comparison of heuristic and approximation algorithms for uncapacitated facility location
English
Springer
Berlin, Germany
2003
2004-06-17
165
178
Ascona, Switzerland
2003-05-26
Experimental and efficient algorithms : Second International Workshop, WEA 2003
Lecture Notes in Computer Science
No
expertsonly
published
M.
Hoefer
Martin
K.
Jansen
Klaus
M.
Margraf
Marian
M.
Mastrolli
Monaldo
J.D.P.
Rolim
José D. P.
3-540-40205-5
C1256428004B93B8-0FF050BD4B94A840C1256EB60050AD58-Hoefer03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018572012-09-1987:931
Conference-Paper
Space Efficient Hash Tables with Worst Case Constant Access Time
English
Springer
Berlin, Germany
2003
2004-06-11
271
282
Berlin, Germany
2003-02-27
Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003)
Lecture Notes in Computer Science
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$d$-ary Cuckoo Hashing}
and show how this yields a simple hash table data structure that stores $n$
elements in $(1+\epsilon)\,n$ memory cells, for any constant $\epsilon > 0$.
Assuming uniform hashing, accessing or deleting table entries takes at most $d
= O(\ln\frac{1}{\epsilon})$ probes and the expected amortized insertion time is
constant. This is the first dictionary that has worst case constant access time
and expected constant update time, works with $(1+\epsilon)\,n$ space, and
supports satellite information. Experiments indicate that $d=4$ choices suffice
for $\epsilon \approx 0.03$. We also describe a hash table data structure using
explicit constant time hash functions, using at most $d=
O(\ln^2\frac{1}{\epsilon})$ probes in the worst case.
A corollary is an expected linear time algorithm for finding maximum
cardinality matchings in a rather natural model of sparse random bipartite
graphs.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9148&did=201857&ver=0
D.
Fotakis
Dimitris
R.
Pagh
Rasmus
P.
Sanders
Peter
P.G.
Spirakis
Paul G.
H.
Alt
Helmut
M.
Habib
Michel
3-540-00623-0
C1256428004B93B8-6A3318B88A19B993C1256CD800533F95-FPSS03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018592012-09-1987:931
Conference-Paper
A Practical Minimum Spanning Tree Algorithm Using the Cycle Property
English
Springer
Berlin, Germany
2003
2004-06-25
679
690
Budapest, Hungary
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
No
expertsonly
published
I.
Katriel
Irit
P.
Sanders
Peter
J.L.
Träff
Jesper Larsson
G.
Di Battista
Giuseppe
U.
Zwick
Uri
3540200649
C1256428004B93B8-497634CD780A862DC1256E1C006859C6-KatSanTra03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018612012-09-1987:931
InBook
Memory hierarchies - models and lower bounds
English
Springer
Berlin, Germany
2003
2004-06-17
1
10
2625
Algorithms for memory hierarchies
Meyer, Ulrich;Sanders, Peter;Sibeyn, Jop
No
expertsonly
published
notspecified
P.
Sanders
Peter
U.
Meyer
Ulrich
P.
Sanders
Peter
J.
Sibeyn
Jop
3-540-00883-7
C1256428004B93B8-1684EE73A63CE3FBC1256EB6004F403D-PS03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018632012-09-1987:931
Conference-Paper
Nearest Neighbors Can Be Found Efficiently If the Dimension Is Small Relative to the Input Size
English
Springer
New York, USA
2003
2004-06-17
440
454
Siena, Italy
2003-01-08
Database Theory - ICDT 2003 : 9th International Conference
Lecture Notes in Computer Science
No
expertsonly
published
M.
Hagedoorn
Michiel
D.
Calvanese
Diego
M.
Lenzerini
Maurizio
R.
Motwani
Rajeev
3-540-00323-1
C1256428004B93B8-244F00DC9AEB81ADC1256CAF005D7C9F-Hagedoorn2003:nncbfe
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
The copyright for this distribution is held by Springer.
© Springer-Verlag
http://www.springer.de/comp/lncs/index.html
oai:edoc.mpg.de:2018642012-09-1987:931
Conference-Paper
Scheduling and Traffic Allocation for Tasks with Bounded Splittability
English
Springer
Berlin, Germany
2003
2004-06-15
500
510
Bratislava
2003-08-25
Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003
Lecture Notes in Computer Science
No
expertsonly
published
P.
Krysta
Piotr
P.
Sanders
Peter
B.
Vöcking
Berthold
B.
Rovan
Branislav
P.
Vojtáš
Peter
3540406719
C1256428004B93B8-572C4F06E92A32BDC1256E1D003E35D2-KSV03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018692012-09-1987:931
Conference-Paper
Fast Lightweight Suffix Array Construction and Checking
English
Springer
Heidelberg, Germany
2003
2004-08-02
55
69
Morelia, Michoacán, Mexico
2003-06-25
Combinatorial Pattern Matching: 14th Annual Symposium, CPM 2003
Lecture Notes in Computer Science
We describe an algorithm that, for any $v\in[2,n]$, constructs
the suffix array of a string of length $n$ in $\Oh{vn + n \log
n}$ time using $\Oh{v+n/\sqrt{v}}$ space in addition to the
input (the string) and the output (the suffix array). By setting
$v=\log n$, we obtain an $\Oh{n \log n}$ time algorithm using
$\Oh{n/\sqrt{\log n}}$ extra space. This solves the open problem
stated by Manzini and Ferragina [ESA\;'02] of whether there
exists a lightweight (sublinear extra space) $\Oh{n \log n}$ time
algorithm. The key idea of the algorithm is to first sort a
sample of suffixes chosen using mathematical constructs called
difference covers. The algorithm is not only lightweight but also
fast in practice as demonstrated by experiments. Additionally,
we describe fast and lightweight suffix array checkers, i.e.,
algorithms that check the correctness of a suffix array.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9149&did=201869&ver=0
S.
Burkhardt
Stefan
J.
Kärkkäinen
Juha
R.
Baeza-Yates
R.
E.
Chávez
E.
M.
Crochemore
M.
0302-9743
C1256428004B93B8-3E2B1773D0314EDEC1256E8A002B0F6D-Burkhardt2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018702012-09-1987:931
Conference-Paper
The factor algorithm for regular all-to-all communication on clusters of SMP nodes
English
Springer
Berlin, Germany
2002
2003-08-28
799
803
Paderborn
2002-08-27
Proceedings of the 8th International Euro-Par Conference
Lecture Notes in Computer Science
No
expertsonly
published
notspecified
P.
Sanders
Peter
J.L.
Träff
Jesper Larsson
B.
Monien
Burkhard
R.
Feldman
Rainer
3-450-67956-1
C1256428004B93B8-CB53878DBD30EC6EC1256CBE0062DC16-Sanders2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018712012-09-1987:931
Conference-Paper
Random Arc Allocation and Applications to Disks, Drums and DRAMs
English
Springer
Berlin, Germany
2002
2003-08-29
121
130
Turku
2002-07-03
Algorithm theory, SWAT 2002 : 8th Scandinavian Workshop on Algorithm Theory
Lecture Notes in Computer Science
No
expertsonly
published
notspecified
P.
Sanders
Peter
B.
Vöcking
Berthold
M.
Penttonen
Martti
E.
Meineche Schmidt
Erik
3-540-43866-1
C1256428004B93B8-87AD39F4B8488430C1256CBE0063F98B-Sanders2002g
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018742012-09-1987:931
InBook
The reliable algorithmic software challenge RASC : dedicated to Thomas Ottmann on the occassion of his 60th birthday
English
Springer
Berlin, Germany
2003
2004-06-28
255
263
2598
Computer Science in Perspective : essays dedicated to Thomas Ottmann
Klein, Rolf; Six, Hans-Werner; Wegner, Lutz
No
expertsonly
published
notspecified
K.
Mehlhorn
Kurt
R.
Klein
Rolf
H.-W.
Six
Hans-Werner
L.
Wegner
Lutz
3-540-00579-X
C1256428004B93B8-A185BAA82C068ABBC1256E1D0048A367-KM03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018782012-09-1987:931
Article
Tail bounds and expectations for random arc allocation and applications
English
2003
2004-06-15
225
244
Combinatorics, Probability and Computing
12
No
expertsonly
published
joureview
P.
Sanders
Peter
B.
Vöcking
Berthold
0963-5483
C1256428004B93B8-6F1F3105E951E1D4C1256E1C0069B7E0-SanVoe03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018852012-09-1987:931
Article
Preemptive scheduling with rejection
English
2003
2004-06-15
361
374
Mathematical Programming
94
We consider the problem of preemptively scheduling a set of $n$ jobs
on $m$ (identical, uniformly related, or unrelated) parallel
machines. The scheduler may reject a subset of the jobs and thereby
incur job-dependent penalties for each rejected job, and he must
construct a schedule for the remaining jobs so as to optimize the
preemptive makespan on the $m$ machines plus the sum of the
penalties of the jobs rejected.
We provide a complete classification of these scheduling problems
with respect to complexity and approximability. Our main results
are on the variant with an arbitrary number of unrelated machines.
This variant is \apx-hard, and we design a $1.58$-approximation
algorithm for it. All other considered variants are weakly
\np-hard, and we provide fully polynomial time approximation schemes
for them. Finally, we argue that our results for unrelated machines
can be carried over to the corresponding preemptive open shop
scheduling problem with rejection.
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9151&did=201885&ver=0
H.
Hoogeveen
Han
M.
Skutella
Martin
G.J.
Woeginger
Gerhard J.
0025-5610
C1256428004B93B8-0DAA99A7CBBA7B62C1256E20004335BB-HoogeveenSkutellaWoeginger2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018892012-09-1987:931
Article
The Safari Interface for Visualizing Time-dependent Volume Data Using Iso-surfaces and Contour Spectra
English
2003
2004-06-15
97
116
Computational Geometry - Theory and Applications
25
We describe a geometric basis for the visualization of time-varying
volume data of one or several variables as they occur in scientific
and engineering applications. We demonstrate a prototype
interface for gridded data, extending the contour spectrum interface of
Bajaj, Pascucci, and Schikore to higher dimensions and to topological
properties that are not decomposable. We also describe a data structure
for pentatope meshes that supports the computation of isosurfaces and their
properties.
No
expertsonly
published
joureview
L.
Kettner
Lutz
J.
Rossignac
Jarek
J.
Snoeyink
Jack
0925-7721
C1256428004B93B8-3E3420DF169FD902C1256D0A005BBD78-Kettner2003Safari
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018902012-09-1987:931
Conference-Paper
Fast Bound-Consistency for the Global Cardinality Constraint
English
Springer
Berlin, Germany
2003
2004-06-17
437
451
Kinsale, Ireland
2003-09-29
Principles and Practice of Constraint Programming - CP 2003 : 9th International Conference, CP 2003
Lecture Notes in Computer Science
No
expertsonly
published
I.
Katriel
Irit
S.
Thiel
Sven
F.
Rossi
Francesca
3-540-20202-1
C1256428004B93B8-59ADBF4D9D0B5ACCC1256E1400562806-KT03:gcc
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2018912012-09-1987:931
Conference-Paper
Boolean Operations on 3D Selective Nef Complexes: Data Structure, Algorithms, and Implementation
English
Springer
Berlin, Germany
2003
2004-06-15
654
666
Budapest, Hungary
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
We describe a data structure for three-dimensional Nef complexes, algorithms
for boolean operations on them, and our implementation of data structure and
algorithms. Nef polyhedra were introduced by W. Nef in his seminal 1978 book on
polyhedra. They are the closure of half-spaces under boolean operations and can
represent non-manifold situations, open and closed boundaries, and mixed
dimensional complexes. Our focus lies on the generality of the data structure,
the completeness of the algorithms, and the exactness and efficiency of the
implementation. In particular, all degeneracies are handled.
No
expertsonly
published
M.
Granados
Miguel
P.
Hachenberger
Peter
S.
Hert
Susan
L.
Kettner
Lutz
K.
Mehlhorn
Kurt
M.
Seel
Michael
G.
Di Battista
Giuseppe
U.
Zwick
Uri
C1256428004B93B8-D0F786CC6723EB72C1256E2F0050063D-ghhkms-bo3ds-03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019002012-09-1987:931
Article
Asynchronous Scheduling of Redundant Disk Arrays
English
2003
2004-06-15
1170
1184
IEEE Transactions on Computers
52
No
expertsonly
published
joureview
P.
Sanders
Peter
0018-9340
C1256428004B93B8-7A96261BEC5D4379C1256E1D00382C4F-Sanders2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019022012-09-1987:931
Article
Scheduling multicasts on unit-capacity trees and meshes
English
2003
2004-06-18
567
611
Journal of Computer and System Sciences
66
No
expertsonly
published
joureview
M.R.
Henzinger
Monika R.
S.
Leonardi
Stefano
0022-0000
C1256428004B93B8-40C302392208C217C1256EB7002AFB5F-Leonardi03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019062012-09-1987:931
Article
A Bandwidth Latency Tradeoff for Broadcast and Reduction
English
2003
2004-06-15
33
38
Information Processing Letters
86
No
expertsonly
published
joureview
P.
Sanders
Peter
J.F.
Sibeyn
Jop F.
0020-0190
C1256428004B93B8-241FAA1B09B19F9EC1256E1D00360D54-SanSib03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019102012-09-1987:931
Article
Infimaximal frames: A technique for making lines look like segments
English
2003
2004-06-15
241
255
International Journal of Computational Geometry & Applications
13
No
expertsonly
published
joureview
K.
Mehlhorn
Kurt
M.
Seel
Michael
C1256428004B93B8-A569041E8BA55F92C1256E2000412135-Mehlhorn157
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019112012-09-1987:931
Conference-Paper
Asynchronous Parallel Disk Sorting
English
ACM
New York, USA
2003
2004-06-17
138
148
San Diego, USA
2004-01-15
Proceedings of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA-03)
No
expertsonly
published
R.
Dementiev
Roman
P.
Sanders
Peter
1581136617
C1256428004B93B8-6D08EEF2E0EA5BDFC1256D0B0031DE12-DemSan03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019122012-09-1987:931
Article
A Heuristic for Dijkstra's Algorithm With Many Targets and its Use in Weighted Matching Algorithms
English
2003
2004-06-17
75
88
Algorithmica
36
We consider the single-source many-targets shortest-path (SSMTSP) problem in
directed graphs with non-negative
edge weights. A source node $s$ and a target set $T$ is specified and the goal
is to compute a shortest path from $s$ to a node in $T$.
Our interest in the shortest path problem with many targets stems from its use
in weighted bipartite matching algorithms. A weighted bipartite matching in a
graph with $n$ nodes on each side reduces to $n$ SSMTSP problems, where the
number
of targets varies between $n$ and $1$.
The SSMTSP problem can be solved by Dijkstra's algorithm. We describe a
heuristic
that leads to a significant improvement in running time for the weighted
matching
problem; in our experiments a speed-up by up to a factor of 12 was achieved.
We also present a partial analysis that gives some theoretical support for our
experimental findings.
No
expertsonly
published
joureview
H.
Bast
Holger
K.
Mehlhorn
Kurt
G.
Schäfer
Guido
H.
Tamaki
Hisao
C1256428004B93B8-6EE356D1B824CE83C1256D03005D49A1-BMST03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019162012-09-1987:931
Conference-Paper
Improving Linear Programming Approaches for the Steiner Tree Problem
English
Springer
Berlin, Germany
2003
2004-06-17
1
14
Ascona, Switzerland
2003-05-26
Experimental and efficient algorithms : Second International Workshop, WEA 2003
Lecture Notes in Computer Science
We present two theoretically interesting and empirically successful
techniques for improving the linear programming approaches, namely
graph transformation and local cuts, in the context of the
Steiner problem. We show the impact of these techniques on the
solution of the largest benchmark instances ever solved.
No
expertsonly
published
E.
Althaus
Ernst
T.
Polzin
Tobias
S.
Vahdati Daneshmand
Siavash
K.
Jansen
Klaus
M.
Margraf
Marian
M.
Mastrolli
Monaldo
J.D.P.
Rolim
José D. P.
C1256428004B93B8-E5856AEC7CE632A3C1256D0A00535C9A-AlPoVa2003-lpimprove
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019192012-09-1987:931
Conference-Paper
Packing a Trunk
English
Springer
Berlin, Germany
2003
2004-06-14
618
629
Budapest, Hungary
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
We report on a project with a German car manufacturer. The task
is to compute (approximate) solutions to a specific large-scale
packing problem. Given a polyhedral model of a car trunk, the
aim is to pack as many identical boxes of size $4 × 2 × 1$ units
as possible into the interior of the trunk. This measure is
important for car manufacturers, because it is a standard in the
European Union.
First, we prove that a natural formal variant of this problem is
NP-complete. Further, we use a combination of integer linear
programming techniques and heuristics that exploit the geometric
structure to attack this problem. Our experiments show that for
all considered instances, we can get very close to the optimal
solution in reasonable time.
No
expertsonly
published
notspecified
http://edoc.mpg.de/get.epl?fid=9161&did=201919&ver=0
F.
Eisenbrand
Friedrich
S.
Funke
Stefan
J.
Reichel
Joachim
E.
Schömer
Elmar
G.
Di Battista
Giuseppe
U.
Zwick
Uri
3-540-20064-9
C1256428004B93B8-A19A49092CA94DCFC1256E15002E4B68-Reichel2003
MPI für Informatik
Algorithms and Complexity Group
MPI für Informatik
Discrete Optimization Group
2012-09-19 10:13:15.652552
(c) Springer-Verlag
oai:edoc.mpg.de:2019232012-09-1987:931
Conference-Paper
Isoperimetric Inequalities and Width Parameters of Graphs
English
Springer
Heidelberg
2003
2004-06-17
385
393
Big Sky, Montana
2003-07-25
Computing and Combinatorics : 9th Annual International Conference, COCOON 2003
Lecture Notes in Computer Science
No
expertsonly
published
notspecified
K.
Telikepalli
Kavitha
S.
Chandran
Sunil
C.R.
Subramanian
C. R.
T.
Warnow
Tandy
B.
Zhu
Binhai
C1256428004B93B8-D4C265756B266ADAC1256E1500400386-Telikepalli2003
MPI für Informatik
Algorithms and Complexity Group
MPI für Informatik
Discrete Optimization Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019252012-09-1987:931
Book
Elliptic Curves : A Computational Approach
English
de Gruyter
Berlin, Germany
2003
31
The purpose of the present text is to give an elementary
introduction to the arithmetic of elliptic curves over number
fields from a computational point of view. This branch of
number theory is particularly accessible to computer assisted
calculations, and the authors make use of this feature by
approaching the theory from a computational point of view.
Specifically, the computer-algebra package SIMATH is applied
on several occasions.
No
notspecified
367
published
S.
Schmitt
Susanne
H. G.
Zimmer
Horst G.
3-11-016808-1
C1256428004B93B8-67C2134CD036FE7EC1256E160031EE01-Schmitt2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019272012-09-1987:931
Article
Approximating Minimum Size 1,2-Connected Networks
English
2003
2004-06-15
267
288
Discrete Applied Mathematics
125
No
expertsonly
published
joureview
P.
Krysta
Piotr
C1256428004B93B8-F1C22A06BBC824F1C1256D180048A1C9-Krysta2003b
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019342012-09-1987:931
Article
Optimal Search for Rationals
English
2003
2004-06-15
23
26
Information Processing Letters
86
No
expertsonly
published
joureview
S.
Kwek
St.
K.
Mehlhorn
Kurt
C1256428004B93B8-7BB72399D6E566FBC1256E2000449EF3-xxxx
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019362012-09-1987:931
Article
Scanning multiple sequences via cache memory
English
2003
2004-06-15
75
93
Algorithmica
35
No
expertsonly
published
joureview
K.
Mehlhorn
Kurt
P.
Sanders
Peter
0178-4617
C1256428004B93B8-E0E179EACB48E199C1256E1D00390DB7-MehSan03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019372012-09-1987:931
Article
Average-case complexity of single-source shortest-path algorithms: lower and upper bounds
English
2003
2004-06-15
91
134
Journal of Algorithms
48
No
expertsonly
published
joureview
U.
Meyer
Ulrich
0196-6774
C1256428004B93B8-1D9EA287DEE4A889C1256D1F003847DB-Meyer2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019382012-09-1987:931
Article
On Steiner trees and minimum spanning trees in hypergraphs
English
2003
2004-06-17
12
20
Operations Research Letters
31
No
expertsonly
published
joureview
T.
Polzin
Tobias
S.
Vahdati Daneshmand
Siavash
0167-6377
C1256428004B93B8-E49C6DE8DB1346A6C1256C72004783C9-Polzin2002-MSTH
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019412012-09-1987:931
Article
Data Management in Networks: Experimental Evaluation of a Provably Good Strategy
English
2003
2004-06-17
217
245
Theory of Computing Systems
35
No
expertsonly
published
joureview
C.
Krick
Christof
F.
Meyer auf der Heide
Friedhelm
H.
Räcke
Harald
B.
Vöcking
Berthold
M.
Westermann
Matthias
C1256428004B93B8-84C97EA9D5963FEDC1256D500047E389-Vöcking2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019442012-09-1987:931
InBook
Full-Text Indexes in External Memory
English
Springer
Berlin, Germany
2003
2004-06-16
149
170
2625
Algorithms for Memory Hierarchies
Meyer, Ulrich;Sanders, Peter;Sibeyn, Jop
No
expertsonly
published
notspecified
J.
Kärkkäinen
Juha
S. S.
Rao
S. Srinivasa
U.
Meyer
Ulrich
P.
Sanders
Peter
J.
Sibeyn
Jop
3-540-00883-7
C1256428004B93B8-2055A8CDA4A9084BC1256CE5006F11BC-Karkkainen2003a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019452012-09-1987:931
Conference-Paper
Polynomial Time Algorithms For Network Information Flow
English
ACM
New York, USA
2003
2004-06-17
286
294
San Diego, USA
2004-01-15
Proceedings of the 15th ACM Symposium on Parallel Algorithms and Architectures (SPAA-03)
No
expertsonly
published
P.
Sanders
Peter
S.
Egner
Sebastian
L.
Tolhuizen
Ludo
1581136617
C1256428004B93B8-B8EA4B673B33DF87C1256D0B00317B75-SET03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019542012-09-1987:931
Conference-Paper
Certifying algorithms for recognizing interval graphs and permutation graph
English
ACM
New York, USA
2003
2004-06-17
158
167
Baltimore
2004-01-12
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)
No
expertsonly
published
D.
Kratsch
Dieter
R.
McConnell
R.
K.
Mehlhorn
Kurt
J.
Spinrad
J.
C1256428004B93B8-90DAACD3D4A0C6A8C1256E20004505E1-xxxx
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019552012-09-1987:931
Conference-Paper
An experimental study of k-splittable scheduling for DNS-based traffic allocation
English
Springer
Berlin, Germany
2003
2004-06-17
230
235
Klagenfurt, Austria
2003-08-26
Euro-Par 2003 parallel processing : 9th International Euro-Par Conference ; proceedings
Lecture Notes in Computer Science
No
expertsonly
published
A.
Agarwal
Amit
T.
Agarwal
Tarun
S.
Chopra
Sumit
A.
Feldmann
Anja
N.
Kammenhuber
Nils
P.
Krysta
Piotr
B.
Vöcking
Berthold
H.
Kosch
Harald
L.
Böszörményi
László
H.
Hellwagner
Hermann
3-540-40788-X
C1256428004B93B8-E93B762BD4F63C49C1256EB6004C1450-Agarwal03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019562012-09-1987:931
Article
On external-memory planar depth first search
English
2003
2004-06-16
105
129
Journal of Graph Algorithms and Applications
7
No
expertsonly
published
joureview
L.
Arge
Lars
U.
Meyer
Ulrich
L.
Toma
Laura
N.
Zeh
Norbert
1526-1719
C1256428004B93B8-5E7BD9F75DAB0192C1256D1F0037E085-AMTZ03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019572012-09-1987:931
Conference-Paper
Scheduling to minimize flow time metrics
English
IEEE
Los Alamitos, USA
2003
2004-08-02
223b
CDROM
Nice, France
2003-04-22
International Parallel and Distributed Processing Symposium (IPDPS-03)
No
expertsonly
published
L.
Becchetti
Luca
S.
Leonardi
Stefano
A.
Marchetti-Spaccamela
Alberto
G.
Schäfer
Guido
0-7695-1926-1
C1256428004B93B8-C69CECCC48B5E4C1C1256EB600297B12-Becchetti2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019592012-09-1987:931
Conference-Paper
Efficient Algorithms for Abelian group isomorphism and related problems
English
Springer
Heidelberg, Germany
2003
2004-06-17
277
288
IIT Mumbai, India.
2003-12-15
FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science : 23rd Conference
Lecture Notes in Computer Science
No
expertsonly
published
K.
Telikepalli
Kavitha
P.
Pandya
Paritosh
J.
Radhakrishnan
Jaikumar
C1256428004B93B8-63E1703F30F40FDDC1256E15003F7402-Telikepalli2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019612012-09-1987:931
Conference-Paper
On Shortest Paths in Line Arrangements
English
Dalhousie University
Halifax, Canada
2003
2004-06-17
170
173
Dalhousie University, Halifax, Canada
2003-08-11
15th Canadian Conference in Computational Geometry (CCCG-03)
No
expertsonly
published
K.
Telikepalli
Kavitha
M.
McAllister
Michael
C1256428004B93B8-103A88BDE76ACE59C1256E15003EB2F0-Telikepalli2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019622012-09-1987:931
InBook
Elementary Graph Algorithms in External Memory
English
Springer
Berlin, Germany
2003
2004-06-15
62
84
2625
Algorithms for Memory Hierarchies
Meyer, Ulrich; Sanders, Peter; Sibeyn, Jop
No
expertsonly
published
notspecified
I.
Katriel
Irit
U.
Meyer
Ulrich
U.
Meyer
Ulrich
P.
Sanders
Peter
J.
Sibeyn
Jop
3-540-00883-7
C1256428004B93B8-EFF762A7CFE3144EC1256D1F00376063-KatMey03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019652012-09-1987:931
Conference-Paper
Sweep Synchronization as a Global Propagation Mechanism
English
Centre for Research on Transportation
Montreal, Canada
2003
2004-06-11
139
152
Montreal, Canada
2003-05-08
Fifth International Workshop on Integration of AI and OR Techniques
in Constraint Programming for Combinatorial Optimization Problems
No
expertsonly
published
N.
Beldiceanu
Nicolas
M.
Carlsson
Mats
S.
Thiel
Sven
C1256428004B93B8-3FAF0AAFE353E7E7C1256D8E00335FA2-BCT03:SweepSynchro
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019662012-09-1987:931
Conference-Paper
I/O-Efficient Undirected Shortest Paths
English
Springer
Berlin, Germany
2003
2004-07-14
434
445
Budapest
2003-09-16
Algorithms - ESA 2003: 11th Annual European Symposium
Lecture Notes in Computer Science
No
expertsonly
published
U.
Meyer
Ulrich
N.
Zeh
Norbert
G.
Di Battista
Giuseppe
U.
Zwick
Uri
0302-9743
C1256428004B93B8-8E8A3EE6223C26DDC1256E15003565DC-MeyZeh2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019692012-09-1987:931
Conference-Paper
Power Efficient Range Assignment in Ad-hoc Wireless
English
IEEE
New Orleans, USA
2003
2004-06-17
1889
1894
New Orleans, USA
2003-03-16
Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC-03)
No
expertsonly
published
E.
Althaus
Ernst
G.
Calinescu
Gruia
I.
Mandoiu
Ion
S.
Prasad
Sushil
N.
Tchervenski
Nickolay
A.
Zelikovsly
Alexander
C1256428004B93B8-C9B7B811A0DFA258C1256D02004DD502-Althaus2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019712012-09-1987:931
Conference-Paper
Optimizing Misdirection
English
ACM
New York, USA
2003
2004-06-14
192
201
Baltimore, USA
2003-01-12
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)
No
expertsonly
published
P.
Berman
Piotr
P.
Krysta
Piotr
C1256428004B93B8-5D8708E61414643EC1256D1800485C01-Berman2003+
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019722012-09-1987:931
Conference-Paper
Random Knapsack in Expected Polynomial Time
English
ACM
New York, USA
2003
2004-06-17
232
241
San Diego, USA
2003-06-09
Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC-03)
In this paper, we present the first average-case analysis proving an expected
polynomial running time for an exact algorithm for the 0/1 knapsack problem.
In particular, we prove, for various input distributions, that the number of
{\em dominating solutions\/} (i.e., Pareto-optimal knapsack fillings)
to this problem is polynomially bounded in the number of available items.
An algorithm by Nemhauser and Ullmann can enumerate these solutions very
efficiently so that a polynomial upper bound on the number of dominating
solutions
implies an algorithm with expected polynomial running time.
The random input model underlying our analysis is very general
and not restricted to a particular input distribution. We assume adversarial
weights and randomly drawn profits (or vice versa). Our analysis covers general
probability
distributions with finite mean, and, in its most general form, can even
handle different probability distributions for the profits of different items.
This feature enables us to study the effects of correlations between profits
and weights. Our analysis confirms and explains practical studies showing
that so-called {\em strongly correlated\/} instances are harder to solve than
{\em weakly correlated\/} ones.
No
expertsonly
published
R.
Beier
Rene
B.
Vöcking
Berthold
1-58113-674-9
C1256428004B93B8-3238DECAE400413DC1256D1F0040A7FE-Beier2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019742012-09-1987:931
Article
An Efficient Algorithm for the Configuration Problem of Dominance Graphs
English
2003
2004-06-23
194
219
Journal of Algorithms
48
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9167&did=201974&ver=0
E.
Althaus
Ernst
D.
Duchier
Denys
A.
Koller
Alexander
K.
Mehlhorn
Kurt
J.
Niehren
Joachim
S.
Thiel
Sven
0196-6774
C1256428004B93B8-E128ACDA946D7067C1256D8E0031A9DC-ADKMNT03:dominance
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019782012-09-1987:931
Article
Proof of a conjecture of Bollobas and Eldridge for graphs of maximum degree three
English
2003
2004-06-17
35
72
Combinatorica
23
Let $G_1$ and $G_2$ be simple graphs on $n$ vertices. If there are
edge-disjoint copies of $G_1$ and $G_2$ in $K_n$, then we say there is
a packing of $G_1$ and $G_2$. A conjecture of Bollob\'as and Eldridge
~\cite{be78} asserts that if $(\Delta(G_1)+1)(\Delta(G_2)+1)\le n+1$ then
there is a packing of $G_1$ and $G_2$. We prove this conjecture when
$\Delta(G_1)=3$, for sufficiently large $n$.
No
expertsonly
published
joureview
B.
Csaba
Bela
0209-9683
C1256428004B93B8-6674AB6492ED6BE8C1256D1F0048AEF5-Csaba2003a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019802012-09-1987:931
Article
Randomized Pursuit-Evasion in Graphs
English
2003
2004-06-15
225
244
Combinatorics, Probability and Computing
12
No
expertsonly
published
joureview
http://edoc.mpg.de/get.epl?fid=9170&did=201980&ver=0
M.
Adler
Micah
H.
Räcke
Harald
N.
Sivadasan
Naveen
C.
Sohler
Christian
B.
Vöcking
Berthold
0963-5483
C1256428004B93B8-84FD4682AF9079ECC1256EAC0033DB77-Sivadas2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019862012-09-1987:931
Conference-Paper
Curve Reconstruction from Noisy Samples
English
ACM
New York, USA
2003
2004-06-15
420
429
San Diego, USA
2003-06-08
Proceedings of the 19th Annual Symposium on Computational Geometry (SCG-03)
No
expertsonly
published
S.-W.
Cheng
Siu-Wing
S.
Funke
Stefan
M.J.
Golin
Mordecai J.
P.
Kumar
Piyush
S.-H.
Poon
Sheung-Hung
E.A.
Ramos
Edgar A.
C1256428004B93B8-2D7B0E82C02E9289C1256D100041FB22-CFGKPR2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2019972012-09-1987:931
Conference-Paper
Solving geometric optimization problems using graphics hardware
English
Blackwell
Oxford, UK
2003
2004-06-17
441
451
Granada, Spain
2003-09-01
EUROGRAPHICS 2003 : the European Association for Computer Graphics 24th Annual Conference
Computer Graphics Forum
No
expertsonly
published
M.
Denny
Markus
P.
Brunet
Pere
D.W.
Fellner
Dieter W.
C1256428004B93B8-5485FE1E6D4A34A7C1256EB6004DF3C3-Denny03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020032012-09-1987:931
InBook
Automatic Layout and Labelling of State Diagrams
English
Springer
Berlin, Germany
2003
2004-06-15
584
608
Mathematics: Key Technology for the Future : Joint Projects Between Universities and Industry
Jäger, Willi; Krebs, Hans-Joachim
No
expertsonly
published
notspecified
G. W.
Klau
Gunnar W.
P.
Mutzel
Petra
W.
Jäger
Willi
H.-J.
Krebs
Hans-Joachim
3-540-44220-0
C1256428004B93B8-E1CB828E67BBA0EAC12569D9004C42B4-KM03
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020082012-09-1987:931
Conference-Paper
A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph
English
ACM
New York, USA
2003
2004-06-11
517
522
Baltimore, USA
2003-01-12
Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)
No
expertsonly
published
F.
Eisenbrand
Friedrich
S.
Funke
Stefan
N.
Garg
Naveen
J.
Könemann
Jochen
C1256428004B93B8-C0EEC62F7F62BD47C1256CC200523755-efgk2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020092012-09-1987:931
Conference-Paper
Multicommodity Flows Over Time: Efficient Algorithms and Complexity
English
Springer
Berlin, Germany
2003
2004-06-15
397
409
Eindhoven, The Netherlands
2003-06-30
Automata, languages and programming : 30th International Colloquium, ICALP 2003
Lecture Notes in Computer Science
Flow variation over time is an important feature in network flow
problems arising in various applications such as road or air traffic
control, production systems, communication networks (e.g., the
Internet), and financial flows. The common characteristic are
networks with capacities and transit times on the arcs which specify
the amount of time it takes for flow to travel through a particular
arc. Moreover, in contrast to static flow problems, flow values on
arcs may change with time in these networks.
While the `maximum $s$-$t$-flow over time' problem can be solved
efficiently and `min-cost flows over time' are known to be NP-hard,
the complexity of (fractional) `multicommodity flows over time' has
been open for many years. We prove that this problem is NP-hard,
even for series-parallel networks, and present new and efficient
algorithms under certain assumptions on the transit times or on the
network topology. As a result, we can draw a complete picture of
the complexity landscape for flow over time problems.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9174&did=202009&ver=0
A.
Hall
Alex
S.
Hippler
Steffen
M.
Skutella
Martin
J.C.M.
Baeten
Jos C.M.
J.K.
Lenstra
Jan Karel
J.
Parrow
Joachim
G.J.
Woeginger
Gerhard J.
3-540-40493-7
C1256428004B93B8-135515929AE279BBC1256E20003919FE-HallHipplerSkutella2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020342012-09-1987:931
Article
Δ-stepping: a parallelizable shortest path algorithm
English
2003
2004-06-15
114
152
Journal of Algorithms
49
No
expertsonly
published
joureview
U.
Meyer
Ulrich
P.
Sanders
Peter
0196-6774
C1256428004B93B8-AC85C4C86B19B506C1256E1500325F12-Meyer2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020382012-09-1987:931
Article
Tight Degree Bounds for Pseudo-triangulations of Points
English
2003
2004-06-15
3
12
Computational Geometry - Theory and Applications
25
We show that every set of $n$ points in general position has a
minimum pseudo-triangulation whose maximum vertex degree is five.
In addition, we demonstrate that every point set in general position
has a minimum pseudo-triangulation whose maximum face degree is four
(i.e.\ each interior face of this pseudo-triangulation has at most
four vertices). Both degree bounds are tight. Minimum
pseudo-triangulations realizing these bounds (individually but not
jointly) can be constructed in $O(n \log n)$ time.
No
expertsonly
published
joureview
L.
Kettner
Lutz
D.
Kirkpatrick
David
A.
Mantler
Andrea
J.
Snoeyink
Jack
B.
Speckmann
Bettina
F.
Takeuchi
Fumihiko
0925-7721
C1256428004B93B8-A20C349D3E243F5FC1256D0A005B3F31-Kettner2003DegreeBound
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020432012-09-1987:931
Conference-Paper
An FPTAS for Quickest Multicommodity Flows with Inflow-Dependent Transit Times
English
Springer
Berlin, Germany
2003
2004-06-17
71
82
Princeton, USA
2003-08-24
Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques ; 6th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2003 and 7th International Workshop on Randomization and Approximation Techniques in Computer Science, RANDOM 2003
Lecture Notes in Computer Science
Given a network with capacities and transit times on the arcs, the
quickest flow problem asks for a `flow over time' that satisfies
given demands within minimal time. In the setting of flows over
time, flow on arcs may vary over time and the transit time of an arc
is the time it takes for flow to travel through this arc. In most
real-world applications (such as, e.g., road traffic, communication
networks, production systems, etc.), transit times are not fixed but
depend on the current flow situation in the network. We consider
the model where the transit time of an arc is given as a
nondecreasing function of the rate of inflow into the arc. We prove
that the quickest $s$-$t$-flow problem is NP-hard in this setting
and give various approximation results, including an FPTAS for the
quickest multicommodity flow problem with bounded cost.
No
expertsonly
published
A.
Hall
Alex
K.
Langkau
Katharina
M.
Skutella
Martin
S.
Arora
Sanjeev
K.
Jansen
Klaus
J.D.P.
Rolim
Jose D. P.
A.
Sahai
Amit
3-540-40770-7
C1256428004B93B8-91589E2EDD7B2533C1256E20003753CF-HallLangkauSkutella2003
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020442012-09-1987:931
Conference-Paper
Smoothed Analysis of Three Combinatorial Problems
English
Springer
Berlin, Germany
2003
2004-06-15
198
207
Bratislava, Slovak Republic
2003-08-25
Mathematical foundations of computer science 2003 : 28th International Symposium, MFCS 2003
Lecture Notes in Computer Science
Smoothed analysis combines elements over worst-case and
average case analysis. For an instance $x$, the smoothed complexity is the
average complexity of an instance obtained from $x$ by a perturbation. The
smoothed complexity of a problem is the worst smoothed complexity of any
instance. Spielman and Teng introduced this notion for
continuous problems. We apply the concept to combinatorial problems and study
the smoothed complexity of three classical discrete problems: quicksort,
left-to-right maxima counting, and shortest paths.
No
expertsonly
published
http://edoc.mpg.de/get.epl?fid=9181&did=202044&ver=0
C.
Banderier
Cyril
R.
Beier
Rene
K.
Mehlhorn
Kurt
B.
Rovan
Branislav
P.
Vojtáš
Peter
3-540-40671-9
C1256428004B93B8-09CF39E77E5072D5C1256E140059E6C7-Beier2003a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020532012-09-1987:931
Conference-Paper
Energy Optimal Routing in Radio Networks Using Geometric Data Structures
English
Springer
Berlin, Germany
2002
2003-08-26
366
376
Málaga, Spain
2002-07-08
Automata, Languages and Programming : 29th International Colloquium, ICALP 2002
Lecture Notes in Computer Science
No
expertsonly
published
notspecified
R.
Beier
Rene
P.
Sanders
Peter
N.
Sivadasan
Naveen
P.
Widmayer
Peter
F.
Triguero
Francisco
R.
Morales
Rafael
M.
Hennessy
Matthew
S.
Eidenbenz
Stephan
R.
Conejo
Ricardo
3-540-43884-5
C1256428004B93B8-9424B1926836A772C1256CBE00646164-Sanders2002h
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020542012-09-1987:931
Conference-Paper
Scheduling at Twilight the Easy Way
English
Springer
Berlin, Germany
2002
2003-09-05
166
178
Antibes, Juan-Les-Pins, France
2002-03-14
STACS 2002 : 19th Annual Symposium on Theoretical Aspects of Computer Science
Lecture Notes in Computer Science
We investigate particularly simple algorithms for optimizing the tradeoff
between load imbalance and assignment overheads in dynamic multiprocessor
scheduling scenarios, when the information that is available about the
processing time of a task before it is completed is vague.
We describe a simple and elegant generic algorithm that, in a very
general model, always comes surprisingly close to the theoretical optimum,
and the performance of which we can analyze exactly with respect to constant
factors. In contrast, we prove that algorithms that assign tasks
in equal-sized portions
perform far from optimal in general. In fact, we give evidence that the
performance of our generic scheme cannot be improved by any constant factor
without sacrificing the simplicity of the algorithm. We also give lower
bounds on the performance of the various decreasing-size heuristics that
have typically been used so far in concrete applications.
No
expertsonly
published
notspecified
H.
Bast
Hannah
A.
Ferreira
Afonso
H.
Alt
Helmut
3-540-43283-3
C1256428004B93B8-1F797C13238C3EF5C1256B110055EA3D-Bast2002a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020552012-09-1987:931
Article
Basic analytic combinatorics of directed lattice paths
English
2002
2003-09-08
37
80
Theoretical Computer Science
281
No
expertsonly
published
joureview
C.
Banderier
Cyril
P.
Flajolet
Philippe
0304-3975
C1256428004B93B8-FE220E9BBE204962C1256B3C00430AC5-Banderier2001
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020562012-09-1987:931
Conference-Paper
Multiple Robot Motion Planning = Parallel Processing + Geometry
English
Springer
Berlin, Germany
2002
2003-08-27
183
205
Schloss Dagstuhl, Wadern, Germany
2000-10-15
Sensor Based Intelligent Robots
Lecture Notes in Computer Science
We present two problems in multiple-robot motion planning that can be quite
naturally solved using techniques from the parallel processing community to
dictate how the robots interact with each other and techniques from
computational geometry to apply these techniques in the geometric environment
in which the robots operate. The first problem we consider is a load-balancing
problem in which a pool of work must be divided among a set of
processors in order to minimize the amount of time required to complete all
the work. We describe a simple polygon partitioning algorithm that allows
techniques from parallel processor scheduling to be applied in the
multiple-robot setting in order to achieve a good balance of the work.
The second problem is that of collision avoidance, where one must avoid that
two (or more) processors occupy the same resource at the same time.
For this problem, we describe a procedure for robot interaction that is
derived from procedures used to shared-memory computers along with a geometric
data structure that can efficiently determine when there are potential
robot collisions.
No
expertsonly
published
notspecified
S.
Hert
Susan
B.
Richards
Brad
H.
Christensen
Henrik
G.
Hager
Greg
C1256428004B93B8-093AEDC50CC59658C1256A9C002B0A47-hr-mrmpipppg-01
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020572012-09-1987:931
Conference-Paper
Randomized Pursuit-Evasion in Graphs
English
Springer
Berlin, Germany
2002
2003-08-26
901
912
Málaga, Spain
2002-07-08
Automata, Languages and Programming : 29th International Colloquium, ICALP 2002
Lecture Notes in Computer Science
{
We analyze a randomized pursuit-evasion game on graphs. This game is
played by two players, a {\em hunter} and a {\em rabbit}. Let
$G$ be any connected, undirected graph with $n$ nodes.
The game is played in rounds and in each round both the
hunter and the rabbit are located at a node of the graph. Between rounds
both the hunter and the rabbit can stay at the current node or move to
another node. The hunter is assumed to be {\em restricted} to the
graph $G$: in every round, the hunter can move using at most one edge.
For the rabbit we investigate two models: in one
model the rabbit is restricted to the same graph as the hunter, and in
the other model the rabbit is {\em unrestricted}, i.e., it can jump to
an arbitrary node in every round.
We say that the rabbit is {\em caught}\/ as soon as hunter and rabbit
are located at the same node in a round. The goal of the hunter is to
catch the rabbit in as few rounds as possible, whereas the rabbit aims
to maximize the number of rounds until it is caught. Given a
randomized hunter strategy for $G$, the {\em escape length} for that
strategy is the worst case expected number of rounds it takes the
hunter to catch the rabbit, where the worst case is with regards to
all (possibly randomized) rabbit strategies.
Our main result is a hunter strategy for general graphs
with an escape length of only $\O(n \log (\diam(G)))$ against
restricted as well as unrestricted rabbits.
This bound is close to optimal since $\Omega(n)$ is a trivial lower bound
on the escape length in both models.
Furthermore, we prove that our upper bound is optimal
up to constant factors against unrestricted rabbits.
}
No
expertsonly
published
notspecified
M.
Adler
Micah
H.
Räcke
Harald
N.
Sivadasan
Naveen
C.
Sohler
Christian
B.
Vöcking
Berthold
P.
Widmayer
Peter
F.
Triguero
Francisco
R.
Morales
Rafael
M.
Hennessy
Matthew
S.
Eidenbenz
Stephan
R.
Conejo
Ricardo
3-540-43864-5
C1256428004B93B8-07C33A9C6FA1B038C1256D13002D8771-NSBV+02
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020582012-09-1987:931
Article
Optimal prefix-free codes for unequal letter costs: Dynamic programming with the Monge property
English
2002
2003-08-20
277
303
Journal of Algorithms
42
No
expertsonly
published
joureview
P.G.
Bradford
Phillip Gnassi
M.J.
Golin
Mordecai J.
L.L.
Larmore
Lawrence L.
0196-6774
C1256428004B93B8-C1C8FFA6B7DC0159C1256D21002D612C-BradfordGolinLarmore2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020592012-09-1987:931
Conference-Paper
A Computational Basis for Conic Arcs and Boolean Operations on Conic Polygons
English
Springer
Berlin, Germany
2002
2003-08-27
174
186
Rome, Italy
2002-09-17
Algorithms - ESA 2002 : 10th Annual European Symposium
Lecture Notes in Computer Science
We give an exact geometry kernel for conic arcs, algorithms for exact
computation with low-degree algebraic numbers, and an algorithm for
computing the arrangement of conic arcs that immediately leads to
a realization of regularized boolean operations on conic polygons. A conic
polygon, or polygon for short, is anything that can be obtained from
linear or conic halfspaces (= the set of points where a linear or quadratic
function is non-negative) by regularized boolean operations. The algorithm and
its implementation are complete (they can handle all cases), exact (they give
the mathematically correct result), and efficient (they can handle inputs with
several hundred primitives).
No
expertsonly
published
notspecified
E.
Berberich
Eric
A.
Eigenwillig
Arno
M.
Hemmer
Michael
S.
Hert
Susan
K.
Mehlhorn
Kurt
E.
Schömer
Elmar
R.
Möhring
Rolf
R.
Raman
Rajeev
3-540-44180-8
C1256428004B93B8-A840A9EA6B064FFDC1256C4D004F2508-behhms-cbcabocp-2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020602012-09-1987:931
Conference-Paper
Translating a Planar Object to Maximize Point Containment
English
Springer
Berlin, Germany
2002
2003-09-08
42
53
Rome, Italy
2002-09-17
Algorithms - ESA 2002 : 10th Annual European Symposium
Lecture Notes in Computer Science
Let $C$ be a compact set in $\IR^2$ and let $S$ be a set
of $n$ points in $\IR^2$. We consider the problem of computing a
translate of $C$ that contains the maximum number, $\kappa^*$, of points
%denoted by $\kappa^*$,
of $S$.
It is known that this problem can be solved in a time that is
roughly quadratic in $n$.
We show how random-sampling and bucketing techniques
can be used to develop a near-linear-time Monte Carlo algorithm
that computes a placement of $C$ containing
at least $(1-\eps) \kappa^*$ points of $S$, for
given $\eps>0$, with high probability.
Finally, we present a deterministic algorithm that
solves the $\eps$-approximate version of the optimal-placement
problem for convex $m$-gons in $O(n^{1+\delta} + (n/\eps)\log m)$ time,
for arbitrary constant $\delta>0$.
%, for convex $m$-gons.
No
expertsonly
published
notspecified
P.
Agarwal
Pankaj
T.
Hagerup
Torben
R.
Ray
Rahul
M.
Sharir
Micha
M.
Smid
Michiel
E.
Welzl
Emo
R.
Möhring
Rolf
R.
Raman
Rajeev
0302-9743
C1256428004B93B8-DEDAEE38A05F3663C1256C850055D604-Rahul2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020612012-09-1987:931
Conference-Paper
Lower Bounds & Competitive Algorithms for Online Scheduling of Unit-Size Tasks to Related Machines
English
ACM
New York, USA
2002
2003-10-16
124
133
Montreal, Quebec, Canada
2002-05-19
Proceedings of the 34th ACM Symposium on Theory of Computing (STOC-02)
In this paper we study the problem of assigning unit-size tasks to
related machines when only limited online information is provided
to each task. This is a general framework whose special cases are
the classical multiple-choice games for the assignment of
unit-size tasks to identical machines. The latter case was the
subject of intensive research for the last decade. The problem is
intriguing in the sense that the natural extensions of the greedy
oblivious schedulers, which are known to achieve near-optimal
performance in the case of identical machines, are proved to
perform quite poorly in the case of the related machines.
In this work we present a rather surprising lower bound stating
that any oblivious scheduler that assigns an arbitrary number of
tasks to $n$ related machines would need $\Omega\left(\frac{\log
n}{\log\!\log n}\right)$ polls of machine loads per task, in order to
achieve a constant competitive ratio versus the optimum offline
assignment of the same input sequence to these machines. On the
other hand, we prove that the missing information for an oblivious
scheduler to perform almost optimally, is the amount of tasks to
be inserted into the system. In particular, we provide an
oblivious scheduler that only uses $\cal{O}(\log\!\log n)$ polls, along with
the additional information of the size of the input sequence, in
order to achieve a constant competitive ratio vs. the optimum
offline assignment. The philosophy of this scheduler is based on
an interesting exploitation of the {\sc slowfit} concept
([AAFPW97,BFN00,BCK97]; for a survey see
[BY98,Azar98,Sgall98]) for the assignment of the tasks to the
related machines despite the restrictions on the provided online
information, in combination with a layered induction argument for
bounding the tails of the number of tasks passing from slower to
faster machines. We finally use this oblivious scheduler as the
core of an adaptive scheduler that does not demand the knowledge
of the input sequence and yet achieves almost the same
performance.
No
expertsonly
published
notspecified
S.
Kontogiannis
Spyros
C1256428004B93B8-0E9201F9D0830BB9C1256B7B002CD33E-Kontogiannis2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
Permission to make digital or hard copies of part or all of
this work for personal or classroom use is granted without fee
provided that copies are not made or distributed for profit or
commercial advantage and that copies bear this notice and the
full citation on the first page. Copyrights for components of
this work owned by others than ACM must be honored. Abstracting
with credit is permitted. To copy otherwise, to republish, to
post on servers or to redistribute to lists, requires prior
specific permission and/or a fee.
oai:edoc.mpg.de:2020622012-09-1987:931
Conference-Paper
Computing the threshold for q-gram filters
English
Springer
Berlin, Germany
2002
2003-08-27
348
357
Turku, Finland
2002-07-03
Algorithm theory, SWAT 2002 : 8th Scandinavian Workshop on Algorithm Theory
Lecture Notes in Computer Science
A popular and much studied class of filters for approximate string
matching is based on finding common $q$-grams, substrings of length
$q$, between the pattern and the text. A variation of the basic idea uses
\emph{gapped} $q$-grams and has been recently shown to provide
significant improvements in practice. A major difficulty with gapped
$q$-gram filters is the computation of the so-called \emph{threshold}
which defines the filter criterium. We describe the first general
method for computing the threshold for $q$-gram filters. The method is
based on a carefully chosen precise statement of the problem which is
then transformed into a constrained shortest path problem.
In its generic form the method leaves certain parts open
but is applicable to a large variety of $q$-gram filters and may be
extensible even to other classes of filters. We also give a full
algorithm for a specific subclass. For this subclass, the algorithm
has been implemented and used succesfully in an experimental
comparison.
No
expertsonly
published
notspecified
J.
Kärkkäinen
Juha
M.
Penttonen
Martti
E.
Meineche Schmidt
Erik
3-540-43866-1
C1256428004B93B8-BDE5926620208DA2C1256CE5006C7B5E-Karkkainen2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020632012-09-1987:931
Article
Linear-Time Approximation Schemes for Scheduling Malleable Parallel Tasks
English
2002
2003-09-24
507
520
Algorithmica
32
No
expertsonly
published
joureview
K.
Jansen
Klaus
L.
Porkolab
Lorant
0178-4617
C1256428004B93B8-E394746B381F8BBAC1256DAB0049510E-JansenPorkolab2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020642012-09-1987:931
Conference-Paper
A Polyhedral Approach to Surface Reconstruction from Planar Contours.
English
Springer
Berlin, Germany
2002
2003-08-27
258
272
Cambridge, USA
2002-05-27
Proceedings of the 9th International Conference on Integer Programming and Combinatorial Optimization
Lecture Notes in Computer Science
We investigate the problem of reconstruction a surface given its contours on
parallel slices. We present a branch-and-cut algorithm which computes the
surface with the minimal area. This surface is assumed to be the best
reconstruction since a long time. Nevertheless there were no algorithms to
compute this surface. Our experiments show that the running time of our
algorithm is very reasonable and that the computed surfaces are highly similar
to the original surfaces.
No
expertsonly
published
notspecified
E.
Althaus
Ernst
C.
Fink
Christian
W.J.
Cook
William J.
A.S.
Schulz
Andreas S.
3-540-43676-6
C1256428004B93B8-01485E5AAA7765F5C1256C9300542412-Althaus2002a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020652012-09-1987:931
Conference-Paper
Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics
English
Oxford University Press
Oxford, UK
2002
2003-08-28
S4
S16
Saarbrücken
2002-10-06
Proceedings of the European Conference on Computational Biology (ECCB 2002)
Bioinformatics
Multiple sequence alignment is one of the dominant problems in computational
molecular biology. Numerous scoring functions and methods have been proposed,
most of which result in NP-hard problems. In this paper we propose for the
first time a general formulation for multiple alignment with arbitrary
gap-costs based on an integer linear program (ILP). In addition we describe a
branch-and-cut algorithm to effectively solve the ILP to optimality. We
evaluate the performances of our approach in terms of running time and quality
of the alignments using the BAliBase database of reference alignments. The
results show that our implementation ranks amongst the best programs developed
so far.
No
expertsonly
published
notspecified
E.
Althaus
Ernst
A.
Caprara
Alberto
H.-P.
Lenhof
Hans-Peter
K.
Reinert
Knut
T.
Lengauer
Thomas
C1256428004B93B8-14DF56BBB5470A4DC1256C930054F370-Althaus2002b
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020662012-09-1987:931
Conference-Paper
SCIL - Symbolic Constraints in Integer Linear Programming.
English
Springer
Berlin, Germany
2002
2003-08-27
75
87
Rom, Italy
2002-09-17
Algorithms - ESA 2002 : 10th Annual European Symposium
Lecture Notes in Computer Science
We describe a new software system SCIL that introduces symbolic constraints
into branch-and-cut-and-price algorithms for integer linear programs. Symbolic
constraints are known from constraint programming and contribute significantly
to the expressive power, ease of use, and efficiency of constraint programming
systems.
No
expertsonly
published
notspecified
E.
Althaus
Ernst
A.
Bockmayr
Alexander
M.
Elf
Matthias
T.
Kasper
Thomas
M.
Jünger
Michael
K.
Mehlhorn
Kurt
R.
Möhring
Rolf
R.
Raman
Rajeev
3-540-44180-8
C1256428004B93B8-5EA058E323C086ACC1256C9300519510-Althaus2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020672012-09-1987:931
Article
Exploring unkown environments with obstacles
English
2002
2003-08-26
123
143
Algorithmica
32
No
expertsonly
published
joureview
S.
Albers
Susanne
K.
Kursawe
Klaus
S.
Schuierer
Sven
0178-4617
C1256428004B93B8-BCE46206EE77372400256D20004BC704-Kursawe2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020682012-09-1987:931
Article
On the competitive theory and practice of online list accessing algorithms
English
2002
2003-08-29
201
246
Algorithmica
32
No
expertsonly
published
joureview
R.
Bachrach
Ran
R.
El-Yaniv
Ran
M.
Reinstädtler
Martin
0178-4617
C1256428004B93B8-40A8A5EA48179CD1C1256D210029A112-BachrachEl-YanivReinstädtler2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020692012-09-1987:931
Article
Approximation algorithms for maximum two-dimensional pattern matching
English
2001
2003-08-29
51
62
Theoretical Computer Science
255
No
expertsonly
published
joureview
S.R.
Arikati
Srinivasa Rao
A.
Dessmark
Anders
A.
Lingas
Andrzej
M.V.
Marathe
Madhav V.
0304-3975
C1256428004B93B8-6C1795FE8553898A00256D2000520DF6-ArikatiDessmarketal2001
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020702012-09-1987:931
Conference-Paper
On Radiocoloring Hierarchically Specified Planar Graphs: PSPACE-Completeness and Approximations
English
Springer
Berlin, Germany
2002
2003-08-28
81
92
Warsaw, Poland
2002-08-26
Mathematical Foundations of Computer Science 2002 : 27th International Symposium, MFCS 2002
Lecture Notes in Computer Science
Hierarchical specifications of graphs have been widely used in many important
applications, such as VLSI design, parallel programming and software
engineering. A well known hierarchical specification model, considered in this
work, is that of Lengauer [9, 10] referred to as L-specifications. In this
paper we discuss a restriction on the L-specifications resulting to graphs
which we call Well-Separated (WS). This class is characterized by a polynomial
time (to the size of the specification of the graph) testable combinatorial
property.
In this work we study the Radiocoloring Problem (RCP) on WS L-specified
hierarchical planar graphs. The optimization version of RCP studied here,
consists in assigning colors to the vertices of a graph, such that any two
vertices of distance at most two get different colors. The objective here is to
minimize the number of colors used. This problem is equivalent to the problem
of vertex coloring the square of a graph $G$, $G^2$, where $G^2$ has the same
vertex set as $G$ and there is an edge between any two vertices of $G^2$ if
their distance in $G$ is at most 2.
We first show that RCP is PSPACE-complete for WS L-specified hierarchical
planar graphs. Second, we present a polynomial time 3-approximation algorithm
as well as a more efficient 4-approximation algorithm for RCP on graphs of this
class.
We note that, the best currently known approximation ratio for the RCP on
ordinary (non-hierarchical) planar graphs of general degree is 2 ([6, 1]). Note
also that the only known results on any kind of coloring problems have been
shown for another special kind of hierarchical graphs (unit disk graphs)
achieving a 6-approximation solution [13].
No
expertsonly
published
notspecified
M.
Andreou
Maria
D.
Fotakis
Dimitris
S.
Nikoletseas
Sotiris
V.
Papadopoulou
Vicky
P.G.
Spirakis
Paul G.
K.
Diks
Krzysztof
W.
Rytter
Wojciech
3-540-44040-2
C1256428004B93B8-C91B00E18E06B3F7C1256C7800554212-AFNPS02
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020712012-09-1987:931
Article
A combinatorial approach to protein docking with flexible side chains
English
2002
2003-09-29
597
612
Journal of Computational Biology
9
No
expertsonly
published
joureview
E.
Althaus
Ernst
O.
Kohlbacher
Oliver
H.-P.
Lenhof
Hans-Peter
P.
Müller
Peter
1066-5277
C1256428004B93B8-0F6AF25C607ECEDEC1256D0A004BEDA9-ALKM2001
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020722012-09-1987:931
Article
An O(n log n) algorithm for the maximum agreement subtree problem for binary trees
English
2000
2003-05-09
1385
1404
SIAM Journal on Computing
30
Automatic journal name synchronization
No
expertsonly
published
joureview
R.
Cole
Richard
M.
Farach-Colton
Martin
R.
Hariharan
Ramesh
T.
Przytycka
Teresa
M.
Thorup
Mikkel
0097-5397
C1256428004B93B8-7FB9DBD953ABAAFDC1256D2100333ABB-ColeFarachetal2000
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020732012-09-1987:931
Conference-Paper
One-Gapped q-Gram Filters for Levenshtein Distance
English
Springer
Berlin, Germany
2002
2003-09-08
225
234
Fukuoka, Japan
2002-07-03
Combinatorial Pattern Matching : 13th Annual Symposium, CPM 2002
Lecture Notes in Computer Science
We have recently shown that $q$-gram filters based on gapped $q$-grams
instead of the usual contiguous $q$-grams can provide orders of
magnitude faster and/or more efficient filtering for the Hamming
distance. In this paper, we extend the results for the Levenshtein
distance, which is more problematic for gapped $q$-grams because an
insertion or deletion in a gap affects a $q$-gram while a
replacement does not. To keep this effect under control, we
concentrate on gapped $q$-grams with just one gap. We demostrate with
experiments that the resulting filters provide a significant
improvement over the contiguous $q$-gram filters. We also develop new
techniques for dealing with complex $q$-gram filters.
No
expertsonly
published
notspecified
S.
Burkhardt
Stefan
J.
Kärkkäinen
Juha
A.
Apostolico
Alberto
M.
Takeda
Masayuki
3-540-43862-9
C1256428004B93B8-E631B996E8179208C1256CA2005D83B6-Burkhardt2002
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020742012-09-1987:931
Article
Generating Functions for Generating Trees
English
2002
2003-09-08
29
55
Discrete Mathematics
246
No
expertsonly
published
joureview
C.
Banderier
Cyril
M.
Bousquet-Mélou
Mireille
A.
Denise
Alain
P.
Flajolet
Philippe
D.
Gardy
Danièle
D.
Gouyou-Beauchamps
Dominique
0012-365X
C1256428004B93B8-42D1A2011A96D4D3C1256B3C0043FAD6-Banderier2001_3
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020752012-09-1987:931
InBook
Algorithm Engineering for Parallel Computation
English
Springer
Berlin, Germany
2002
2003-09-08
1
23
2547
Experimental Algorithmics
Fleischer, Rudolf; Moret, Bernard;Meineche Schmidt, Erik
The emerging discipline of algorithm engineering has primarily focussed
on transforming pencil-and-paper sequential algorithms into
robust, efficient, well tested, and easily used implementations. As
parallel computing becomes ubiquitous, we need to extend algorithm
engineering techniques to parallel computation. Such an extension
adds significant complications. After a short review of algorithm
engineering achievements for sequential computing, we review the various
complications caused by parallel computing, present some examples of
successful efforts, and give a personal view of possible future research.
No
expertsonly
published
notspecified
D.
Bader
David
B.
Moret
Bernard
P.
Sanders
Peter
R.
Fleischer
Rudolf
B.
Moret
Bernard
E.
Meineche Schmidt
Erik
3-540-00346-0
C1256428004B93B8-9EE2FCF662ED1B38C1256CBE005C29DD-Sanders2002a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020762012-09-1987:931
Conference-Paper
Efficient Collision Detection for Curved Solid Objects
English
ACM
New York, USA
2002
2003-08-27
321
328
Saarbrücken, Germany
2002-06-17
Proceedings of the Seventh {ACM} Symposium on Solid Modeling and Applications
The design-for-assembly technique requires realistic physically based
simulation algorithms and in particular efficient geometric collision
detection routines. Instead of approximating mechanical parts by large
polygonal models, we work with the much smaller original CAD-data directly,
thus avoiding precision and tolerance problems.
We present a generic algorithm, which can decide whether two solids intersect
or not. We identify classes of objects for which this algorithm can be
efficiently specialized, and describe in detail how this specialization is
done. These classes are objects that are bounded by quadric surface patches and
conic arcs, objects that are bounded by natural quadric patches, torus patches,
line segments and circular arcs, and objects that are
bounded by quadric surface patches, segments of quadric intersection curves and
segments of cubic spline curves. We show that all necessary geometric
predicates can be evaluated by finding the roots of univariate polynomials of
degree at most $4$ for the first two classes, and at most $8$ for the third
class.
In order to speed up the intersection tests we
use bounding volume hierarchies. With the help of numerical
optimization techniques we succeed in calculating smallest enclosing spheres
and bounding boxes for a given set of surface patches fulfilling the properties
mentioned above.
No
expertsonly
published
notspecified
E.
Schömer
Elmar
J.
Reichel
Joachim
T.
Warken
Thomas
C.
Lennerz
Christian
K.
Lee
Kunwoo
N.M.
Patrikalakis
Nicholas M.
1-58113-506-8
C1256428004B93B8-1B96BB733FE4FB34C1256C8D0055A3D9-SRWLSM02
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020772012-09-1987:931
Article
Feasible models of computation: Three-dimensionality and energy consumption
English
2002
2003-09-08
233
248
Fundamenta Informaticae
52
No
expertsonly
published
joureview
P.
Sanders
Peter
R.
Vollmar
R.
T.
Worsch
T.
0169-2968
C1256428004B93B8-3DF232068F5630E9C1256CBE005FC0A2-Sanders2002e
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020782012-09-1987:931
Conference-Paper
Selfish Traffic Allocation for Server Farms
English
ACM
New York, USA
2002
2003-08-28
287
296
Montreal, Canada
2002-05-19
Proceedings of the 34th ACM Symposium on Theory of Computing (STOC-02)
No
expertsonly
published
notspecified
A.
Czumaj
Artur
P.
Krysta
Piotr
B.
Vöcking
Berthold
C1256428004B93B8-A1C495AACF4668DDC1256C7100468A9B-Krysta2002b
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020792012-09-1987:931
Conference-Paper
Approximability of Dense and Sparse Instances of Minimum 2-Connectivity, TSP and Path Problems
English
ACM
New York, USA
2002
2003-08-27
74
83
San Francisco, CA, USA
2002-01-06
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-02)
No
expertsonly
published
notspecified
B.
Csaba
Bela
P.
Krysta
Piotr
M.
Karpinski
Marek
C1256428004B93B8-08AE5D9C120A99B2C1256C6F00588047-Krysta2002a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
oai:edoc.mpg.de:2020802012-09-1987:931
Article
Surface Topography Quantification by Integral and Feature-related Parameters
English
2002
2003-09-08
621
627
Materialwissenschaft und Werkstofftechnik
33
Using topographical images obtained by confocal laser scanning microscopy, the
topography of brittle fracture
surfaces and wire-eroded surfaces was quantified. The global topometry values
show a significant dependency
on the imaging conditions and on the computing algorithm. An algorithm was
developed and implemented for the
automatic detection and measuring of feature-related parameters in
topographies, which uses methods of
computational geometry. The software was tested using brittle fracture surfaces
of steel.
No
expertsonly
published
joureview
U.
Wendt
Ulrich
K.
Lange
Katharina
M.
Smid
Michiel
R.
Ray
Rahul
K.-D.
Tönnies
Klaus-Dietz
1521-4052
C1256428004B93B8-5629367C3D5C509EC1256C8600486516-Rahul2002a
MPI für Informatik
Algorithms and Complexity Group
2012-09-19 10:13:15.652552
ResultSet_5ZGNnofJJKB_range_100-199