Home News About Us Contact Contributors Disclaimer Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Display Documents



ID: 518172.0, MPI für Informatik / Algorithms and Complexity Group
Theory and Practice of Time-Space Trade-Offs in Memory Limited Search
Authors:Edelkamp, Stefan; Meyer, Ulrich
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2001
Title of Proceedings:Proceedings of the Joint German/Austrian Conference on AI: Advances in Artificial Intelligence (KI-01)
Start Page:169
End Page:184
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Wien, Österreich
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-61CD1C052EFB5BBEC1256A6900496CFE-...
ISBN:3-540-42612-4
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.