Kombinatorický seminář v LS 2006/2007

Program

26.2.úvodní seminář, burza článků a povídání o procházení čtverce/krychle lomenou čarou
5.3.Zdeněk VilušinskýS. Wu, U. Manber, G. Myers: An O(NP) Sequence Comparison Algorithm
(hezký převod řetězcové úlohy na grafovou)
12.3.Petr ŠkodaS. Aravamuthan, S. Lodha: Covering Codes for Hats-on-a-line
Dnešním hostem byl Jiří Fiala a pověděl nám o lokálních homomorfismech
19.3.Tomáš GavenčiakM. Paterson, U. Zwick: Overhang
26.3.Povídání o problému procházení krychle.
Dnešním hostem byl Jan Kratochvíl.
2.4.Jan HladkýB. Sudakov: Making a K4-free graph bipartite
9.4.Velikonoce
16.4.Jarní škola
23.4.Tereza KlimošováBarteld Kooi: Yet another Mastermind strategy.
30.4.Jan HladkýMetoda polynomů pro věty o množinových systémech
7.5.Státní skorosvátek
14.5.Lukáš MachSoft heaps (dle Bernarda Chazella)
21.5.

Další články k referování

E. Ackerman: On the maximum number of edges in topological graphs with no four pairwise crossing edges
(náročnější článek, použití metody dischargingu na známý geometrický problém)
S. Akbari, V. S. Mirrokni, B. S. Sadjad: A relation between choosability and uniquely list colorability
(připomenutí Alon-Tarsiho věty)
M. Albertson, D. B. West: Extending precolorings to circular colorings
(rozšiřování předbarvování pro cirkulární barevnost, zajímavé problémy, pole neorané)
N. Alon et al.: Testing Triangle-Freeness in General Graphs
(dolní a horní odhad na známý problém hledání trojúhelníků)
J. Anderson, H. Wu: An extremal problem on contractible edges in 3-connected graphs
(jednoduché procvičení práce s kontrahovatelnými hranami v 3-souvislých grafech)
M. Axenovich, R. E. Jamison: Canonical pattern Ramsey numbers
(trocha kanonické Ramseyovy teorie)
J. Balogh: A remark on the number of edge colorings of graphs
(jednoduché počítání hranových obarvení)
D. P. Biebighauser, M. N. Ellingham: Prism-hamiltonicity of triangulations
(procvičení práce s 3-souvislými rovinnými grafy)
A. Bohra, L. S. Chandran, J. K. Raju: Boxicity of series-parallel graphs
(jednoduché připomenutí sériově-paralelních grafů na geometrických reprezentacích)
G. Borradaile, P. Klein: An O(n log n) algorithm for maximum st-flow in a directed planar graph
(trochu delší, ale pěkný článek o algoritmu na toky v planární síti)
R. Čada et al.: Hamiltonian decompositions of prisms over cubic graphs
(zajímavý důkaz z oblasti hamiltonovských kružnic)
S. Chaudhuri, C. D. Zaroliagis: Shortest Paths in Digraphs of Small Treewidth (Part I)
(jak předzpracovat graf s malou stromovou šířkou a pak rychle hledat nejkratší cesty)
A. A. Diwan: Disconnected 2-factors in planar cubic bridgeless graphs
(důkaz jednoho otevřeného problému; téma nabízí velký prostor pro další práci)
N. Gazit, M. Krivelevich: On the assymptotic value of the choice number of complete multipartite graphs
(pravděpodbnostní počítání vybíravosti grafů, hodně výpočtů)
P. Heggernes, D. Lokshtanov: Optimal broadcast domination of arbitrary graphs in polynomial time
(zobecnění dominance grafů, které je překvapivě polynomiální)
T. Kaiser: A note on interconnecting matchings in graphs
(aplikace jedné moc zajímavé věty o matroidech a simpliciálních komplexech)
P. Keevash, B. Sudakov: The Turán number of the Fano plane
(trocha extremální kombinatoriky)
K. Kenthapadi, R. Panigrahy: Balanced Allocation on Graphs
(pěkné zobecnění hashování, kombinatorika a pravděpodobnost)
H.-J. Lai, X. Yao: Group connectivity of graphs with diameter at most 2
(článek o trošku opomíjeném konceptu grupové souvislosti)
M. Lemos: On the number of non-isomorphic matroids
(zajímavý článek o matroidech)
S. McGuinness: Circuits through cocircuits in a graph with extensions to matroids
(hodně vět o grafech je spíše o matroidech)
D. Maister: Computing treewidth and minimum fill-in for permutation graphs in linear time
(jak zacházet s permutačními grafy)
R. Naserasr: K5-free bound for the class of planar graphs
(jednoduchý článek o grafových homomorfismech)
S. Norine, R. Thomas: Minimal bricks
(jednoduchý článek o důležitém pojmu bricků)
C. Tardif: The fractional chromatic number of the categorical product of graphs
(jednoduchý článek o zlomkové barevnosti)
G. Tóth: Note on the pair-crossing number
(nový odhad na průsečíková čísla grafů, krátký a přístupný důkaz)
R. Xu, C.-Q. Zhang: On flows in bidirected graphs
(trochu opomíjené dvojtoky)

Webmaster: kamweb@kam.mff.cuni.cz         Modified: 30. 10. 2007