de.mpg.escidoc.pubman.appbase.FacesBean
English
 
HelpDisclaimerContact usLogin
  Advanced SearchBrowse

Item

  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.), Proceedings of the Joint German/Austrian Conference on AI: Advances in Artificial Intelligence (KI-01) (pp. 169-184). Berlin, Germany: Springer.

Item is

Basic

show hide
Bookmark this item: http://pubman.mpdl.mpg.de/pubman/item/escidoc:1330596:2
Genre: Conference Paper

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, escidoc: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
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 Identifiers: eDoc: 518172
Other: Local-ID: C1256428004B93B8-61CD1C052EFB5BBEC1256A6900496CFE-EdelkampMeyer2001
 Degree: -

Event

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

Legal Case

show

Source 1

show
hide
Title: Proceedings of the Joint German/Austrian Conference on AI: Advances in Artificial Intelligence (KI-01)
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, escidoc:40045            
Publ. Info: Berlin, Germany : 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
Source Genre: Series
 Creator(s):
-
Affiliations:
-
Publ. Info: -
Pages: - Volume / Issue: 2174 Sequence Number: - Start / End Page: - Identifier: -