4 Search Results for "Bauer, Reinhard"


Document
On the Complexity of Partitioning Graphs for Arc-Flags

Authors: Reinhard Bauer, Moritz Baum, Ignaz Rutter, and Dorothea Wagner

Published in: OASIcs, Volume 25, 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2012)


Abstract
Precomputation of auxiliary data in an additional off-line step is a common approach towards improving the performance of shortest-path queries in large-scale networks. One such technique is the arc-flags algorithm, where the preprocessing involves computing a partition of the input graph. The quality of this partition significantly affects the speed-up observed in the query phase. It is evaluated by considering the search-space size of subsequent shortest-path queries, in particular its maximum or its average over all queries. In this paper, we substantially strengthen existing hardness results of Bauer et al. and show that optimally filling this degree of freedom is NP-hard for trees with unit-length edges, even if we bound the height or the degree. On the other hand, we show that optimal partitions for paths can be computed efficiently and give approximation algorithms for cycles and trees.

Cite as

Reinhard Bauer, Moritz Baum, Ignaz Rutter, and Dorothea Wagner. On the Complexity of Partitioning Graphs for Arc-Flags. In 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 25, pp. 71-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)


Copy BibTex To Clipboard

@InProceedings{bauer_et_al:OASIcs.ATMOS.2012.71,
  author =	{Bauer, Reinhard and Baum, Moritz and Rutter, Ignaz and Wagner, Dorothea},
  title =	{{On the Complexity of Partitioning Graphs for Arc-Flags}},
  booktitle =	{12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{71--82},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-45-3},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{25},
  editor =	{Delling, Daniel and Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2012.71},
  URN =		{urn:nbn:de:0030-drops-37048},
  doi =		{10.4230/OASIcs.ATMOS.2012.71},
  annote =	{Keywords: shortest paths, arc-flags, search space, preprocessing, complexity}
}
Document
14. Experimental Study on Speed-Up Techniques for Timetable Information Systems

Authors: Reinhard Bauer, Daniel Delling, and Dorothea Wagner

Published in: OASIcs, Volume 7, 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07) (2007)


Abstract
During the last years, impressive speed-up techniques for Dijkstra's algorithm have been developed. Unfortunately, recent research mainly focused on road networks. However, fast algorithms are also needed for other applications like timetable information systems. Even worse, the adaption of recently developed techniques to timetable information is often more complicated than expected. In this work, we check whether results from road networks are transferable to timetable information. To this end, we present an extensive experimental study of the most prominent speed-up techniques on different types of inputs. It turns out that recently developed techniques are much slower on graphs derived from timetable information than on road networks. In addition, we gain amazing insights into the behavior of speed-up techniques in general.

Cite as

Reinhard Bauer, Daniel Delling, and Dorothea Wagner. 14. Experimental Study on Speed-Up Techniques for Timetable Information Systems. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07). Open Access Series in Informatics (OASIcs), Volume 7, pp. 209-225, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)


Copy BibTex To Clipboard

@InProceedings{bauer_et_al:OASIcs.ATMOS.2007.1169,
  author =	{Bauer, Reinhard and Delling, Daniel and Wagner, Dorothea},
  title =	{{14. Experimental Study on Speed-Up Techniques for Timetable Information Systems}},
  booktitle =	{7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'07)},
  pages =	{209--225},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-04-0},
  ISSN =	{2190-6807},
  year =	{2007},
  volume =	{7},
  editor =	{Ahuja, Ravindra K. and Liebchen, Christian and Mesa, Juan A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2007.1169},
  URN =		{urn:nbn:de:0030-drops-11695},
  doi =		{10.4230/OASIcs.ATMOS.2007.1169},
  annote =	{Keywords: Speed-up techniques, timetable information, shortest path}
}
Document
Analysis of Dynamic Communicating Systems by Hierarchical Abstraction

Authors: Jörg Bauer and Reinhard Wilhelm

Published in: Dagstuhl Seminar Proceedings, Volume 6081, Software Verification: Infinite-State Model Checking and Static Program Analysis (2006)


