MPI-INF Logo
Publications

Thesis (Server    domino.mpi-inf.mpg.de)

Thesis

Master's thesis | @MastersThesis{Nissen98, ... | Masterarbeit

Nissen, Marco

Graph Iterators: Decoupling Graph Structures from Algorithms

Universität des Saarlandes, March, 1998

Integrated into LEDA


I will present a way to implement graph algorithms which is
different from traditional methods. This work was motivated by the
belief that some ideas from software engineering should be applied
to graph algorithms. Re-usability of software is an important and
difficult problem in general, and this is particularly true for
graph algorithms. The scientific literature demonstrates plenty of
applications of graph algorithms as subroutines for other
algorithms. Moreover, many practical problems from various domains
may be modeled as graph problems and hence solved by means of graph
algorithms. Chapter 2 introduces some data structures that will be
used in 5 basic graph algorithms in chapter 3. Chapter 4 discusses
an implementation of a maximum cardinality matching algorithm for
general graphs. Chapter 5 explains some techniques in C++, which
are useful to implement the data structures and algorithms in an
efficient way. Finally chapter 6 contains some concluding remarks.
STL LEDA Graphiterators Iterator Design Pattern
Mehlhorn, Kurt
Wagner, Dorothea (Universität Konstanz)
Uhrig, Christian
Completed
Max-Planck-Institut für Informatik
Algorithms and Complexity Group
experts only
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list


BibTeX Entry:
@MASTERSTHESIS{Nissen98,
AUTHOR = {Nissen, Marco},
TITLE = {Graph Iterators: Decoupling Graph Structures from Algorithms},
SCHOOL = {Universit{\"a}t des Saarlandes},
YEAR = {1998},
TYPE = {Master's thesis}
MONTH = {March},
NOTE = {Integrated into LEDA},
}



Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Evelyn Haak
Created
11/11/1998 01:33:07 PM
Revisions
5.
4.
3.
2.
1.
Editor(s)
Uwe Brahm
Uwe Brahm
Marco Nissen
Marco Nissen
Marco Nissen
Edit Dates
05/20/2007 08:04:02 PM
31.03.99 22:25:56
10/03/99 08:54:00
10/03/99 08:49:04
19.11.98 22:22:47