$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Zakładu Matematyki Dyskretnej
Wydziału Matematyki Stosowanej
AGH

We wtorek, 10 czerwca 2003 roku, o godzinie 12:45

w sali 304, łącznik A-3-A-4, A G H

Gyula Y. KATONA

(Budapest Univ. of Technology)

wygłosi referat pod tytułem:

Structure Theorem and Algorithm

on $(1,f)$-odd subgraphs

The authors give a Gallai-Edmonds type structure theorem on $(1,f)$-odd subgraphs and a polynomial algorithm for finding an optimal $(1,f)$-odd subgraph. Lovász and Cornuéjols solved these problems for a more general problem, the general factor problem with gaps at most $1$. However, the statements of the theorems and the algorithm are much more simple in this special case, so it is worth of interest on its own. Also, the algorithm given for this case is faster than the general algorithm. The proofs follow a direct approach instead of deducing from the general case.

Serdecznie zapraszamy wszystkich chętnych !