Abstract
We propose a new abstraction technique for verifying topology properties of dynamic communicating systems (DCS), a special class of infinite-state systems. DCS are characterized by unbounded creation and destruction of objects along with an evolving communication connectivity or topology. We employ a lightweight graph transformation system to specify DCS. Hierarchical Abstraction (HA) computes a bounded over-approximation of all topologies that can occur in a DCS directly from its transformation rules. HA works in two steps. First, for each connected component, called cluster, of a topology, objects sharing a common property are summarized to one abstract object. Then isomorphic abstract connected components are summarized to one abstract component, called abstract cluster. This yields a conservative approximation of all graphs that may occur during any DCS run. The technique is implemented.

Cite as

Jörg Bauer and Reinhard Wilhelm. Analysis of Dynamic Communicating Systems by Hierarchical Abstraction. In Software Verification: Infinite-State Model Checking and Static Program Analysis. Dagstuhl Seminar Proceedings, Volume 6081, pp. 1-25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{bauer_et_al:DagSemProc.06081.3,
  author =	{Bauer, J\"{o}rg and Wilhelm, Reinhard},
  title =	{{Analysis of Dynamic Communicating Systems by Hierarchical Abstraction}},
  booktitle =	{Software Verification: Infinite-State Model Checking and Static Program Analysis},
  pages =	{1--25},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6081},
  editor =	{Parosh Aziz Abdulla and Ahmed Bouajjani and Markus M\"{u}ller-Olm},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06081.3},
  URN =		{urn:nbn:de:0030-drops-7271},
  doi =		{10.4230/DagSemProc.06081.3},
  annote =	{Keywords: Graph transformation, Abstract Interpretation, Shape Analysis}
}
Document
Abstract Interpretation of Graph Transformation

Authors: Jörg Bauer and Reinhard Wilhelm

Published in: Dagstuhl Seminar Proceedings, Volume 6161, Simulation and Verification of Dynamic Systems (2006)


Abstract
The semantics of many dynamic systems can be described by evolving graphs. Graph transformation systems (GTS) are a natural, intuitive, and formally defined method to specify systems of evolving graphs, whereas verification techniques for GTS are scarce. We present an abstract interpretation based approach for GTS verification. Single graphs are abstracted in two steps. First similar nodes within a connected component, then similar abstracted connected components are summarized. Transformation rules are applied directly to abstract graphs yielding a bounded set of abstract graphs of bounded size that over-approximates the concrete GTS and can be used for further verification. Since our abstraction is homomorphic, existential positive properties are preserved under abstraction. Furthermore, we identify automatically checkable completeness criteria for the abstraction. The technique is implemented and successfully tested on the platoon case study.

Cite as

Jörg Bauer and Reinhard Wilhelm. Abstract Interpretation of Graph Transformation. In Simulation and Verification of Dynamic Systems. Dagstuhl Seminar Proceedings, Volume 6161, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)


Copy BibTex To Clipboard

@InProceedings{bauer_et_al:DagSemProc.06161.5,
  author =	{Bauer, J\"{o}rg and Wilhelm, Reinhard},
  title =	{{Abstract Interpretation of Graph Transformation}},
  booktitle =	{Simulation and Verification of Dynamic Systems},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6161},
  editor =	{David M. Nicol and Corrado Priami and Hanne Riis Nielson and Adelinde M. Uhrmacher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06161.5},
  URN =		{urn:nbn:de:0030-drops-7039},
  doi =		{10.4230/DagSemProc.06161.5},
  annote =	{Keywords: Abstract Interpretation, Graph Transformation}
}
  • Refine by Author
  • 2 Bauer, Jörg
  • 2 Bauer, Reinhard
  • 2 Wagner, Dorothea
  • 2 Wilhelm, Reinhard
  • 1 Baum, Moritz
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Abstract Interpretation
  • 1 Graph Transformation
  • 1 Graph transformation
  • 1 Shape Analysis
  • 1 Speed-up techniques
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2006
  • 1 2007
  • 1 2012

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