---
_id: '24338'
author:
- first_name: Matthias
full_name: Grünewald, Matthias
last_name: Grünewald
- first_name: Tamás
full_name: Lukovszki, Tamás
last_name: Lukovszki
- first_name: Christian
full_name: Schindelhauer, Christian
last_name: Schindelhauer
- first_name: Klaus
full_name: Volbert, Klaus
last_name: Volbert
citation:
ama: 'Grünewald M, Lukovszki T, Schindelhauer C, Volbert K. Distributed Maintenance
of Resource Efficient Wireless Network Topologies. In: Proceedings of the 8th
International Euro-Par Conference. ; 2002. doi:10.1007/3-540-45706-2_134'
apa: Grünewald, M., Lukovszki, T., Schindelhauer, C., & Volbert, K. (2002).
Distributed Maintenance of Resource Efficient Wireless Network Topologies. Proceedings
of the 8th International Euro-Par Conference. https://doi.org/10.1007/3-540-45706-2_134
bibtex: '@inproceedings{Grünewald_Lukovszki_Schindelhauer_Volbert_2002, place={Paderborn,
Germany}, title={Distributed Maintenance of Resource Efficient Wireless Network
Topologies}, DOI={10.1007/3-540-45706-2_134},
booktitle={Proceedings of the 8th International Euro-Par Conference}, author={Grünewald,
Matthias and Lukovszki, Tamás and Schindelhauer, Christian and Volbert, Klaus},
year={2002} }'
chicago: Grünewald, Matthias, Tamás Lukovszki, Christian Schindelhauer, and Klaus
Volbert. “Distributed Maintenance of Resource Efficient Wireless Network Topologies.”
In Proceedings of the 8th International Euro-Par Conference. Paderborn,
Germany, 2002. https://doi.org/10.1007/3-540-45706-2_134.
ieee: 'M. Grünewald, T. Lukovszki, C. Schindelhauer, and K. Volbert, “Distributed
Maintenance of Resource Efficient Wireless Network Topologies,” 2002, doi: 10.1007/3-540-45706-2_134.'
mla: Grünewald, Matthias, et al. “Distributed Maintenance of Resource Efficient
Wireless Network Topologies.” Proceedings of the 8th International Euro-Par
Conference, 2002, doi:10.1007/3-540-45706-2_134.
short: 'M. Grünewald, T. Lukovszki, C. Schindelhauer, K. Volbert, in: Proceedings
of the 8th International Euro-Par Conference, Paderborn, Germany, 2002.'
date_created: 2021-09-14T09:15:57Z
date_updated: 2022-01-06T06:56:18Z
department:
- _id: '63'
doi: 10.1007/3-540-45706-2_134
language:
- iso: eng
place: Paderborn, Germany
publication: Proceedings of the 8th International Euro-Par Conference
publication_identifier:
issn:
- 0302-9743
publication_status: published
status: public
title: Distributed Maintenance of Resource Efficient Wireless Network Topologies
type: conference
user_id: '15415'
year: '2002'
...
---
_id: '18566'
abstract:
- lang: eng
text: "We analyze a randomized pursuit-evasion game on graphs. This game is played
by two players, a hunter and a 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 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 unrestricted, i.e., it can jump to an arbitrary node in every round.\r\n\r\nWe
say that the rabbit is 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 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\r\n(n log (diam(G))) against restricted as well as
unrestricted rabbits. This bound is close to optimal since Ω(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."
author:
- first_name: Micah
full_name: Adler, Micah
last_name: Adler
- first_name: Harald
full_name: Räcke, Harald
last_name: Räcke
- first_name: Naveen
full_name: Sivadasan, Naveen
last_name: Sivadasan
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
- first_name: Berthold
full_name: Vöcking, Berthold
last_name: Vöcking
citation:
ama: 'Adler M, Räcke H, Sivadasan N, Sohler C, Vöcking B. Randomized Pursuit-Evasion
in Graphs. In: Proceedings of the 29th International Colloquium on Automata,
Languages and Programming. Berlin, Heidelberg; 2002. doi:10.1007/3-540-45465-9_77'
apa: Adler, M., Räcke, H., Sivadasan, N., Sohler, C., & Vöcking, B. (2002).
Randomized Pursuit-Evasion in Graphs. In Proceedings of the 29th International
Colloquium on Automata, Languages and Programming. Berlin, Heidelberg. https://doi.org/10.1007/3-540-45465-9_77
bibtex: '@inproceedings{Adler_Räcke_Sivadasan_Sohler_Vöcking_2002, place={Berlin,
Heidelberg}, title={Randomized Pursuit-Evasion in Graphs}, DOI={10.1007/3-540-45465-9_77},
booktitle={Proceedings of the 29th International Colloquium on Automata, Languages
and Programming}, author={Adler, Micah and Räcke, Harald and Sivadasan, Naveen
and Sohler, Christian and Vöcking, Berthold}, year={2002} }'
chicago: Adler, Micah, Harald Räcke, Naveen Sivadasan, Christian Sohler, and Berthold
Vöcking. “Randomized Pursuit-Evasion in Graphs.” In Proceedings of the 29th
International Colloquium on Automata, Languages and Programming. Berlin, Heidelberg,
2002. https://doi.org/10.1007/3-540-45465-9_77.
ieee: M. Adler, H. Räcke, N. Sivadasan, C. Sohler, and B. Vöcking, “Randomized Pursuit-Evasion
in Graphs,” in Proceedings of the 29th International Colloquium on Automata,
Languages and Programming, 2002.
mla: Adler, Micah, et al. “Randomized Pursuit-Evasion in Graphs.” Proceedings
of the 29th International Colloquium on Automata, Languages and Programming,
2002, doi:10.1007/3-540-45465-9_77.
short: 'M. Adler, H. Räcke, N. Sivadasan, C. Sohler, B. Vöcking, in: Proceedings
of the 29th International Colloquium on Automata, Languages and Programming, Berlin,
Heidelberg, 2002.'
date_created: 2020-08-28T12:04:12Z
date_updated: 2022-01-06T06:53:40Z
department:
- _id: '63'
doi: 10.1007/3-540-45465-9_77
language:
- iso: eng
place: Berlin, Heidelberg
publication: Proceedings of the 29th International Colloquium on Automata, Languages
and Programming
publication_identifier:
isbn:
- '9783540438649'
- '9783540454656'
issn:
- 0302-9743
publication_status: published
status: public
title: Randomized Pursuit-Evasion in Graphs
type: conference
user_id: '15415'
year: '2002'
...
---
_id: '16723'
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Mohan
full_name: Kumar, Mohan
last_name: Kumar
- first_name: Sotiris
full_name: Nikoletseas, Sotiris
last_name: Nikoletseas
- first_name: Paul
full_name: Spirakis, Paul
last_name: Spirakis
citation:
ama: 'Meyer auf der Heide F, Kumar M, Nikoletseas S, Spirakis P. Mobile Computing,
Mobile Networks. In: Euro-Par 2002 Parallel Processing. Lecture Notes in
Computer Science, vol 2400. Berlin, Heidelberg; 2002. doi:10.1007/3-540-45706-2_133'
apa: Meyer auf der Heide, F., Kumar, M., Nikoletseas, S., & Spirakis, P. (2002).
Mobile Computing, Mobile Networks. In Euro-Par 2002 Parallel Processing
(Lecture Notes in Computer Science, vol 2400). Berlin, Heidelberg. https://doi.org/10.1007/3-540-45706-2_133
bibtex: '@inbook{Meyer auf der Heide_Kumar_Nikoletseas_Spirakis_2002, place={Berlin,
Heidelberg}, edition={Lecture Notes in Computer Science, vol 2400}, title={Mobile
Computing, Mobile Networks}, DOI={10.1007/3-540-45706-2_133},
booktitle={Euro-Par 2002 Parallel Processing}, author={Meyer auf der Heide, Friedhelm
and Kumar, Mohan and Nikoletseas, Sotiris and Spirakis, Paul}, year={2002} }'
chicago: Meyer auf der Heide, Friedhelm, Mohan Kumar, Sotiris Nikoletseas, and Paul
Spirakis. “Mobile Computing, Mobile Networks.” In Euro-Par 2002 Parallel Processing,
Lecture Notes in Computer Science, vol 2400. Berlin, Heidelberg, 2002. https://doi.org/10.1007/3-540-45706-2_133.
ieee: F. Meyer auf der Heide, M. Kumar, S. Nikoletseas, and P. Spirakis, “Mobile
Computing, Mobile Networks,” in Euro-Par 2002 Parallel Processing, Lecture
Notes in Computer Science, vol 2400., Berlin, Heidelberg, 2002.
mla: Meyer auf der Heide, Friedhelm, et al. “Mobile Computing, Mobile Networks.”
Euro-Par 2002 Parallel Processing, Lecture Notes in Computer Science, vol
2400, 2002, doi:10.1007/3-540-45706-2_133.
short: 'F. Meyer auf der Heide, M. Kumar, S. Nikoletseas, P. Spirakis, in: Euro-Par
2002 Parallel Processing, Lecture Notes in Computer Science, vol 2400, Berlin,
Heidelberg, 2002.'
date_created: 2020-04-17T11:40:33Z
date_updated: 2022-01-06T06:52:55Z
department:
- _id: '63'
doi: 10.1007/3-540-45706-2_133
edition: Lecture Notes in Computer Science, vol 2400
language:
- iso: eng
place: Berlin, Heidelberg
publication: Euro-Par 2002 Parallel Processing
publication_identifier:
isbn:
- '9783540440499'
- '9783540457060'
issn:
- 0302-9743
publication_status: published
status: public
title: Mobile Computing, Mobile Networks
type: book_chapter
user_id: '15415'
year: '2002'
...
---
_id: '18749'
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
citation:
ama: Czumaj A, Sohler C. Testing Hypergraph Coloring. Proceedings of the 28th
International Colloquium on Automata, Languages and Programming (ICALP). 2001:493-505.
doi:10.1007/3-540-48224-5_41
apa: Czumaj, A., & Sohler, C. (2001). Testing Hypergraph Coloring. Proceedings
of the 28th International Colloquium on Automata, Languages and Programming (ICALP),
493–505. https://doi.org/10.1007/3-540-48224-5_41
bibtex: '@article{Czumaj_Sohler_2001, title={Testing Hypergraph Coloring}, DOI={10.1007/3-540-48224-5_41},
journal={Proceedings of the 28th International Colloquium on Automata, Languages
and Programming (ICALP)}, author={Czumaj, Artur and Sohler, Christian}, year={2001},
pages={493–505} }'
chicago: Czumaj, Artur, and Christian Sohler. “Testing Hypergraph Coloring.” Proceedings
of the 28th International Colloquium on Automata, Languages and Programming (ICALP),
2001, 493–505. https://doi.org/10.1007/3-540-48224-5_41.
ieee: A. Czumaj and C. Sohler, “Testing Hypergraph Coloring,” Proceedings of
the 28th International Colloquium on Automata, Languages and Programming (ICALP),
pp. 493–505, 2001.
mla: Czumaj, Artur, and Christian Sohler. “Testing Hypergraph Coloring.” Proceedings
of the 28th International Colloquium on Automata, Languages and Programming (ICALP),
2001, pp. 493–505, doi:10.1007/3-540-48224-5_41.
short: A. Czumaj, C. Sohler, Proceedings of the 28th International Colloquium on
Automata, Languages and Programming (ICALP) (2001) 493–505.
date_created: 2020-09-01T10:48:38Z
date_updated: 2022-01-06T06:53:51Z
department:
- _id: '63'
doi: 10.1007/3-540-48224-5_41
language:
- iso: eng
page: 493-505
publication: Proceedings of the 28th International Colloquium on Automata, Languages
and Programming (ICALP)
publication_identifier:
isbn:
- '9783540422877'
- '9783540482246'
issn:
- 0302-9743
publication_status: published
status: public
title: Testing Hypergraph Coloring
type: journal_article
user_id: '15415'
year: '2001'
...
---
_id: '18964'
author:
- first_name: Tamás
full_name: Lukovszki, Tamás
last_name: Lukovszki
- first_name: Anil
full_name: Maheshwari, Anil
last_name: Maheshwari
- first_name: Norbert
full_name: Zeh, Norbert
last_name: Zeh
citation:
ama: 'Lukovszki T, Maheshwari A, Zeh N. I/O-Efficient Batched Range Counting and
Its Applications to Proximity Problems. In: Proceedings of the 21st Annual
Conference on Foundations of Software Technology and Theoretical Computer Science
(FSTTCS 2001), LNCS. ; 2001. doi:10.1007/3-540-45294-x_21'
apa: Lukovszki, T., Maheshwari, A., & Zeh, N. (2001). I/O-Efficient Batched
Range Counting and Its Applications to Proximity Problems. In Proceedings of
the 21st Annual Conference on Foundations of Software Technology and Theoretical
Computer Science (FSTTCS 2001), LNCS. https://doi.org/10.1007/3-540-45294-x_21
bibtex: '@inproceedings{Lukovszki_Maheshwari_Zeh_2001, title={I/O-Efficient Batched
Range Counting and Its Applications to Proximity Problems}, DOI={10.1007/3-540-45294-x_21},
booktitle={Proceedings of the 21st Annual Conference on Foundations of Software
Technology and Theoretical Computer Science (FSTTCS 2001), LNCS}, author={Lukovszki,
Tamás and Maheshwari, Anil and Zeh, Norbert}, year={2001} }'
chicago: Lukovszki, Tamás, Anil Maheshwari, and Norbert Zeh. “I/O-Efficient Batched
Range Counting and Its Applications to Proximity Problems.” In Proceedings
of the 21st Annual Conference on Foundations of Software Technology and Theoretical
Computer Science (FSTTCS 2001), LNCS, 2001. https://doi.org/10.1007/3-540-45294-x_21.
ieee: T. Lukovszki, A. Maheshwari, and N. Zeh, “I/O-Efficient Batched Range Counting
and Its Applications to Proximity Problems,” in Proceedings of the 21st Annual
Conference on Foundations of Software Technology and Theoretical Computer Science
(FSTTCS 2001), LNCS, 2001.
mla: Lukovszki, Tamás, et al. “I/O-Efficient Batched Range Counting and Its Applications
to Proximity Problems.” Proceedings of the 21st Annual Conference on Foundations
of Software Technology and Theoretical Computer Science (FSTTCS 2001), LNCS,
2001, doi:10.1007/3-540-45294-x_21.
short: 'T. Lukovszki, A. Maheshwari, N. Zeh, in: Proceedings of the 21st Annual
Conference on Foundations of Software Technology and Theoretical Computer Science
(FSTTCS 2001), LNCS, 2001.'
date_created: 2020-09-03T13:26:01Z
date_updated: 2022-01-06T06:53:55Z
department:
- _id: '63'
doi: 10.1007/3-540-45294-x_21
language:
- iso: eng
publication: Proceedings of the 21st Annual Conference on Foundations of Software
Technology and Theoretical Computer Science (FSTTCS 2001), LNCS
publication_identifier:
isbn:
- '9783540430025'
- '9783540452942'
issn:
- 0302-9743
publication_status: published
status: public
title: I/O-Efficient Batched Range Counting and Its Applications to Proximity Problems
type: conference
user_id: '15415'
year: '2001'
...
---
_id: '18152'
abstract:
- lang: eng
text: Computing the spectral decomposition of a normal matrix is among the most
frequent tasks to numerical mathematics. A vast range of methods are employed
to do so, but all of them suffer from instabilities when applied to degenerate
matrices, i.e., those having multiple eigenvalues. We investigate the spectral
representation's effectivity properties on the sound formal basis of computable
analysis. It turns out that in general the eigenvectors cannot be computed from
a given matrix. If however the size of the matrix' spectrum (=number of different
eigenvalues) is known in advance, it can be diagonalized effectively. Thus, in
principle the spectral decomposition can be computed under remarkably weak non-degeneracy
conditions.
author:
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
- first_name: Vasco
full_name: Brattka, Vasco
last_name: Brattka
citation:
ama: 'Ziegler M, Brattka V. A Computable Spectral Theorem. In: Proceedings of
the 4th Workshop on Computability and Complexity in Analysis (CCA’2000). Vol
2064. Berlin, Heidelberg; 2001:378-388. doi:10.1007/3-540-45335-0_23'
apa: Ziegler, M., & Brattka, V. (2001). A Computable Spectral Theorem. In Proceedings
of the 4th Workshop on Computability and Complexity in Analysis (CCA’2000)
(Vol. 2064, pp. 378–388). Berlin, Heidelberg. https://doi.org/10.1007/3-540-45335-0_23
bibtex: '@inproceedings{Ziegler_Brattka_2001, place={Berlin, Heidelberg}, title={A
Computable Spectral Theorem}, volume={2064}, DOI={10.1007/3-540-45335-0_23},
booktitle={Proceedings of the 4th Workshop on Computability and Complexity in
Analysis (CCA’2000)}, author={Ziegler, Martin and Brattka, Vasco}, year={2001},
pages={378–388} }'
chicago: Ziegler, Martin, and Vasco Brattka. “A Computable Spectral Theorem.” In
Proceedings of the 4th Workshop on Computability and Complexity in Analysis
(CCA’2000), 2064:378–88. Berlin, Heidelberg, 2001. https://doi.org/10.1007/3-540-45335-0_23.
ieee: M. Ziegler and V. Brattka, “A Computable Spectral Theorem,” in Proceedings
of the 4th Workshop on Computability and Complexity in Analysis (CCA’2000),
2001, vol. 2064, pp. 378–388.
mla: Ziegler, Martin, and Vasco Brattka. “A Computable Spectral Theorem.” Proceedings
of the 4th Workshop on Computability and Complexity in Analysis (CCA’2000),
vol. 2064, 2001, pp. 378–88, doi:10.1007/3-540-45335-0_23.
short: 'M. Ziegler, V. Brattka, in: Proceedings of the 4th Workshop on Computability
and Complexity in Analysis (CCA’2000), Berlin, Heidelberg, 2001, pp. 378–388.'
date_created: 2020-08-24T10:14:06Z
date_updated: 2022-01-06T06:53:26Z
department:
- _id: '63'
doi: 10.1007/3-540-45335-0_23
intvolume: ' 2064'
language:
- iso: eng
page: 378-388
place: Berlin, Heidelberg
publication: Proceedings of the 4th Workshop on Computability and Complexity in Analysis
(CCA'2000)
publication_identifier:
isbn:
- '9783540421979'
- '9783540453352'
issn:
- 0302-9743
publication_status: published
status: public
title: A Computable Spectral Theorem
type: conference
user_id: '15415'
volume: 2064
year: '2001'
...
---
_id: '16493'
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
citation:
ama: 'Meyer auf der Heide F. Data Management in Networks. In: Graph-Theoretic
Concepts in Computer Science. Vol 2204. Lecture Notes in Computer Science.
Berlin, Heidelberg; 2001. doi:10.1007/3-540-45477-2_2'
apa: Meyer auf der Heide, F. (2001). Data Management in Networks. In Graph-Theoretic
Concepts in Computer Science (Vol. 2204). Berlin, Heidelberg. https://doi.org/10.1007/3-540-45477-2_2
bibtex: '@inbook{Meyer auf der Heide_2001, place={Berlin, Heidelberg}, series={
Lecture Notes in Computer Science}, title={Data Management in Networks}, volume={2204},
DOI={10.1007/3-540-45477-2_2},
booktitle={Graph-Theoretic Concepts in Computer Science}, author={Meyer auf der
Heide, Friedhelm}, year={2001}, collection={ Lecture Notes in Computer Science}
}'
chicago: Meyer auf der Heide, Friedhelm. “Data Management in Networks.” In Graph-Theoretic
Concepts in Computer Science, Vol. 2204. Lecture Notes in Computer Science.
Berlin, Heidelberg, 2001. https://doi.org/10.1007/3-540-45477-2_2.
ieee: F. Meyer auf der Heide, “Data Management in Networks,” in Graph-Theoretic
Concepts in Computer Science, vol. 2204, Berlin, Heidelberg, 2001.
mla: Meyer auf der Heide, Friedhelm. “Data Management in Networks.” Graph-Theoretic
Concepts in Computer Science, vol. 2204, 2001, doi:10.1007/3-540-45477-2_2.
short: 'F. Meyer auf der Heide, in: Graph-Theoretic Concepts in Computer Science,
Berlin, Heidelberg, 2001.'
date_created: 2020-04-09T10:40:48Z
date_updated: 2022-01-06T06:52:51Z
department:
- _id: '63'
doi: 10.1007/3-540-45477-2_2
intvolume: ' 2204'
language:
- iso: eng
place: Berlin, Heidelberg
publication: Graph-Theoretic Concepts in Computer Science
publication_identifier:
isbn:
- '9783540427070'
- '9783540454779'
issn:
- 0302-9743
publication_status: published
series_title: ' Lecture Notes in Computer Science'
status: public
title: Data Management in Networks
type: book_chapter
user_id: '15415'
volume: 2204
year: '2001'
...
---
_id: '16494'
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Rolf
full_name: Wanka, Rolf
last_name: Wanka
citation:
ama: 'Meyer auf der Heide F, Wanka R. Parallel Bridging Models and Their Impact
on Algorithm Design. In: Computational Science - ICCS 2001. Berlin, Heidelberg;
2001. doi:10.1007/3-540-45718-6_68'
apa: Meyer auf der Heide, F., & Wanka, R. (2001). Parallel Bridging Models and
Their Impact on Algorithm Design. In Computational Science - ICCS 2001.
Berlin, Heidelberg. https://doi.org/10.1007/3-540-45718-6_68
bibtex: '@inbook{Meyer auf der Heide_Wanka_2001, place={Berlin, Heidelberg}, title={Parallel
Bridging Models and Their Impact on Algorithm Design}, DOI={10.1007/3-540-45718-6_68},
booktitle={Computational Science - ICCS 2001}, author={Meyer auf der Heide, Friedhelm
and Wanka, Rolf}, year={2001} }'
chicago: Meyer auf der Heide, Friedhelm, and Rolf Wanka. “Parallel Bridging Models
and Their Impact on Algorithm Design.” In Computational Science - ICCS 2001.
Berlin, Heidelberg, 2001. https://doi.org/10.1007/3-540-45718-6_68.
ieee: F. Meyer auf der Heide and R. Wanka, “Parallel Bridging Models and Their Impact
on Algorithm Design,” in Computational Science - ICCS 2001, Berlin, Heidelberg,
2001.
mla: Meyer auf der Heide, Friedhelm, and Rolf Wanka. “Parallel Bridging Models and
Their Impact on Algorithm Design.” Computational Science - ICCS 2001, 2001,
doi:10.1007/3-540-45718-6_68.
short: 'F. Meyer auf der Heide, R. Wanka, in: Computational Science - ICCS 2001,
Berlin, Heidelberg, 2001.'
date_created: 2020-04-09T10:51:36Z
date_updated: 2022-01-06T06:52:51Z
department:
- _id: '63'
doi: 10.1007/3-540-45718-6_68
language:
- iso: eng
place: Berlin, Heidelberg
publication: Computational Science - ICCS 2001
publication_identifier:
isbn:
- '9783540422334'
- '9783540457183'
issn:
- 0302-9743
publication_status: published
status: public
title: Parallel Bridging Models and Their Impact on Algorithm Design
type: book_chapter
user_id: '15415'
year: '2001'
...
---
_id: '16722'
citation:
ama: 'Meyer auf der Heide F, ed. Algorithms — ESA 2001, 9th Annual European Symposium
Århus, Denmark. Lecture Notes in Computer Science (LNCS, volume 2161). Berlin,
Heidelberg: Springer ; 2001. doi:10.1007/3-540-44676-1'
apa: 'Meyer auf der Heide, F. (Ed.). (2001). Algorithms — ESA 2001, 9th Annual
European Symposium Århus, Denmark (Lecture Notes in Computer Science (LNCS,
volume 2161)). Berlin, Heidelberg: Springer . https://doi.org/10.1007/3-540-44676-1'
bibtex: '@book{Meyer auf der Heide_2001, place={Berlin, Heidelberg}, edition={Lecture
Notes in Computer Science (LNCS, volume 2161)}, title={Algorithms — ESA 2001,
9th Annual European Symposium Århus, Denmark}, DOI={10.1007/3-540-44676-1},
publisher={Springer }, year={2001} }'
chicago: 'Meyer auf der Heide, Friedhelm, ed. Algorithms — ESA 2001, 9th Annual
European Symposium Århus, Denmark. Lecture Notes in Computer Science (LNCS,
Volume 2161). Berlin, Heidelberg: Springer , 2001. https://doi.org/10.1007/3-540-44676-1.'
ieee: 'F. Meyer auf der Heide, Ed., Algorithms — ESA 2001, 9th Annual European
Symposium Århus, Denmark, Lecture Notes in Computer Science (LNCS, Volume
2161). Berlin, Heidelberg: Springer , 2001.'
mla: Meyer auf der Heide, Friedhelm, editor. Algorithms — ESA 2001, 9th Annual
European Symposium Århus, Denmark. Lecture Notes in Computer Science (LNCS,
Volume 2161), Springer , 2001, doi:10.1007/3-540-44676-1.
short: F. Meyer auf der Heide, ed., Algorithms — ESA 2001, 9th Annual European Symposium
Århus, Denmark, Lecture Notes in Computer Science (LNCS, volume 2161), Springer
, Berlin, Heidelberg, 2001.
date_created: 2020-04-17T10:59:08Z
date_updated: 2022-01-06T06:52:55Z
department:
- _id: '63'
doi: 10.1007/3-540-44676-1
edition: Lecture Notes in Computer Science (LNCS, volume 2161)
editor:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
language:
- iso: eng
place: Berlin, Heidelberg
publication_identifier:
isbn:
- '9783540424932'
- '9783540446767'
issn:
- 0302-9743
publication_status: published
publisher: 'Springer '
status: public
title: Algorithms — ESA 2001, 9th Annual European Symposium Århus, Denmark
type: book_editor
user_id: '15415'
year: '2001'
...
---
_id: '3023'
author:
- first_name: Johannes
full_name: Blömer, Johannes
id: '23'
last_name: Blömer
citation:
ama: 'Blömer J. Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices.
In: Automata, Languages and Programming. Berlin, Heidelberg: Springer Berlin
Heidelberg; 2000:248-259. doi:10.1007/3-540-45022-x_22'
apa: 'Blömer, J. (2000). Closest Vectors, Successive Minima, and Dual HKZ-Bases
of Lattices. In Automata, Languages and Programming (pp. 248–259). Berlin,
Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-45022-x_22'
bibtex: '@inbook{Blömer_2000, place={Berlin, Heidelberg}, title={Closest Vectors,
Successive Minima, and Dual HKZ-Bases of Lattices}, DOI={10.1007/3-540-45022-x_22},
booktitle={Automata, Languages and Programming}, publisher={Springer Berlin Heidelberg},
author={Blömer, Johannes}, year={2000}, pages={248–259} }'
chicago: 'Blömer, Johannes. “Closest Vectors, Successive Minima, and Dual HKZ-Bases
of Lattices.” In Automata, Languages and Programming, 248–59. Berlin, Heidelberg:
Springer Berlin Heidelberg, 2000. https://doi.org/10.1007/3-540-45022-x_22.'
ieee: 'J. Blömer, “Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices,”
in Automata, Languages and Programming, Berlin, Heidelberg: Springer Berlin
Heidelberg, 2000, pp. 248–259.'
mla: Blömer, Johannes. “Closest Vectors, Successive Minima, and Dual HKZ-Bases of
Lattices.” Automata, Languages and Programming, Springer Berlin Heidelberg,
2000, pp. 248–59, doi:10.1007/3-540-45022-x_22.
short: 'J. Blömer, in: Automata, Languages and Programming, Springer Berlin Heidelberg,
Berlin, Heidelberg, 2000, pp. 248–259.'
date_created: 2018-06-05T08:27:28Z
date_updated: 2022-01-06T06:58:51Z
department:
- _id: '64'
doi: 10.1007/3-540-45022-x_22
page: 248-259
place: Berlin, Heidelberg
publication: Automata, Languages and Programming
publication_identifier:
isbn:
- '9783540677154'
- '9783540450221'
issn:
- 0302-9743
publication_status: published
publisher: Springer Berlin Heidelberg
status: public
title: Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices
type: book_chapter
user_id: '25078'
year: '2000'
...
---
_id: '17990'
abstract:
- lang: eng
text: We consider the notion of Property Testing as applied to computational geometry.
We aim at developing efficient algorithms which determine whether a given (geometrical)
object has a predetermined property Q or is 'far' from any object having the property.
We show that many basic geometric properties have very efficient testing algorithms,
whose running time is significantly smaller than the object description size.
author:
- first_name: Artur
full_name: Czumaj, Artur
last_name: Czumaj
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
citation:
ama: 'Czumaj A, Sohler C, Ziegler M. Property Testing in Computational Geometry.
In: Proceedings of the 8th Annual European Symposium on Algorithms (ESA’00).
Vol 4698. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer; 2000:155-166.
doi:10.1007/3-540-45253-2_15'
apa: 'Czumaj, A., Sohler, C., & Ziegler, M. (2000). Property Testing in Computational
Geometry. In Proceedings of the 8th Annual European Symposium on Algorithms
(ESA’00) (Vol. 4698, pp. 155–166). Berlin, Heidelberg: Springer. https://doi.org/10.1007/3-540-45253-2_15'
bibtex: '@inproceedings{Czumaj_Sohler_Ziegler_2000, place={Berlin, Heidelberg},
series={Lecture Notes in Computer Science}, title={Property Testing in Computational
Geometry}, volume={4698}, DOI={10.1007/3-540-45253-2_15},
booktitle={Proceedings of the 8th Annual European Symposium on Algorithms (ESA’00)},
publisher={Springer}, author={Czumaj, Artur and Sohler, Christian and Ziegler,
Martin}, year={2000}, pages={155–166}, collection={Lecture Notes in Computer Science}
}'
chicago: 'Czumaj, Artur, Christian Sohler, and Martin Ziegler. “Property Testing
in Computational Geometry.” In Proceedings of the 8th Annual European Symposium
on Algorithms (ESA’00), 4698:155–66. Lecture Notes in Computer Science. Berlin,
Heidelberg: Springer, 2000. https://doi.org/10.1007/3-540-45253-2_15.'
ieee: A. Czumaj, C. Sohler, and M. Ziegler, “Property Testing in Computational Geometry,”
in Proceedings of the 8th Annual European Symposium on Algorithms (ESA’00),
2000, vol. 4698, pp. 155–166.
mla: Czumaj, Artur, et al. “Property Testing in Computational Geometry.” Proceedings
of the 8th Annual European Symposium on Algorithms (ESA’00), vol. 4698, Springer,
2000, pp. 155–66, doi:10.1007/3-540-45253-2_15.
short: 'A. Czumaj, C. Sohler, M. Ziegler, in: Proceedings of the 8th Annual European
Symposium on Algorithms (ESA’00), Springer, Berlin, Heidelberg, 2000, pp. 155–166.'
date_created: 2020-08-14T13:48:54Z
date_updated: 2022-01-06T06:53:24Z
department:
- _id: '63'
doi: 10.1007/3-540-45253-2_15
intvolume: ' 4698'
language:
- iso: eng
page: 155-166
place: Berlin, Heidelberg
publication: Proceedings of the 8th Annual European Symposium on Algorithms (ESA'00)
publication_identifier:
isbn:
- '9783540410041'
- '9783540452539'
issn:
- 0302-9743
publication_status: published
publisher: Springer
series_title: Lecture Notes in Computer Science
status: public
title: Property Testing in Computational Geometry
type: conference
user_id: '15415'
volume: 4698
year: '2000'
...
---
_id: '18146'
abstract:
- lang: eng
text: 'Since its very beginning, linear algebra is a highly algorithmic subject.
Let us just mention the famous Gauss Algorithm which was invented before the theory
of algorithms has been developed. The purpose of this paper is to link linear
algebra explicitly to computable analysis, that is the theory of computable real
number functions. Especially, we will investigate in which sense the dimension
of a given linear subspace can be computed. The answer highly depends on how the
linear subspace is given: if it is given by a finite number of vectors whose linear
span represents the space, then the dimension does not depend continuously on
these vectors and consequently it cannot be computed. If the linear subspace is
represented via its distance function, which is a standard way to represent closed
subspaces in computable analysis, then the dimension does computably depend on
the distance function.'
author:
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
- first_name: Vasco
full_name: Brattka, Vasco
last_name: Brattka
citation:
ama: 'Ziegler M, Brattka V. Computing the Dimension of Linear Subspaces. In: SOFSEM
2000: Theory and Practice of Informatics. Vol 1963. Berlin, Heidelberg: Springer;
2000:450-458. doi:10.1007/3-540-44411-4_34'
apa: 'Ziegler, M., & Brattka, V. (2000). Computing the Dimension of Linear Subspaces.
In SOFSEM 2000: Theory and Practice of Informatics (Vol. 1963, pp. 450–458).
Berlin, Heidelberg: Springer. https://doi.org/10.1007/3-540-44411-4_34'
bibtex: '@inproceedings{Ziegler_Brattka_2000, place={Berlin, Heidelberg}, title={Computing
the Dimension of Linear Subspaces}, volume={1963}, DOI={10.1007/3-540-44411-4_34},
booktitle={SOFSEM 2000: Theory and Practice of Informatics}, publisher={Springer},
author={Ziegler, Martin and Brattka, Vasco}, year={2000}, pages={450–458} }'
chicago: 'Ziegler, Martin, and Vasco Brattka. “Computing the Dimension of Linear
Subspaces.” In SOFSEM 2000: Theory and Practice of Informatics, 1963:450–58.
Berlin, Heidelberg: Springer, 2000. https://doi.org/10.1007/3-540-44411-4_34.'
ieee: 'M. Ziegler and V. Brattka, “Computing the Dimension of Linear Subspaces,”
in SOFSEM 2000: Theory and Practice of Informatics, 2000, vol. 1963, pp.
450–458.'
mla: 'Ziegler, Martin, and Vasco Brattka. “Computing the Dimension of Linear Subspaces.”
SOFSEM 2000: Theory and Practice of Informatics, vol. 1963, Springer, 2000,
pp. 450–58, doi:10.1007/3-540-44411-4_34.'
short: 'M. Ziegler, V. Brattka, in: SOFSEM 2000: Theory and Practice of Informatics,
Springer, Berlin, Heidelberg, 2000, pp. 450–458.'
date_created: 2020-08-24T09:58:56Z
date_updated: 2022-01-06T06:53:26Z
department:
- _id: '63'
doi: 10.1007/3-540-44411-4_34
intvolume: ' 1963'
language:
- iso: eng
page: 450-458
place: Berlin, Heidelberg
publication: 'SOFSEM 2000: Theory and Practice of Informatics'
publication_identifier:
isbn:
- '9783540413486'
- '9783540444114'
issn:
- 0302-9743
publication_status: published
publisher: Springer
status: public
title: Computing the Dimension of Linear Subspaces
type: conference
user_id: '15415'
volume: 1963
year: '2000'
...
---
_id: '16497'
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Mirosław
full_name: Kutyłowski, Mirosław
last_name: Kutyłowski
- first_name: Prabhakar
full_name: Ragde, Prabhakar
last_name: Ragde
citation:
ama: 'Meyer auf der Heide F, Kutyłowski M, Ragde P. Complexity Theory and Algorithms.
In: Euro-Par 2000 Parallel Processing. Berlin, Heidelberg; 2000. doi:10.1007/3-540-44520-x_59'
apa: Meyer auf der Heide, F., Kutyłowski, M., & Ragde, P. (2000). Complexity
Theory and Algorithms. In Euro-Par 2000 Parallel Processing. Berlin, Heidelberg.
https://doi.org/10.1007/3-540-44520-x_59
bibtex: '@inbook{Meyer auf der Heide_Kutyłowski_Ragde_2000, place={Berlin, Heidelberg},
title={Complexity Theory and Algorithms}, DOI={10.1007/3-540-44520-x_59},
booktitle={Euro-Par 2000 Parallel Processing}, author={Meyer auf der Heide, Friedhelm
and Kutyłowski, Mirosław and Ragde, Prabhakar}, year={2000} }'
chicago: Meyer auf der Heide, Friedhelm, Mirosław Kutyłowski, and Prabhakar Ragde.
“Complexity Theory and Algorithms.” In Euro-Par 2000 Parallel Processing.
Berlin, Heidelberg, 2000. https://doi.org/10.1007/3-540-44520-x_59.
ieee: F. Meyer auf der Heide, M. Kutyłowski, and P. Ragde, “Complexity Theory and
Algorithms,” in Euro-Par 2000 Parallel Processing, Berlin, Heidelberg,
2000.
mla: Meyer auf der Heide, Friedhelm, et al. “Complexity Theory and Algorithms.”
Euro-Par 2000 Parallel Processing, 2000, doi:10.1007/3-540-44520-x_59.
short: 'F. Meyer auf der Heide, M. Kutyłowski, P. Ragde, in: Euro-Par 2000 Parallel
Processing, Berlin, Heidelberg, 2000.'
date_created: 2020-04-09T13:30:45Z
date_updated: 2022-01-06T06:52:51Z
department:
- _id: '63'
doi: 10.1007/3-540-44520-x_59
language:
- iso: eng
place: Berlin, Heidelberg
publication: Euro-Par 2000 Parallel Processing
publication_identifier:
isbn:
- '9783540679561'
- '9783540445203'
issn:
- 0302-9743
publication_status: published
status: public
title: Complexity Theory and Algorithms
type: book_chapter
user_id: '15415'
year: '2000'
...
---
_id: '2435'
author:
- first_name: Jens
full_name: Simon, Jens
id: '15273'
last_name: Simon
- first_name: Alexander
full_name: Reinefeld, Alexander
last_name: Reinefeld
- first_name: Oliver
full_name: Heinz, Oliver
last_name: Heinz
citation:
ama: 'Simon J, Reinefeld A, Heinz O. Large-Scale SCI Clusters in Practice: Architecture
and Performance in SCI. In: Hellwagner H, Reinefeld A, eds. SCI: Scalable Coherent
Interface. Architecture and Software for High-Performance Compute Clusters.
Vol 1734. Lecture Notes in Computer Science (LNCS). Berlin / Heidelberg: Springer;
1999:367-381. doi:10.1007/10704208'
apa: 'Simon, J., Reinefeld, A., & Heinz, O. (1999). Large-Scale SCI Clusters
in Practice: Architecture and Performance in SCI. In H. Hellwagner & A. Reinefeld
(Eds.), SCI: Scalable Coherent Interface. Architecture and Software for High-Performance
Compute Clusters (Vol. 1734, pp. 367–381). Berlin / Heidelberg: Springer.
https://doi.org/10.1007/10704208'
bibtex: '@inbook{Simon_Reinefeld_Heinz_1999, place={Berlin / Heidelberg}, series={Lecture
Notes in Computer Science (LNCS)}, title={Large-Scale SCI Clusters in Practice:
Architecture and Performance in SCI}, volume={1734}, DOI={10.1007/10704208},
booktitle={SCI: Scalable Coherent Interface. Architecture and Software for High-Performance
Compute Clusters}, publisher={Springer}, author={Simon, Jens and Reinefeld, Alexander
and Heinz, Oliver}, editor={Hellwagner, Hermann and Reinefeld, AlexanderEditors},
year={1999}, pages={367–381}, collection={Lecture Notes in Computer Science (LNCS)}
}'
chicago: 'Simon, Jens, Alexander Reinefeld, and Oliver Heinz. “Large-Scale SCI Clusters
in Practice: Architecture and Performance in SCI.” In SCI: Scalable Coherent
Interface. Architecture and Software for High-Performance Compute Clusters,
edited by Hermann Hellwagner and Alexander Reinefeld, 1734:367–81. Lecture Notes
in Computer Science (LNCS). Berlin / Heidelberg: Springer, 1999. https://doi.org/10.1007/10704208.'
ieee: 'J. Simon, A. Reinefeld, and O. Heinz, “Large-Scale SCI Clusters in Practice:
Architecture and Performance in SCI,” in SCI: Scalable Coherent Interface.
Architecture and Software for High-Performance Compute Clusters, vol. 1734,
H. Hellwagner and A. Reinefeld, Eds. Berlin / Heidelberg: Springer, 1999, pp.
367–381.'
mla: 'Simon, Jens, et al. “Large-Scale SCI Clusters in Practice: Architecture and
Performance in SCI.” SCI: Scalable Coherent Interface. Architecture and Software
for High-Performance Compute Clusters, edited by Hermann Hellwagner and Alexander
Reinefeld, vol. 1734, Springer, 1999, pp. 367–81, doi:10.1007/10704208.'
short: 'J. Simon, A. Reinefeld, O. Heinz, in: H. Hellwagner, A. Reinefeld (Eds.),
SCI: Scalable Coherent Interface. Architecture and Software for High-Performance
Compute Clusters, Springer, Berlin / Heidelberg, 1999, pp. 367–381.'
date_created: 2018-04-17T16:03:28Z
date_updated: 2022-01-06T06:56:18Z
department:
- _id: '27'
doi: 10.1007/10704208
editor:
- first_name: Hermann
full_name: Hellwagner, Hermann
last_name: Hellwagner
- first_name: Alexander
full_name: Reinefeld, Alexander
last_name: Reinefeld
intvolume: ' 1734'
language:
- iso: eng
page: 367-381
place: Berlin / Heidelberg
project:
- _id: '52'
name: Computing Resources Provided by the Paderborn Center for Parallel Computing
publication: 'SCI: Scalable Coherent Interface. Architecture and Software for High-Performance
Compute Clusters'
publication_identifier:
isbn:
- 978-3-540-47048-9
- 978-3-540-66696-7
issn:
- 0302-9743
publisher: Springer
series_title: Lecture Notes in Computer Science (LNCS)
status: public
title: 'Large-Scale SCI Clusters in Practice: Architecture and Performance in SCI'
type: book_chapter
user_id: '15273'
volume: 1734
year: '1999'
...
---
_id: '18959'
abstract:
- lang: eng
text: We investigate the problem of constructing spanners for a given set of points
that are tolerant for edge/vertex faults. Let S be a set of $n$ points in the
d-dimensional space and let k be an integer number. A k-edge/vertex fault tolerant
spanner for S has the property that after the deletion of k arbitrary edges/vertices
each pair of points in the remaining graph is still connected by a short path.
Recently
it was shown that for each set S of n points there exists a k-edge/vertex fault
tolerant spanner with O(k^2 n) edges which can be constructed in O(n log n + k^2
n) time. Furthermore, it was shown that for each set S of n points there exists
a k-edge/vertex fault tolerant spanner whose degree is bouned by O(c^k+1) for
some constant c.
Our first contribution is a construction of a k-vertex
fault tolerant spanner with O(kn) edges which is a tight bound. The computation
takes O(n log^d-1 n + k n log log n) time. Then we show that the same k-vertex
fault tolerant spanner is also k-edge fault tolerant. Thereafter, we construct
a k-vertex fault tolerant spanner with O(k^2 n) edges whose degree is bounded
by O(k^2). Finally, we give a more natural but stronger definition of k-edge fault
tolerance which not necessarily can be satisfied if one allows only simple edges
between the points of S. We investigate the question whether Steiner points help.
We answer this question affirmatively and prove Theta(kn) bounds on the number
of Steiner points and on the number of edges in such spanners.
author:
- first_name: Tamás
full_name: Lukovszki, Tamás
last_name: Lukovszki
citation:
ama: 'Lukovszki T. New Results on Fault Tolerant Geometric Spanners. In: Proceedings
of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS. ; 1999:193-204.
doi:10.1007/3-540-48447-7_20'
apa: Lukovszki, T. (1999). New Results on Fault Tolerant Geometric Spanners. In
Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99),
LNCS (pp. 193–204). https://doi.org/10.1007/3-540-48447-7_20
bibtex: '@inproceedings{Lukovszki_1999, title={New Results on Fault Tolerant Geometric
Spanners}, DOI={10.1007/3-540-48447-7_20},
booktitle={Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99),
LNCS}, author={Lukovszki, Tamás}, year={1999}, pages={193–204} }'
chicago: Lukovszki, Tamás. “New Results on Fault Tolerant Geometric Spanners.” In
Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS’99),
LNCS, 193–204, 1999. https://doi.org/10.1007/3-540-48447-7_20.
ieee: T. Lukovszki, “New Results on Fault Tolerant Geometric Spanners,” in Proceedings
of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS, 1999,
pp. 193–204.
mla: Lukovszki, Tamás. “New Results on Fault Tolerant Geometric Spanners.” Proceedings
of the 6th Workshop on Algorithms an Data Structures (WADS’99), LNCS, 1999,
pp. 193–204, doi:10.1007/3-540-48447-7_20.
short: 'T. Lukovszki, in: Proceedings of the 6th Workshop on Algorithms an Data
Structures (WADS’99), LNCS, 1999, pp. 193–204.'
date_created: 2020-09-03T13:03:45Z
date_updated: 2022-01-06T06:53:55Z
department:
- _id: '63'
doi: 10.1007/3-540-48447-7_20
language:
- iso: eng
page: 193-204
publication: Proceedings of the 6th Workshop on Algorithms an Data Structures (WADS'99),
LNCS
publication_identifier:
isbn:
- '9783540662792'
- '9783540484479'
issn:
- 0302-9743
publication_status: published
status: public
title: New Results on Fault Tolerant Geometric Spanners
type: conference
user_id: '15415'
year: '1999'
...
---
_id: '17053'
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Berthold
full_name: Vöcking, Berthold
last_name: Vöcking
- first_name: Matthias
full_name: Westermann, Matthias
last_name: Westermann
citation:
ama: 'Meyer auf der Heide F, Vöcking B, Westermann M. Provably Good and Practical
Strategies for Non-uniform Data Management in Networks. In: Algorithms - ESA’
99. Berlin, Heidelberg; 1999. doi:10.1007/3-540-48481-7_9'
apa: Meyer auf der Heide, F., Vöcking, B., & Westermann, M. (1999). Provably
Good and Practical Strategies for Non-uniform Data Management in Networks. In
Algorithms - ESA’ 99. Berlin, Heidelberg. https://doi.org/10.1007/3-540-48481-7_9
bibtex: '@inbook{Meyer auf der Heide_Vöcking_Westermann_1999, place={Berlin, Heidelberg},
title={Provably Good and Practical Strategies for Non-uniform Data Management
in Networks}, DOI={10.1007/3-540-48481-7_9},
booktitle={Algorithms - ESA’ 99}, author={Meyer auf der Heide, Friedhelm and Vöcking,
Berthold and Westermann, Matthias}, year={1999} }'
chicago: Meyer auf der Heide, Friedhelm, Berthold Vöcking, and Matthias Westermann.
“Provably Good and Practical Strategies for Non-Uniform Data Management in Networks.”
In Algorithms - ESA’ 99. Berlin, Heidelberg, 1999. https://doi.org/10.1007/3-540-48481-7_9.
ieee: F. Meyer auf der Heide, B. Vöcking, and M. Westermann, “Provably Good and
Practical Strategies for Non-uniform Data Management in Networks,” in Algorithms
- ESA’ 99, Berlin, Heidelberg, 1999.
mla: Meyer auf der Heide, Friedhelm, et al. “Provably Good and Practical Strategies
for Non-Uniform Data Management in Networks.” Algorithms - ESA’ 99, 1999,
doi:10.1007/3-540-48481-7_9.
short: 'F. Meyer auf der Heide, B. Vöcking, M. Westermann, in: Algorithms - ESA’
99, Berlin, Heidelberg, 1999.'
date_created: 2020-05-20T13:35:49Z
date_updated: 2022-01-06T06:53:03Z
department:
- _id: '63'
doi: 10.1007/3-540-48481-7_9
language:
- iso: eng
place: Berlin, Heidelberg
publication: Algorithms - ESA’ 99
publication_identifier:
isbn:
- '9783540662518'
- '9783540484813'
issn:
- 0302-9743
publication_status: published
status: public
title: Provably Good and Practical Strategies for Non-uniform Data Management in Networks
type: book_chapter
user_id: '15415'
year: '1999'
...
---
_id: '13608'
author:
- first_name: Michael
full_name: Eisenring, Michael
last_name: Eisenring
- first_name: Marco
full_name: Platzner, Marco
id: '398'
last_name: Platzner
- first_name: Lothar
full_name: Thiele, Lothar
last_name: Thiele
citation:
ama: 'Eisenring M, Platzner M, Thiele L. Communication Synthesis for Reconfigurable
Embedded Systems. In: Proceedings of the 9th International Workshop on Field
Programmable Logic and Applications (FPL). Vol 1673. LCS. Springer; 1999:205-214.
doi:10.1007/978-3-540-48302-1_21'
apa: Eisenring, M., Platzner, M., & Thiele, L. (1999). Communication Synthesis
for Reconfigurable Embedded Systems. In Proceedings of the 9th International
Workshop on Field Programmable Logic and Applications (FPL) (Vol. 1673, pp.
205–214). Springer. https://doi.org/10.1007/978-3-540-48302-1_21
bibtex: '@inproceedings{Eisenring_Platzner_Thiele_1999, series={LCS}, title={Communication
Synthesis for Reconfigurable Embedded Systems}, volume={1673}, DOI={10.1007/978-3-540-48302-1_21},
booktitle={Proceedings of the 9th International Workshop on Field Programmable
Logic and Applications (FPL)}, publisher={Springer}, author={Eisenring, Michael
and Platzner, Marco and Thiele, Lothar}, year={1999}, pages={205–214}, collection={LCS}
}'
chicago: Eisenring, Michael, Marco Platzner, and Lothar Thiele. “Communication Synthesis
for Reconfigurable Embedded Systems.” In Proceedings of the 9th International
Workshop on Field Programmable Logic and Applications (FPL), 1673:205–14.
LCS. Springer, 1999. https://doi.org/10.1007/978-3-540-48302-1_21.
ieee: M. Eisenring, M. Platzner, and L. Thiele, “Communication Synthesis for Reconfigurable
Embedded Systems,” in Proceedings of the 9th International Workshop on Field
Programmable Logic and Applications (FPL), 1999, vol. 1673, pp. 205–214.
mla: Eisenring, Michael, et al. “Communication Synthesis for Reconfigurable Embedded
Systems.” Proceedings of the 9th International Workshop on Field Programmable
Logic and Applications (FPL), vol. 1673, Springer, 1999, pp. 205–14, doi:10.1007/978-3-540-48302-1_21.
short: 'M. Eisenring, M. Platzner, L. Thiele, in: Proceedings of the 9th International
Workshop on Field Programmable Logic and Applications (FPL), Springer, 1999, pp.
205–214.'
date_created: 2019-10-04T21:01:05Z
date_updated: 2022-01-06T06:51:40Z
department:
- _id: '78'
doi: 10.1007/978-3-540-48302-1_21
extern: '1'
intvolume: ' 1673'
language:
- iso: eng
page: 205-214
publication: Proceedings of the 9th International Workshop on Field Programmable Logic
and Applications (FPL)
publication_identifier:
isbn:
- '9783540664574'
- '9783540483021'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer
series_title: LCS
status: public
title: Communication Synthesis for Reconfigurable Embedded Systems
type: conference
user_id: '398'
volume: 1673
year: '1999'
...
---
_id: '17412'
abstract:
- lang: eng
text: "We study algorithmic aspects in the management of geometric scenes in interactive
walkthrough animations. We consider arbitrarily large scenes consisting of unit
size balls. For a smooth navigation in the scene we have to fulfill hard real
time requirements. Therefore, we need algorithms whose running time is independent
of the total number of objects in the scene and that use as small space as possible.
In this work we focus on one of the basic operations in our walkthrough system:
reporting the objects around the visitor within a certain distance. Previously
a randomized data structure was presented that supports reporting the balls around
the visitor in an output sensitive time and allows insertion and deletion of objects
nearly as fast as searching. These results were achieved by exploiting the fact
that the visitor moves ''slowly'' through the scene. A serious disadvantage of
the aforementioned data structure is a big space overhead and the use of randomization.
Our first result is a construction of weak spanners that leads to an improvement
of the space requirement of the previously known data structures. Then we develop
a deterministic data structure for the searching problem in which insertion of
objects are allowed. Our incremental data structure supports O(1+k) reporting
time, where k is a certain quantity close to the number of reported objects. The
insertion time is similar to the reporting time and the space is linear to the
total number of objects.\r\n"
author:
- first_name: Matthias
full_name: Fischer, Matthias
id: '146'
last_name: Fischer
- first_name: Tamás
full_name: Lukovszki, Tamás
last_name: Lukovszki
- first_name: Martin
full_name: Ziegler, Martin
last_name: Ziegler
citation:
ama: 'Fischer M, Lukovszki T, Ziegler M. Geometric Searching in Walkthrough Animations
with Weak Spanners in Real Time. In: Algorithms — ESA’ 98. Berlin, Heidelberg;
1998. doi:10.1007/3-540-68530-8_14'
apa: Fischer, M., Lukovszki, T., & Ziegler, M. (1998). Geometric Searching in
Walkthrough Animations with Weak Spanners in Real Time. In Algorithms — ESA’
98. Berlin, Heidelberg. https://doi.org/10.1007/3-540-68530-8_14
bibtex: '@inbook{Fischer_Lukovszki_Ziegler_1998, place={Berlin, Heidelberg}, title={Geometric
Searching in Walkthrough Animations with Weak Spanners in Real Time}, DOI={10.1007/3-540-68530-8_14},
booktitle={Algorithms — ESA’ 98}, author={Fischer, Matthias and Lukovszki, Tamás
and Ziegler, Martin}, year={1998} }'
chicago: Fischer, Matthias, Tamás Lukovszki, and Martin Ziegler. “Geometric Searching
in Walkthrough Animations with Weak Spanners in Real Time.” In Algorithms —
ESA’ 98. Berlin, Heidelberg, 1998. https://doi.org/10.1007/3-540-68530-8_14.
ieee: M. Fischer, T. Lukovszki, and M. Ziegler, “Geometric Searching in Walkthrough
Animations with Weak Spanners in Real Time,” in Algorithms — ESA’ 98, Berlin,
Heidelberg, 1998.
mla: Fischer, Matthias, et al. “Geometric Searching in Walkthrough Animations with
Weak Spanners in Real Time.” Algorithms — ESA’ 98, 1998, doi:10.1007/3-540-68530-8_14.
short: 'M. Fischer, T. Lukovszki, M. Ziegler, in: Algorithms — ESA’ 98, Berlin,
Heidelberg, 1998.'
date_created: 2020-07-27T11:42:54Z
date_updated: 2022-01-06T06:53:11Z
ddc:
- '000'
department:
- _id: '63'
doi: 10.1007/3-540-68530-8_14
file:
- access_level: closed
content_type: application/pdf
creator: koala
date_created: 2020-08-27T11:20:38Z
date_updated: 2020-08-27T11:20:38Z
file_id: '18442'
file_name: hni-id-854.pdf
file_size: 266070
relation: main_file
success: 1
file_date_updated: 2020-08-27T11:20:38Z
has_accepted_license: '1'
language:
- iso: eng
place: Berlin, Heidelberg
publication: Algorithms — ESA’ 98
publication_identifier:
isbn:
- '9783540648482'
- '9783540685302'
issn:
- 0302-9743
publication_status: published
status: public
title: Geometric Searching in Walkthrough Animations with Weak Spanners in Real Time
type: book_chapter
user_id: '15415'
year: '1998'
...
---
_id: '16562'
author:
- first_name: Friedhelm
full_name: Meyer auf der Heide, Friedhelm
id: '15523'
last_name: Meyer auf der Heide
- first_name: Gabriel Terán
full_name: Martinez, Gabriel Terán
last_name: Martinez
citation:
ama: 'Meyer auf der Heide F, Martinez GT. Communication-efficient parallel multiway
and approximate minimum cut computation. In: LATIN’98: Theoretical Informatics.
Berlin, Heidelberg; 1998. doi:10.1007/bfb0054332'
apa: 'Meyer auf der Heide, F., & Martinez, G. T. (1998). Communication-efficient
parallel multiway and approximate minimum cut computation. In LATIN’98: Theoretical
Informatics. Berlin, Heidelberg. https://doi.org/10.1007/bfb0054332'
bibtex: '@inbook{Meyer auf der Heide_Martinez_1998, place={Berlin, Heidelberg},
title={Communication-efficient parallel multiway and approximate minimum cut computation},
DOI={10.1007/bfb0054332}, booktitle={LATIN’98:
Theoretical Informatics}, author={Meyer auf der Heide, Friedhelm and Martinez,
Gabriel Terán}, year={1998} }'
chicago: 'Meyer auf der Heide, Friedhelm, and Gabriel Terán Martinez. “Communication-Efficient
Parallel Multiway and Approximate Minimum Cut Computation.” In LATIN’98: Theoretical
Informatics. Berlin, Heidelberg, 1998. https://doi.org/10.1007/bfb0054332.'
ieee: 'F. Meyer auf der Heide and G. T. Martinez, “Communication-efficient parallel
multiway and approximate minimum cut computation,” in LATIN’98: Theoretical
Informatics, Berlin, Heidelberg, 1998.'
mla: 'Meyer auf der Heide, Friedhelm, and Gabriel Terán Martinez. “Communication-Efficient
Parallel Multiway and Approximate Minimum Cut Computation.” LATIN’98: Theoretical
Informatics, 1998, doi:10.1007/bfb0054332.'
short: 'F. Meyer auf der Heide, G.T. Martinez, in: LATIN’98: Theoretical Informatics,
Berlin, Heidelberg, 1998.'
date_created: 2020-04-15T10:34:15Z
date_updated: 2022-01-06T06:52:52Z
department:
- _id: '63'
doi: 10.1007/bfb0054332
language:
- iso: eng
place: Berlin, Heidelberg
publication: 'LATIN''98: Theoretical Informatics'
publication_identifier:
isbn:
- '9783540642756'
- '9783540697152'
issn:
- 0302-9743
- 1611-3349
publication_status: published
status: public
title: Communication-efficient parallel multiway and approximate minimum cut computation
type: book_chapter
user_id: '15415'
year: '1998'
...
---
_id: '13606'
author:
- first_name: Marco
full_name: Platzner, Marco
id: '398'
last_name: Platzner
- first_name: Giovanni
full_name: De Micheli, Giovanni
last_name: De Micheli
citation:
ama: 'Platzner M, De Micheli G. Acceleration of satisfiability algorithms by reconfigurable
hardware. In: Proceedings of the 8th International Workshop on Field Programmable
Logic and Applications (FPL) . LNCS. Berlin, Heidelberg: Springer ; 1998:69-78.
doi:10.1007/bfb0055234'
apa: 'Platzner, M., & De Micheli, G. (1998). Acceleration of satisfiability
algorithms by reconfigurable hardware. In Proceedings of the 8th International
Workshop on Field Programmable Logic and Applications (FPL) (pp. 69–78).
Berlin, Heidelberg: Springer . https://doi.org/10.1007/bfb0055234'
bibtex: '@inproceedings{Platzner_De Micheli_1998, place={Berlin, Heidelberg}, series={LNCS},
title={Acceleration of satisfiability algorithms by reconfigurable hardware},
DOI={10.1007/bfb0055234}, booktitle={Proceedings
of the 8th International Workshop on Field Programmable Logic and Applications
(FPL) }, publisher={Springer }, author={Platzner, Marco and De Micheli, Giovanni},
year={1998}, pages={69–78}, collection={LNCS} }'
chicago: 'Platzner, Marco, and Giovanni De Micheli. “Acceleration of Satisfiability
Algorithms by Reconfigurable Hardware.” In Proceedings of the 8th International
Workshop on Field Programmable Logic and Applications (FPL) , 69–78. LNCS.
Berlin, Heidelberg: Springer , 1998. https://doi.org/10.1007/bfb0055234.'
ieee: M. Platzner and G. De Micheli, “Acceleration of satisfiability algorithms
by reconfigurable hardware,” in Proceedings of the 8th International Workshop
on Field Programmable Logic and Applications (FPL) , 1998, pp. 69–78.
mla: Platzner, Marco, and Giovanni De Micheli. “Acceleration of Satisfiability Algorithms
by Reconfigurable Hardware.” Proceedings of the 8th International Workshop
on Field Programmable Logic and Applications (FPL) , Springer , 1998, pp.
69–78, doi:10.1007/bfb0055234.
short: 'M. Platzner, G. De Micheli, in: Proceedings of the 8th International Workshop
on Field Programmable Logic and Applications (FPL) , Springer , Berlin, Heidelberg,
1998, pp. 69–78.'
date_created: 2019-10-04T20:46:34Z
date_updated: 2022-01-06T06:51:40Z
department:
- _id: '78'
doi: 10.1007/bfb0055234
extern: '1'
language:
- iso: eng
page: 69-78
place: Berlin, Heidelberg
publication: 'Proceedings of the 8th International Workshop on Field Programmable
Logic and Applications (FPL) '
publication_identifier:
isbn:
- '9783540649489'
- '9783540680666'
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: 'Springer '
series_title: LNCS
status: public
title: Acceleration of satisfiability algorithms by reconfigurable hardware
type: conference
user_id: '398'
year: '1998'
...