V zimním semestru 2013/14 má kód BI-TS1 (případně MI-TS1) a koná se každou Středu od 14:30 v místnosti T2:C3-54. To je v budově FELu Technická 2 (tenhle vchod), konkrétně v části C3 (za vrátnicí chodbou v přízemí vlevo), místnost 54 (první druhé dveře napravo).
V případě příznivých stavebních podmínek by mohl být přesunut do budovy A, ale o tom byste byli včas informováni.
Seminář vedou společně Ondřej Suchý a Tomáš Valla.
Chcete-li nás kontaktovat, napište na email ondrej.suchy@fit nebo tomas.valla@fit (místo @fit doplňte @fit.cvut.cz).
Program semináře
Teoretický seminář v zimním semestru 2013/14 skončil. Těšíme se na setkání s Vámi v letním semestru.
Následuje
BI/MI-TS2
Minulý program
25.9. Přivítání s novými tvářemi, výběr článků
Dne 2.10.2013 promluvil Josef Malík na téma Persistentní Trie.
Dne 9.10.2013 představil Jan Cejhon článek Complete Solutions for a Combinatorial Puzzle in Linear Time, jehož autory jsou Lei Wang, Xiaodong Wang, Yingjie Wu a Daxin Zhu.
Dne 16.10.2013 představil Ondřej Fiedler článek The (K,k)-capacitated spanning tree problem, jehož autory jsou Esther M. Arkin, Nili Guttmann-Beck a Refael Hassin.
Dne 23.10.2013 představil Stanislav Zubal článek Hercules versus Hidden Hydra Helper, jehož autory jsou Jiří Matoušek a Martin Loebl.
Dne 30.10.2013 představil Adam Kučera článek A nonenumerative algorithm to find the k longest (shortest) paths in a DAG, jehož autorem je Fatih Koçan.
Dne 6.11.2013 promluvil Tomáš Valla na téma Ramseyova věta a věty podobného typu.
Dne 13.11.2013 představil David Příhoda článek Packing a Knapsack of Unknown Capacity, jehož autory jsou Yann Disser, Max Klimm, Nicole Megow a Sebastian Stiller.
Dne 20.11.2013 mluvili Ondřej Suchý a Tomáš Valla o Pravděpodobnostní metodě.
Dne 27.11.2013 představil Matyáš Kopp článek Testing Mutual Duality of Planar Graphs , jehož autory jsou Patrizio Angelini, Thomas Bläsius a Ignaz Rutter.
Dne 4.12.2013 promluvili Ondřej Suchý a Tomáš Valla o Kombinatorických odhadech.
Dne 11.12.2013 promluvil Michal Polívka na téma Vehicle Routing.
Dne 18.12.2013 proběhl Závěrečný vánoční seminář, o Splay stromečcích mluvil Tomáš Valla.
Jesse Stern: Spider Solitaire is NP-Complete
Aneb jak vyuzit vasi babicku :-) PDF
Graham: Fault-free Tilings of Rectangles
Vyplnovani obdelniku obdelnicky tak, aby zadna spara nebyla skrz. PDF
Chung, Gilbert, Graham, Shearer, van Lint: Tiling Rectangles with Rectangles
Zkouma se pokryvani obdelniku obdelnicky takove, ze neexistuje netrivialni podobdelnicek, jehoz hrany by vsechny byli sparami. PDF
Laurent Bulteau, Guillaume Fertin, Irena Rusu: Pancake Flipping Is Hard
Otaceni palacinek tim, ze se do hromady palacinek nekam zapichne obracecka a vse nad ni se obrati. Cilem je je setridit aby nejvetsi byla dole. Ukazuje se NP-tezkost.
PDF
Sergio Cabello, Jean Cardinal, Stefan Langerman: The Clique Problem in Ray Intersection Graphs
Uvazme graf, kde kazdemu vrcholu odpovida poloprimka v rovine a dva vrcholy jsou sousedy, pokud se poloprimky protinaji. Ukazuje se, ze kazdy takovy graf je komplementem nejakeho sudeho podrozdeleni rovinneho grafu. V dusledku toho je klika v takovych grafech tezka. PDF
Rani Hod, Alon Naor: Component Games on Regular Graphs
Studuji se hry na grafech, kdy si dva hraci stridave berou hrany. Jeden se snazi ze svych hran vytvorit velkou komponentu a druhy mu brani. Ukazuje se kdo kdy zvitezi na d-regularnich grafech. PDF
Tomasz Krawczyk, Arkadiusz Pawlik, And Bartosz Walczak: Coloring Triangle-Free Rectangular Frame Intersection
Graphs with O(log log n) Colors
Graf, kde vrcholy jsou (prazdne) obdelniky rovnobezne s osami a jsou spojene hranou pokud se protinaji, lze obarvit O(log log n) barvami. Pouzivaji se netrivialni vysledky odjinud, ale snad je nejaka myslenka i tady. PDF
Brendan D. McKay, Adolfo Piperno: Practical graph isomorphism, II
Souhrn jak se dnes resi grafovy isomorfismus. Mozna bude tezke najit neco rozumneho, co by se dalo odprezentovat. PDF
Dmitriy Nuriyev: A DP Approach to Hamiltonian Path Problem
Netrivialni "polynomialni" algoritmus resici tento NP uplny problem. Jde o to najit chybu. Mozna spise pro nekoho, kdo nechce prezentovat? PDF
el Houcein el Abdalaoui, Mohamed Dahmoune, and Djelloul Ziadi: On the transition reduction problem for finite
automata
Jde o to minimalizovat konecny automat, tentokrate nikoliv co do poctu stavu, nybrz co do poctu prechodu. PDF
Benjamin Doerr, Anton Eremeev, Frank Neumann, Madeleine Theile, Christian Thyssen: Evolutionary Algorithms and Dynamic
Programming
Srovnani DP a evolucnich algoritmu a jak prevadet jedno na druhe. Hodne dlouhe a asi ne moc presentovatelne. PDF
Guillaume Bonfante, Florian Deloup: The genus of regular languages
Rod grafu je (zjednodusene receno) pocet usi, ktere musim pridat kouli, abych na ni mohl nakreslit tento graf bez krizeni. Zkoumaji se regularni jazyky podle rodu grafu jejich automatu. Pomerne dlouhe a mozna slozite pro nekoho kdo se zatim moc nesetkal s topologii. PDF
Richard Southwell and Chris Cannings: Best Response Games on Regular Graphs
Hry v socialnich sitich kdy kazdy hrac nejakym zpusobem reaguje na chovani ostatnich. Trochu nejasne, co se vlastne dela, prevadi se to na deleni mnohodimenzionalniho prostoru... Celkem dlouhe, mozna by se z toho dalo neco vybrat. PDF
Artur Jeż: Approximation Of Grammar-Based Compression Via Recompression
Linearni algoritmus, ktery vystoupi malou bezkontextovou gramatiku, ktera vygeneruje vstupni retezec. Jen o logaritmus vetsi, nez velikost nejmensi takove.
Takove algoritmy byly znamy, ale tenhle je pry "jednoduchy s jednoduchou analyzou". PDF
Amy Glen and Jamie Simpson: The Total Run Length of a Word
Beh ve slove je jeho periodicke podslovo o delce aspon dvou jeho period. Ukazuji se odhady na soucet delek vseh behu ve slove dane delky. PDF
Mohsen Ghaffari, Bernhard Haeupler, Majid Khabbazian: A Bound on the Throughput of Radio Networks
Studuje se model radiovych siti, kde v kazdem kole kazde AP bud vysila, nebo prijima a prijme prave tehdy kdyz vysila prave jeden z jeho sousedu. Cilem je distribuovat k zprav po grafu, aby se je dozvedel kazdy. Predstavuje se sit s malym diametrem, ktera potrebuje hodne kol. Potreba trochu pravdepodobnosti. PDF
Vida Dujmovic: Graph Layouts via Layered Separators
Ukazuji se vylepsene odhady na tzv. trackove a frontove cislo planarnich grafu. V obou pripadech se nejak radi vrcholy a rodeluji se hrany nebo vrcholy do skupin tak, ze hrany (v jedne skupine) respektuji poradi vrcholu - nekrizi se. PDF
Michal Adamaszek: The Smallest Nonevasive Graph Property
Vlastnost je "tekava", pokud se kazdy algoritmus, ktery ji testuje musi v nejhorsim pripade zeptat na existenci kazde hrany. Vetsina vlastnosti takovych je, ukazuje se jedna na 5-i vrcholech, ktera takova neni. Velmi kratke a jednoduche. PDF
Igor Pak And Jed Yang: Tiling Simply Connected Regions With Rectangles
Vi se, ze dlazdeni obecneho utvaru dvema obdelniky je tezke, kdezto dlazdeni jednodusse souvisleho utvaru dvema obdelniky je jednoduche. Ukazuje se, ze dlazdeni jedn. souv. utv. miliony obdelniku je tezke. Mozna by bylo zajimave nastudovat i ten znamy algoritmus, ale to uz by asi bylo moc dlouhe. PDF
A. Ahadia, A. Dehghan: The Complexity of the Proper Orientation Number
Orientace grafu je vlastni, pokud kazde dva sousedni vrcholy maji v teto orientaci jiny vystupni stupen. Minimalizuje se potrebny vystupni stupen. Ukazuje se NP-tezkost pro rovinne a 4-regularni grafy a poly algortimus pro 3-regularni. PDF
Alejandro Erickson and Frank Ruskey: Domino Tatami Covering is NP-complete
DLazdi se pravouhly utvar pomoci kostek domina tak, aby se zadne 4 kostky nepotkali v jednom bode. Ukazuje se NP-uplnost a jeji dusledky pro hledani specialniho parovani v jistych grafech PDF
Hai-Jun Zhou: The Feedback Vertex Set Problem: a Spin Glass Approach
V problemu jde o to najit mnozinu vrcholu, ktera protina vsechny cykly grafu, a je NP-uplny. Zavadi se nejaky "spin glass" model, ktery prevadi vyse uvedenou globalni pominku na lokalni pro kazdou hranu. Ten se resi pomoci bilief propagation a ukazuje se, ze to dava dobrou aproximaci. Zni to komplikovane. PDF
Patrizio Angelini, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli: Morphing Planar Graph Drawings Efficiently
Hleda se spojita transformace mezi dvema rovinnymi useckovymi nakreslenimi grafu. Ukazuje se, ze takova transformace se da rozdelit O(n^2) casti, z nichz kazda je linearni, coz vylepsuje starsi vysledky. Snad ta myslenka neni moc skryta v referencich. PDF
Brešar, Klavžar, Rall: Domination game played on trees and spanning subgraphs
Dominator a Prodluzovac hraji hru na grafu: stridave vybiraji vrcholy tak,
aby vybrana mnozina dominovala aspon o 1 vrchol vic nez v predchozim tahu.
Dominator se snazi hru ukoncit co nejdrive, Prodluzovac ji prodluzuje.
Otazka je, na jak dlouho obema hracum jejich strategie vydrzi.
Clanek to studuje pro stromy a kostry grafu.
PDF
Axenovich, Osang: Unavoidable subtrees
Uvazme mnozinu M vsech stromu na K vrcholech.
Kolik minimalne vrcholu N potrebuju, aby libovolny strom T na N vrcholech
obsahoval aspon jeden strom z M jako podstrom?
PDF
Palbom: Complexity of the directed spanning cactus problem
Kaktus K je podgraf grafu G, ktery je silne souvisly orientovany graf,
jeho kazda hrana je obsazena v prave jednom cyklu, a spojuje
vsechny vrchol z G.
Clanek studuje vypocetni slozitost hledani kaktusu v zadanem grafu.
PDF
Meeks, Scott: The complexity of flood-filling games on graphs
Clanek studuje kombinatorickou hru Free-Flood-It, kde se hraci
minimalni poctem tahu "flood-fill" snazi udelat barevny hraci plan
jednobarevny.
PDF
Shao, Chao: Recursive method to solve the problem of "Gambling with God"
Co se stane, kdyz chci hrat hazardni hru s vsemocnym bohem? :-)
PDF
Brimkov, Leach, Wu, Mastroianni: Approximation algorithms for a geometric set cover problem
Kdyz mame na vstupu mnozinu usecek v rovine, existuje
mala mnozina bodu, ktera protina vsechny zadane usecky?
Rozhodnout tento problem je vypocetne obtizne, clanek tedy zkouma
aproximacni pristupy.
PDF
Demange, Stefano, Leroy-Beaulieu: On the online track assignment problem
Jak studovat vypravovani vlaku pomoci barveni grafu?
PDF
Hoang, Kaminski, Sawada, Sritharan: Finding and listing induced paths and cycles
Jak efektivne hledat a vypsat vsechny indukovane cesty v grafu?
PDF
Anily, Pfeffer: The uncapacitated swapping problem on a line and on a circle
Mame graf s vyznacenymi zdrojovymi a cilovymi vrcholy se zbozim,
a mame autickem povymenovat zbozi na nich tak, aby najelo minimalni trasu.
To je obecne NP-tezke. Clanek ukazuje polynomialni algoritmy pro
line grafy a circle grafy.
PDF
Feldheim, Hod: 3/2 firefighters are not enough
Na grafu vypukl ohen, ktery se siri do sousednich vrcholu.
Kolik hasicu potrebujeme, abychom pozar uhasili na rovinne mrizce?
PDF
Kabadi, Punnen: Spanning cactus of a graph: Existence, extension, optimization, and approximation
Clanek studuje vypocetni slozitost hledani kaktusu v grafu.
PDF
Campos, Wakabayashi: On dominating sets of maximal outerplanar graphs
Ukazuje se horni odhad na dominanci maximalniho vnejskove rovinneho grafu,
pricemz tento odhad nakonec vyjde jako optimalni.
PDF
Durocher, He, Munro, Nicholson, Skala: Range majority in constant time and linear space
Clanek popisuje datovou strukturu, ktera umi v O(1) zodpovidat tyto dotazy:
je dano pole, dotaz je na interval, pro ktery se ma vratit prevladajici
prvek v tomto intervalu.
PDF
Thorup: All Structured Programs Have Small Tree Width and Good Register Allocation
Alokace registru pri prekladu urcitych programovacich jazyku je vlastne
ekvivalentni obarveni jisteho specialniho grafu. V clanku se ukazuje, ze pokud
ma graf omezenou stromovou sirku, zvladneme problem rozumne aproximovat.
Specialne, jazyky bez nepodmineneho skoku maji stromovou sirku maximalne 6
a lze tedy rozvrzeni registru 4-aproximovat.
PDF
Cornelsen, Stefano: Track assignment
Jak vyresit problem vlakoveho jizdniho radu pomoci barveni grafu?
Studujeme pro urcite specialni tridy jizdnich radu.
PDF
Raphael Yuster: Maximum Matching in Regular and Almost Regular
Graphs
Ukazuje se algoritmus pro hledani maximalniho parovani v grafech, jejichz minimalni a maximalni stupen se lisi jen o malo. V nekterych pripadech rychlejsi nez zname algoritmy pro obecne grafy. PDF
Lijun Chang, Jeffrey Xu Yu, Lu Qin: Fast Maximal Cliques Enumeration in Sparse Graphs
Cilem je vypsat vsechny kliky v ridkem grafu tak, aby se na kazdou dalsi cekalo jen na polynomialni cas. Polynom zavisi jen na stupnich grafu, nikoliv na jeho velikosti. PDF
Jessica Muntza, Sivaram Narayana, Noah Streibb, Kelly Van Ochtena: Optimal pebbling of graphs
Klasicka hra na grafu. Kdyz sundame dva kaminky z jednoho vrcholu muzeme polozit jeden na souseda. Kolik musime mit na zacatku kaminku (libovolne rozlozenych), chceme-li mit na konci na kazdem vrcholu aspon jeden? Ukazuji se horni a dolni meze pro grafy polomeru d. PDF
Bernhard Haeupler, Siddhartha Sen, and Robert E. Tarjan: Rank-Pairing Heaps
Haldy, ktere jsou stejne rychle jako Fibonacciho, ale na delete potrebuji jen jeden cut. PDF,PDF
Torben Hagerup: An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees
Pro dany strom s vahami na hranach a seznam paru vrcholu toho stromu je treba pro kazdy par urcit nejtezsi hranu na ceste mezi nimi. Linearni algoritmus se znal, tenhle je jednodussi. Lze pouzit k overeni, ze strom je skutecne nejlehci kostrou grafu. Implementace v Dcku. PDF
Yoshiaki Yamaguchi, Kazunori Yamaguchi, Tetsuro Tanaka, and Tomoyuki Kaneko: Infinite Connect-Four Is Solved: Draw
Hra kdy hraci X a O hazi kameny do sloupecku a vyhrava ten kdo ma ctyri v rade (svisle, vodorovne nebo diagonalne). V clanku strategie pro nejake varinaty s nekonecne mnoha sloupci. Kdyz oba hraji optimalne, hra je nekonecna. PDF
Antoni Lozano, Merce Mora, Carlos Seara: Distinguishing trees in linear time
Graf je d-odlisitelny, pokud existuje ocislovani jeho vrcholu pomoci {1, ..., d}, ktere je zachovano jen identitou. Clanek obsahuje linearni algoritmus pro urceni nejmensiho d-odlisujiciho cisla pro lesy. Mozna dost zavisi na predchozich O(n log n) algoritmech. PDF
Saieed Akbari, Vahid Liaghat, Afshin Nikzad: Colorful Paths in Vertex Coloring of Graphs
Ukazuje se, ze v grafu obarvenem delta+1 barvami, existuje pro kazdy vrchol cesta, ktera v nem zacina a obsahuje prave jeden vrchol kazde barvy. PDF
Mikkel Thorup: Undirected Single Source Shortest Path in Linear Time
Prvni, ktery toho dosahuje deterministicky. Preklada, ze vahy jsou prirozena ne moc velka cisla. PDF
Mikkel Thorup: Floats, Integers, and Single Source Shortest Paths
Vylepsuje predchozi i na floaty, vyuziva ho jako podproceduru. PDF
Uriel Feige: On optimal strategies for a hat game on graphs
Hra s klobouky, v niz kazdy hrac sedi ve vrcholu grafu a vidi klobouky sousedu. Vsichni vyhraji, pokud aspon jeden tipne spravne a nikdo netipne spatne. Ukazuji se nejlepsi strategie pro bipartitni grafy a rovinne grafy s trojuhelnikem. PDF
Wesley Pegden: A finite goal set in the plane which is not a Winner
Je dana konecna mnozina bodu v rovine a hraci si stridave berou body roviny. Vyhrava ten ktery prvni ziska kopii zadane mnoziny. Zde mnozina o peti prvcich tak, ze druhy hrac muze vzdy vyhrat. PDF
Mike Paterson, Uri Zwick: Overhang
Skladame cihlicky na sebe, jak daleko pres okraj stolu mohou viset? Zde konstrukce s presahem theta(n^{1/3}), drive se znalo jen theta(log n). PDF
E.R. van Dam, M.A. Fiol: A short proof of the odd-girth theorem
Novy dukaz, ze graf s d+1 vlastnimi cisly a lichym obvodem 2d+1 je vzdalenostne regularni (pocet sousedu u ve vzdalenosti j od v je stejny pro vsechny u a v ve vzdalenosti i). Bude asi tezke rict nejak smysluplne bez referenci. PDF
Jozsef Balogh, Andras Pluhar: The positive minimum degree game on sparse graphs
Maker a Breaker spolu hraji hru: Stridave si vybiraji hrany grafu a Maker vyhraje, pokud hrany ktere si vybral tvori graf s urcitym minimalnim stupnem. V clanku se vylepsuje mez na to, kolik musel mit puvodni graf hran, aby mohl Maker vyhrat. Jednoducha aplikace metody vybijeni (discharging). PDF
Sam Ganzfried: Computing Strong Game-Theoretic Strategies in Jotto
Hra kdy si kazdy hrac mysli tajne slovo a klade druhemu otazky ve forme slova. Odpovedi je pocet pismenek ktera jsou v obou slovech. Resi se jak pocitat strategie pocitacem. PDF
Andras Gyarfas, Gabor N. Sarkozy: Monochromatic path and cycle partitions in hypergraphs
Rozdelovani hranove obarvenych uniformnich hypergrafu na jednobarevne cesty a cykly. Asi bude potreba nahlidnout do referenci a nastudovat nazvoslovi. PDF
S. Akbari, N. Ghareghani, G. B. Khosrovshahi, S. Zare: A note on zero-sum 5-flows in regular graphs
Tok s nulovym souctem je prirazeni nenulovych realnych cisel hranam tak, ze soucet u kazdeho vrcholu je 0. Ukazuje se, ze r-regularni graf (r >= 3, r != 5) ma takovy tok pouzivajic jen cisla {-5, ..., -1, 1, ..., 5}. Samotny dukaz ma asi pul stranky, bude potreba nastudovat reference. PDF
Richard Ehrenborg, Chris M. Skinner: The Blind Bartender's Problem
Na otocnem stole ctyri sklenice, se zavazanyma ocima muzete vzdy obratit nejake dve, ale nekdo mezi tim toci stolem. Lze dosahnout toho, ze vsechny stejne? Zobecneni pro vice sklenic a slozitejsi stoly. Asi docela slozite, mozna se da neco vybrat. PDF
Laurie Kirby And Jeff Paris: Accessible Independence Results For Peano Arithmetic
Zabijeni hydry. Tvrzeni prvniho radu nezavisle na Peanove aritmetice. Asi trochu obtížnější, je potřeba vědet něco z logiky. PDF
Matula, Shiloach, Tarjan: Two linear time algorithms for five-coloring a planar graph
Vi se, ze kazdy rovinny graf je 4 barevny. Zde se ukazuje, jak obarvit rovinny graf 5-i barvami v linearnim case. PDF
Mark K. Goldberg and Malik Magdon-Ismail: Embedding a Forest in a Graph
Kazdy les lze vlozit do kazdeho grafu s dostatkem vrcholu. PDF
Janusz Dybizbanski: Sequences containing no 3-term arithmetic progressions
Jaka je nejdelsi podposloupnost posloupnosti 1, ..., n, ktera neobsahuje aritmetickou podposloupnost delky 3? Odhad s pomoci pocitace pro n <= 122. Velmi kratke. PDF
Joshua Erde, Bruno Golenia, Sylvain Golenia: The closed knight tour problem in higher dimensions
Lze nalezt uzavreny tah konem navstevujici kazde policko ctyr nebo vice dimenzionalni sachovnice prave jednou? Jeden z delsich, ale o to zajimavejsich. PDF
Yang Jiao: On the Sprague-Grundy Values of the F-Wythoff Game
Odebirani sirek ze dvou hromadek - bud z jedne, nebo stejne z obou. Zde navic pri odebirani z obou potreba zachovat celou cast pomeru velikosti. Ukazuji se zajimave vlastnosti o cislech charakterizujicich pozice z nichz jeden ci druhy ma vyherni strategii. PDF
Tamas Matrai: Covering the Edges of a Graph by Three Odd Subgraphs
Kazdy graf se da (hranove) pokryt trojici svych podgrafu, v nichz vsechny stupne jsou liche. PDF
Fan Chung, Ron Graham, Jia Mao, and Andrew Yao: Oblivious and Adaptive Strategies for the Majority and Plurality Problems
Mame n micku obarvenych dvema nebo vice barvami. Kolik porovnani barev je potreba abychom zjistili, jestli je nekterych micku vic nez polovina, nebo kterych je nejvice? PDF
Nathan Linial, Jaikumar Radhakrishnan: Essential covers of the cube by hyperplanes
Kolik polynomu je potreba, abychom pokryli hyperkrychli jejich koreny? PS
David R. Karger, Philip N. Klein, Robert E. Tarjan: A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees PDF
Adam L. Buchsbaum, Haim Kaplan, Anne Rogers, Jeffery R. Westbrook: Linear-Time Pointer-Machine Algorithms for Least Common Ancestors,
MST Verification, and Dominators
Sjednoceni disjunktnich mnozin, radix sort s pointery a jejich spolecne pouziti k reseni vyse uvedenych. PDF
Haim Kaplan, Matthew J. Katz, Gila Morgenstern, and Micha Sharir: Optimal cover of points by disks in a simple polygon
Mame mnohouhelnik a v nem nekolik bodu. Chceme body pokryt kruhy ktere budou zcela v mnohouhelniku. Skoro linearni algoritmus. PDF
Články, které už byly
Lei Wang,Xiaodong Wang,Yingjie Wu, and Daxin Zhu: Complete Solutions for a Combinatorial Puzzle in Linear Time
Hleda se reseni pro nejakou hru dvou hracu s bilymi a cernymi kameny. Najde se kvadraticke reseni. Hra neni popsana v abstraktu, coz je podezrele, ale clanek je docela dlouhy. PDF
Představil: Jan Cejhon
Arkin, Guttman-Beck, Hassin: The (K,k)-capacitated spanning tree problem
Kapacitni kostra grafu je takova kostra, kde velikost podstromu pro kazdy vrchol
v ni je aspon takova jako kapacita prirazena vrcholu.
Clanek ukazuje konstantni aproximacni algoritmus.
PDF
Představil: Ondřej Fiedler
Jiri Matousek, Martin Loebl: Hercules versus Hidden Hydra Helper
Opet boj s hydrou, ale tentokrat se Herkules strida s milovnikem hydry, ktery ji sice seka, ale tak aby prezila co nejdele. Pokud milovnik dela jen jeden sek za kazdy sek Herkula, Herkules muze hydru zabit ``rychle''. Pokud ma milovnik vice seku, bude to trvat ``dlouho''. PDF
Představil: Stanislav Zubal
Fatih Koçan: A nonenumerative algorithm to find the k longest (shortest) paths in a DAG
Predvadi se udajne rychly algoritmus na nalezeni k nejdelsich cest v orientovanem acyklickem grafu. PDF
Představil: Adam Kučera
Yann Disser, Max Klimm, Nicole Megow, and Sebastian Stiller: Packing a Knapsack of Unknown Capacity
Plnime batoh nezname kapacity, to ze se tam neco nevejde se dozvime az kdyz to tam zkusime strcit. Veci nelze vyndavat. Ukazuje se, ze i tak lze zabalit aspon polovinu hodnoty optimalniho sbaleni a lepe to nejde! Dalsi zajimave tezkosti. Delsi. PDF
Představil: David Příhoda
Patrizio Angelini, Thomas Bläsius, and Ignaz Rutter: Testing Mutual Duality of Planar Graphs
Otazka zni, kdyz dostaneme na vstupu dbva rovinne grafy, lze jeden nakreslit tak, ze druhy je izomorfni jeho dualu? Ukazuje se NP-uplnost v obecnem pripade a linearni algoritmus pro 2-souvisle grafy. PDF
Představil: Matyáš Kopp