$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Matematyka Dyskretna
(prowadzone przez M.Woźniaka)

We wtorek, 28 kwietnia 2004 roku, o godzinie 12:45

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

Karol SUCHAN

(Laboratoire d'Informatique Fondamentale d'Orléans)

wygłosi referat pod tytułem:

Przeszkody dla małej ,drzewo-grubości"

Pojęcie dobrej charakteryzacji zostało po raz pierwszy zaproponowane w 1965 r. przez J. Edmondsa. Charakteryzacja własności grafów jest dobra, jeżeli określa dwa dopełniające się stwierdzenia dotyczące grafu. To znaczy, pierwsze stwierdzenie jest prawdziwe wtedy i tylko wtedy, gdy drugie jest fałszywe. Dodatkowo, dla każdego z tych stwierdzeń, dobra charakteryzacja dostarcza łatwo sprawdzalnego certyfikatu. Tak więc, dla każdej dobrej charakteryzacji, odpowiedni problem decyzyjny należy do klasy NP $\cap$ co-NP. W kontekście ,drzewo-grubości", jeżeli tw$(G) \leq k$, to potrafimy skonstruować ,drzewo-dekompozycję" grubości $w \leq k$. Natomiast nie potrafimy podać certyfikatu zaświadczającego że tw$(G) > k$. W jego poszukiwaniu zwracamy się do twierdzeń mini-maksowych, określających że grubości drzewo-dekompozycji grafu $G$ są ograniczone z dołu przez charakterystyki pewnych struktur występujących w $G$. Struktury te są przeszkodami dla małej drzewo-grubości grafu.

Serdecznie zapraszamy wszystkich chętnych !