Minerva  

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


     
  Homepage  
     
  19th GAMM-Seminar
January, 23th-25th, 2003
 
     
  Announcement  
  Registration  
  Participants  
  Programme  
  Abstracts ->
  Proceedings  
     
  Archive  
     
  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!