MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Edelkamp, Stefan
Meyer, Ulrich
dblp
dblp
Editor(s):
Baader, F.
Brewka, G.
Eiter, T.
dblp
dblp
dblp
BibTeX cite key*:
EdelkampMeyer2001
Title, Booktitle
Title*:
Theory and Practice of Time-Space Trade-Offs in Memory Limited Search
Booktitle*:
Proceedings of the Joint German/Austrian Conference on AI: Advances in Artificial Intelligence (KI-01)
Event, URLs
Conference URL::
http://www.kr.tuwien.ac.at/KI2001/
Downloading URL:
Event Address*:
Wien, Österreich
Language:
English
Event Date*
(no longer used):
September, 19 - September, 21
Organization:
Event Start Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Event End Date:
Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected Incorrect data type for operator or @Function: Time/Date expected
Publisher
Name*:
Springer
URL:
http://www.springer.de/
Address*:
Berlin, Germany
Type:
Vol, No, Year, pp.
Series:
Lecture Notes in Computer Science
Volume:
2174
Number:
Month:
September
Pages:
169-184
Year*:
2001
VG Wort Pages:
27
ISBN/ISSN:
3-540-42612-4
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
We establish $O(n \log n)$ minimum-space algorithms that
omit both the open and the closed list to determine the
shortest path between every two nodes and study the gap
in between full memorization in a hash table and the
information-theoretic lower bound. The proposed structure
of suffix-lists elaborates on a concise binary representation of
states by applying bit-state hashing techniques.
Significantly more states can be stored while searching and
inserting $n$ items into suffix lists is still available in
$O(n \log n)$ time. Bit-state hashing leads to the new paradigm of
partial iterative-deepening heuristic search, in which full exploration
is sacrificed for a better detection of duplicates in large search
depth. We give first promising results in the application area of
communication protocols.
Download
Access Level:

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Audience:
Expert
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{EdelkampMeyer2001,
AUTHOR = {Edelkamp, Stefan and Meyer, Ulrich},
EDITOR = {Baader, F. and Brewka, G. and Eiter, T.},
TITLE = {Theory and Practice of Time-Space Trade-Offs in Memory Limited Search},
BOOKTITLE = {Proceedings of the Joint German/Austrian Conference on AI: Advances in Artificial Intelligence (KI-01)},
PUBLISHER = {Springer},
YEAR = {2001},
VOLUME = {2174},
PAGES = {169--184},
SERIES = {Lecture Notes in Computer Science},
ADDRESS = {Wien, Österreich},
MONTH = {September},
ISBN = {3-540-42612-4},
}


Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Ulrich Meyer
Created
06/12/2001 03:22:00 PM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Uwe Brahm
Uwe Brahm
Anja Becker
Anja Becker
Anja Becker
Edit Dates
01/20/2009 07:14:31 PM
04/25/2002 07:39:00 PM
08.04.2002 14:55:44
04.04.2002 13:27:03
08/01/2002 11:10:58