Mosenkis, Viktor ;
Naumann, Uwe ;
Peise, Elmar
LowMemory Tour Reversal in Directed Graphs
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,l1.$ The tour can be processed in lastinfirstout 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 controlflow graphs of largescale numerical simulation programs. The tour reversal problem also arises in adjoint programs used, for example, in the context of derivativebased 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 NPhard and big controlflow 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:DSP:2009:2092,
author = {Viktor Mosenkis and Uwe Naumann and Elmar Peise},
title = {LowMemory Tour Reversal in Directed Graphs},
booktitle = {Combinatorial Scientific Computing},
year = {2009},
editor = {Uwe Naumann and Olaf Schenk and Horst D. Simon and Sivan Toledo},
number = {09061},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2092},
annote = {Keywords: Directed graph, tour reversal, offline algorithm, dynamic programming, online algorithm, controlflow reversal, adjoint program}
}
Keywords: 

Directed graph, tour reversal, offline algorithm, dynamic programming, online algorithm, controlflow reversal, adjoint program 
Seminar: 

09061  Combinatorial Scientific Computing

Issue date: 

2009 
Date of publication: 

24.07.2009 