2 Search Results for "Gustedt, Jens"


Document
Optimal Decremental Connectivity in Planar Graphs

Authors: Jakub Lacki and Piotr Sankowski

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)


Abstract
We show an algorithm for dynamic maintenance of connectivity information in an undirected planar graph subject to edge deletions. Our algorithm may answer connectivity queries of the form 'Are vertices u and v connected with a path?' in constant time. The queries can be intermixed with any sequence of edge deletions, and the algorithm handles all updates in O(n) time. This results improves over previously known O(n \log n) time algorithm.

Cite as

Jakub Lacki and Piotr Sankowski. Optimal Decremental Connectivity in Planar Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 608-621, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)


Copy BibTex To Clipboard

@InProceedings{lacki_et_al:LIPIcs.STACS.2015.608,
  author =	{Lacki, Jakub and Sankowski, Piotr},
  title =	{{Optimal Decremental Connectivity in Planar Graphs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{608--621},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.608},
  URN =		{urn:nbn:de:0030-drops-49457},
  doi =		{10.4230/LIPIcs.STACS.2015.608},
  annote =	{Keywords: decremental connectivity, planar graphs, dynamic connectivity, algorithms}
}
Document
Data Handover: Reconciling Message Passing and Shared Memory

Authors: Jens Gustedt

Published in: Dagstuhl Seminar Proceedings, Volume 5081, Foundations of Global Computing (2006)


Abstract
Data Handover (DHO) is a programming paradigm and interface that aims to handle data between parallel or distributed processes that mixes aspects of message passing and shared memory. It is designed to overcome the potential problems in terms of efficiency of both: (1) memory blowup and forced copies for message passing and (2) data consistency and latency problems for shared memory. Our approach attempts to be simple and easy to understand. It contents itself with just a handful of functions to cover the main aspects of coarse grained inter-operation upon data.

Cite as

Jens Gustedt. Data Handover: Reconciling Message Passing and Shared Memory. In Foundations of Global Computing. Dagstuhl Seminar Proceedings, Volume 5081, pp. 1-13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{gustedt:DagSemProc.05081.3,
  author =	{Gustedt, Jens},
  title =	{{Data Handover: Reconciling Message Passing and Shared Memory}},
  booktitle =	{Foundations of Global Computing},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5081},
  editor =	{Jos\'{e} Luiz Fiadeiro and Ugo Montanari and Martin Wirsing},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05081.3},
  URN =		{urn:nbn:de:0030-drops-2977},
  doi =		{10.4230/DagSemProc.05081.3},
  annote =	{Keywords: Efficient data management, message passing, shared memory}
}
  • Refine by Author
  • 1 Gustedt, Jens
  • 1 Lacki, Jakub
  • 1 Sankowski, Piotr

  • Refine by Classification

  • Refine by Keyword
  • 1 Efficient data management
  • 1 algorithms
  • 1 decremental connectivity
  • 1 dynamic connectivity
  • 1 message passing
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2006
  • 1 2015

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