English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Theory and Practice of Time-space Trade-offs in Memory Limited Search

Edelkamp, S., & Meyer, U. (2001). Theory and Practice of Time-space Trade-offs in Memory Limited Search. In F. Baader, G. Brewka, & T. Eiter (Eds.), KI 2001: Advances in Artificial Intelligence (pp. 169-184). Berlin: Springer.

Item is

Files

show Files

Locators

show

Creators

show
hide
 Creators:
Edelkamp, Stefan, Author
Meyer, Ulrich1, Author           
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              

Content

show
hide
Free keywords: -
 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.

Details

show
hide
Language(s): eng - English
 Dates: 2010-03-022001
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 518172
Other: Local-ID: C1256428004B93B8-61CD1C052EFB5BBEC1256A6900496CFE-EdelkampMeyer2001
DOI: 10.1007/3-540-45422-5_13
 Degree: -

Event

show
hide
Title: KI 2001
Place of Event: Wien, Österreich
Start-/End Date: -

Legal Case

show

Project information

show

Source 1

show
hide
Title: KI 2001: Advances in Artificial Intelligence
  Subtitle : Book Subtitle Joint German/Austrian Conference on AI Vienna, Austria, September 19–21, 2001 Proceedings
Source Genre: Proceedings
 Creator(s):
Baader, F.1, Editor           
Brewka, G., Editor
Eiter, T., Editor
Affiliations:
1 Programming Logics, MPI for Informatics, Max Planck Society, ou_40045            
Publ. Info: Berlin : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 169 - 184 Identifier: ISBN: 3-540-42612-4

Source 2

show
hide
Title: Lecture Notes in Computer Science
  Abbreviation : LNCS
Source Genre: Series
 Creator(s):
Affiliations:
Publ. Info: -
Pages: - Volume / Issue: 2174 Sequence Number: - Start / End Page: - Identifier: -