Volume

Dagstuhl Seminar Proceedings, Volume 9491

Publication Details

  • published at: 2010-03-02
  • Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik

Access Numbers

Documents

No documents found matching your filter selection.
Document
DOI: 10.4230/DagSemProc.09491.1
09491 Abstracts Collection – Graph Search Engineering

Authors: Lubos Brim, Stefan Edelkamp, Eric A. Hansen, and Peter Sanders

Abstract
From the 29th November to the 4th December 2009, the Dagstuhl Seminar 09491 ``Graph Search Engineering '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Lubos Brim, Stefan Edelkamp, Eric A. Hansen, and Peter Sanders. 09491 Abstracts Collection – Graph Search Engineering. In Graph Search Engineering. Dagstuhl Seminar Proceedings, Volume 9491, pp. 1-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{brim_et_al:DagSemProc.09491.1,
  author =	{Brim, Lubos and Edelkamp, Stefan and Hansen, Eric A. and Sanders, Peter},
  title =	{{09491 Abstracts Collection – Graph Search Engineering}},
  booktitle =	{Graph Search Engineering},
  pages =	{1--31},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9491},
  editor =	{Lubos Brim and Stefan Edelkamp and Erik A. Hansen and Peter Sanders},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09491.1},
  URN =		{urn:nbn:de:0030-drops-24315},
  doi =		{10.4230/DagSemProc.09491.1},
  annote =	{Keywords: Model Checking, Artificial Intelligence, AI Planning, State Explosion Problem, Error Detection, Protocol Analysis, Software Verification and Validation, Heuristics, Pattern/Abstraction Databases, I/O Efficient Search, Solid State Disks, GPU}
}
Document
DOI: 10.4230/DagSemProc.09491.2
Dynamic State-Space Partitioning in External-Memory Graph Search

Authors: Rong Zhou and Eric A. Hansen

Abstract
State-of-the-art external-memory graph search algorithms rely on a hash function, or equivalently, a state-space projection function, that partitions the stored nodes of the state-space search graph into groups of nodes that are stored as separate files on disk. The scalability and efficiency of the search depends on properties of the partition: whether the number of unique nodes in a file always fits in RAM, the number of files into which the nodes of the state-space graph are partitioned, and how well the partitioning of the state space captures local structure in the graph. All previous work relies on a static partitioning of the state space. In this paper, we introduce a method for dynamic partitioning of the state-space search graph and show that it leads to substantial improvement of search performance.
Cite as

Rong Zhou and Eric A. Hansen. Dynamic State-Space Partitioning in External-Memory Graph Search. In Graph Search Engineering. Dagstuhl Seminar Proceedings, Volume 9491, pp. 1-7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{zhou_et_al:DagSemProc.09491.2,
  author =	{Zhou, Rong and Hansen, Eric A.},
  title =	{{Dynamic State-Space Partitioning in External-Memory Graph Search}},
  booktitle =	{Graph Search Engineering},
  pages =	{1--7},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9491},
  editor =	{Lubos Brim and Stefan Edelkamp and Erik A. Hansen and Peter Sanders},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09491.2},
  URN =		{urn:nbn:de:0030-drops-24334},
  doi =		{10.4230/DagSemProc.09491.2},
  annote =	{Keywords: External-memory graph search, heuristic search}
}
Document
DOI: 10.4230/DagSemProc.09491.3
Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?

Authors: Malte Helmert and Carmel Domshlak

Abstract
Current heuristic estimators for classical domain-independent planning are usually based on one of four ideas: delete relaxation, abstraction, critical paths, and, most recently, landmarks. Previously, these different ideas for deriving heuristic functions were largely unconnected. In my talk, I will show that these heuristics are in fact very closely related. Moreover, I will introduce a new admissible heuristic called the landmark cut heuristic which exploits this relationship. In our experiments, the landmark cut heuristic provides better estimates than other current admissible planning heuristics, especially on large problem instances.
Cite as

Malte Helmert and Carmel Domshlak. Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?. In Graph Search Engineering. Dagstuhl Seminar Proceedings, Volume 9491, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{helmert_et_al:DagSemProc.09491.3,
  author =	{Helmert, Malte and Domshlak, Carmel},
  title =	{{Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?}},
  booktitle =	{Graph Search Engineering},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9491},
  editor =	{Lubos Brim and Stefan Edelkamp and Erik A. Hansen and Peter Sanders},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.09491.3},
  URN =		{urn:nbn:de:0030-drops-24324},
  doi =		{10.4230/DagSemProc.09491.3},
  annote =	{Keywords: Planning, heuristic search, heuristic functions}
}

Filters

  • Authors
  • B
  • Brim, Lubos
  • D
  • Domshlak, Carmel
  • E
  • Edelkamp, Stefan
  • H
  • Hansen, Eric A.
  • Helmert, Malte
  • S
  • Sanders, Peter
  • Z
  • Zhou, Rong

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact