19th GAMM-Seminar Leipzig on
High-dimensional problems - Numerical treatment and applications

Max-Planck-Institute for Mathematics in the Sciences
Inselstr. 22-26, D-04103 [O->]Leipzig
Phone: +49.341.9959.752, Fax: +49.341.9959.999

  19th GAMM-Seminar
January, 23th-25th, 2003
  Abstracts ->
  All seminars  
  All proceedings  
  Abstract Anand Srivastav, Fri, 18.00-18.25 Previous Contents Next  
  Graphpartitioning: Complexity and Algorithms
Anand Srivastav (Uni Kiel)

Graphpartitioning is the problem, where we wish to partition the set of nodes of a fitnite graph into a fixed number k of sets such that the number of crossing edges is minimum. This is a classical problem in combinatorial optimization with many applications in computer science and numerical mathematics. The problem is NP-hard, already for k=2 (this special case is the so called graph bisection problem). The present complexity status of the problem is on the one hand side that polynomial time approximation algorithms achieving a constant factor approximation of the optimum are not known, while on the other hand very efficient heuristics are used in practise, but proofs ar missing. We will survey the known facts about algorithms and complexity of the problem, and will present recent algorithmic progress.

This talk presents joint work with Gerold Jäger.

    Previous Contents Next  

Last updated:
30.11.2004 Impressum
Concept, Design and Realisation
[O->]Jens Burmeister (Uni Kiel), Kai Helms (MPI Leipzig)
Valid HTML 4.0!