Campus Event Calendar: R. Fleischer; K. Mehlhorn (03/26/1999 in MPI/007)

Campus Event Calendar

Campus Event Calendar:
- All Upcoming:
  - only for D1
  - only for D2
  - only for INET
  - only for D4
  - only for D5
  - only for D6
  - only for RG1
  - Mailing Lists
  - by Speaker
  - by Type
  - by Category
  - by Title
  - Calendar
  - RSS Feed
- History of Events:

Event Entry

What and Who

Linear time 2-approximation for weighted matching; Stoer-Wagner Mincut

R. Fleischer; K. Mehlhorn

MPI

SIG Meeting: Approx+Online

AG 1, AG 2

AG Audience

English

Note: We use this to send email in the morning.

Date, Time and Location

Friday, 26 March 99

11:00

-- Not specified --

MPI

007

Saarbrücken

Abstract

Rudolf will first speak about a new 2-approximation weighted

matching algorithm by R. Preis (STACS'99).
Then Kurt will present the Stoer-Wagner algorithm for computing minimum cuts in
undirected networks (LEDAbook, chapter on graph algorithms, section
mincut). He will also show how to compute a correctness certificate
for the algorithm (http://www.mpi-sb.mpg.de/~mehlhorn/ftp/mincut.ps).

Contact

Rudolf Fleischer

9325-119

--email hidden

System used:

Meeting URL:

Meeting ID:

Passcode:

passcode not visible

Code Visible for:

logged in users only

Tags, Category, Keywords and additional notes

Keywords, Tags:

approximation algorithm, weighted matching, min cut

Imprint / Impressum | Data Protection / Datenschutzhinweis