eprintid: 87
rev_number: 4
eprint_status: archive
userid: 5
dir: disk0/00/00/00/87
datestamp: 2007-02-05
lastmod: 2015-05-29 19:47:09
status_changed: 2009-04-08 16:53:56
type: report
metadata_visibility: show
item_issues_count: 0
creators_name: Bisseling, Rob H.
creators_name: Byrka, Jarosław
creators_name: Cerav-Erbas, Selin
creators_name: Gvozdenovíc, Nebojša
creators_name: Lorenz, Mathias
creators_name: Pendavingh, Rudi
creators_name: Reeves, Colin
creators_name: Röger, Matthias
creators_name: Verhoeven, Arie
title: Partitioning a call graph
ispublished: pub
subjects: telecom
studygroups: esgi52
companyname: Software Improvement Group
full_text_status: public
abstract: Splitting a large software system into smaller and more manageable units has become an important problem for many organizations. The basic structure of a software system is given by a directed graph with vertices representing the programs of the system and arcs representing calls from one program to another. Generating a good partitioning into smaller modules becomes a minimization problem for the number of programs being called by external programs. First, we formulate an equivalent integer linear programming problem with 0–1 variables. theoretically, with this approach the problem can be solved to optimality, but this becomes very costly with increasing size of the software system. Second, we formulate the problem as a hypergraph partitioning problem. This is a heuristic method using a multilevel strategy, but it turns out to be very fast and to deliver solutions that are close to optimal.
date: 2005-02-04
date_type: published
pages: 13
citation:   Bisseling, Rob H. and Byrka, Jarosław and Cerav-Erbas, Selin and Gvozdenovíc, Nebojša and Lorenz, Mathias and Pendavingh, Rudi and Reeves, Colin and Röger, Matthias and Verhoeven, Arie  (2005) Partitioning a call graph.  [Study Group Report]     
document_url: http://miis.maths.ox.ac.uk/miis/87/1/callgraph.pdf