Martin Tancer: d-collapsibility is NP-complete for d greater or equal to 4
Abstract: A simplicial complex is d-collapsible if it can be reduced to
an empty complex by repeatedly removing (collapsing) a face of dimension
at most d-1 that is contained in a unique maximal face. We prove that the
algorithmic question whether a given simplicial complex is d-collapsible
is NP-complete for d greater or equal to 4 and polynomial time solvable
for d at most 2.
As an intermediate step, we prove that d-collapsibility can be recognized
by the greedy algorithm for d at most 2, but the greedy algorithm does not
work for d greater or equal 3.
Graph theory and algorithms seminar
15. 10. 2008
Seminar za osnove bo na obisku pri seminarju za diskretno matematiko
Torek 14.10.2008, od 10h do 12h, Plemljev seminar, Jadranska 19
Mathematics and theoretical computing seminar
13. 10. 2008
Klemen Šivic: Komutirajoci pari v centralizatorju matrike z enako velikimi Jordanovimi kletkami
Algebra seminar
13. 10. 2008
Vito Vitrih: Integracija nad mrežami na simpleksih (2. del); Selena Praprotnik: Uvod v finančno matematiko - finančni trgi, terminske pogodbe, opcije
Sreda 15.10.2008 od 10h do 12h, soba 3.06 na Jadranski 21
Numerical analysis seminar
11. 10. 2008
Gašper Zadnik: Konfiguracijski prostori grafov, 1. del
V ponedeljek, 13. oktobra 2008 ob 12. uri v predavalnici 3.07 na Jadranski 21
Topology seminar
10. 10. 2008
Tadej Starčič: Baza q-kompletnih okolic kompaktne q-kompletne analitične množice
Complex analysis seminar
9. 10. 2008
Lê Dũng Tráng: Topology of local surface singularities
Četrtek, 16. 10. 2008, ob 18.15 v predavalnici 2.02 na Jadranski 21.
Mathematics colloquium
8. 10. 2008
Sandi Klavžar: Novejši rezultati o strukturi kartezičnih produktov grafov
Graph theory and algorithms seminar
7. 10. 2008
Seminar za osnove v letu 2008/09
Seminar se prične 14. 10. 2008 ob 12h.
Mathematics and theoretical computing seminar
7. 10. 2008
Vito Vitrih: Integracija nad mrežami na simpleksih; Bor Plestenjak: Poročila s konferenc
Sreda 8.10.2008 od 10h do 12h, soba 3.06 na Jadranski 21
Numerical analysis seminar
7. 10. 2008
Jose Antonio Vilches (Univerza v Sevilli): Non-compact discrete Morse theory
V ponedeljek, 6. oktobra 2008 ob 12. uri v predavalnici 3.07 na Jadranski 21
Topology seminar
3. 10. 2008
Damjana Kokol Bukovšek: Semitranzitivne podpolgrupe v IS_n majhne moči
Algebra seminar
3. 10. 2008
R. Skrekovski: Planar graphs without 3-,7-,8-cycles are 3-choosable
Thursday, October 2, 2008, at 12:15 in room 3.07, Jadranska 21
Graph theory and algorithms seminar
30. 9. 2008
Emil Žagar, Andrej Muhič: Poročila s konferenc
Sreda 1.10.2008 od 10h do 11h, soba 3.06 na Jadranski 21
Numerical analysis seminar
29. 9. 2008
João Pita Costa: A Categorical Perspective on Skew Lattices
Sreda, 1. oktrobra 2008, ob 10. uri v Plemljevem seminarju, Jadranska 19/III, Ljubljana.
Algebra seminar
25. 9. 2008
Seminar za numerično analizo v letu 2008/09
Sreda 1.10.2008 od 10h do 12h, soba 3.06 na Jadranski 21
Numerical analysis seminar
25. 9. 2008
Jernej Barbič: Od matematike prek računalniške grafike do mehanike
Četrtek, 25. 9. 2008, ob 18.15 v predavalnici 2.02 na Jadranski 21.
Mathematics colloquium
16. 9. 2008
Robert Samal in Bojan Mohar
Monday (!!), September 15, 2008, at 12:15 in room PS, Jadranska 19
Graph theory and algorithms seminar
11. 9. 2008
Paul Taylor: The importance of subspace topology
Četrtek 12.6.2007, od 14h do 16h, soba 3.07 na Jadranski 21
Mathematics and theoretical computing seminar
12. 6. 2008
Zagovor doktorata Marjete Krajnc
Četrtek, 12.6.2008 ob 9h v 3.05, Jadranska 21
Numerical analysis seminar
9. 6. 2008
