License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.09061.12
URN: urn:nbn:de:0030-drops-20924
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2092/
Go to the corresponding Portal

Mosenkis, Viktor ; Naumann, Uwe ; Peise, Elmar

Low-Memory Tour Reversal in Directed Graphs

pdf-format:
09061.MosenkisViktor.ExtAbstract.2092.pdf (0.09 MB)

Abstract

We consider the problem of reversing a {em tour} $(i_1,i_2,ldots,i_l)$ in a directed graph $G=(V,E)$ with positive integer vertices $V$ and edges
$E subseteq V imes V$, where $i_j in V$ and $(i_j,i_{j+1}) in E$ for
all $j=1,ldots,l-1.$ The tour can be processed in last-in-first-out order as long as the size of the corresponding stack does not exceed the available memory. This constraint is violated in most cases when considering control-flow graphs of large-scale numerical simulation programs. The tour reversal problem also arises in adjoint programs used, for example, in the context of derivative-based nonlinear optimization, sensitivity analysis, or
other, often inverse, problems. The intention is to compress the tour in order not to run out of memory. As the general optimal compression problem was proven to be NP-hard and big control-flow graphs results from loops in programs we do not want to use general purpose algorithms to compress the tour. We want rather to compress the tour by finding loops and replace the redundant information by proper representation of the loops.

BibTeX - Entry

@InProceedings{mosenkis_et_al:DagSemProc.09061.12,
  author =	{Mosenkis, Viktor and Naumann, Uwe and Peise, Elmar},
  title =	{{Low-Memory Tour Reversal in Directed Graphs}},
  booktitle =	{Combinatorial Scientific Computing},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9061},
  editor =	{Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2009/2092},
  URN =		{urn:nbn:de:0030-drops-20924},
  doi =		{10.4230/DagSemProc.09061.12},
  annote =	{Keywords: Directed graph, tour reversal, offline algorithm, dynamic programming, online algorithm, control-flow reversal, adjoint program}
}

Keywords: Directed graph, tour reversal, offline algorithm, dynamic programming, online algorithm, control-flow reversal, adjoint program
Collection: 09061 - Combinatorial Scientific Computing
Issue Date: 2009
Date of publication: 24.07.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI