Teoretický seminář (BI/MI-TS3)

Základní informace

Teoretický seminář si klade za cíl přiblížit studentům současnou vědeckou práci.

V zimním semestru 2014/15 má kód BI-TS3 (případně MI-TS3) a koná se každou středu od 12:45 v místnosti TH:A-1242, tedy na dvanáctém patře budovy A.

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

Seminář v zimním semestru 2014/15 skončil. Těšíme se na setkání s Vámi opět v letním semestru, tentokrát pod kódem BI-TS4, případně MI-TS4.

Minulý program

• Dne 17.12.2014 se pokusil Milan Resch představit článek The cyclical scheduling problem jehož autory jsou Binay Bhattacharya, Soudipta Chakraborty, Ehsan Iranmanesh a Ramesh Krishnamurti.
• Dne 10.12.2014 představil Josef Malík článek The Firing Squad Synchronization Problem on CA with Multiple Updating Cycles jehož autory jsou Luca Manzoni a Hiroshi Umeo.
• Dne 3.12.2014 se seminář nekonal z důvodu nízké účasti publika a probíhajícího dne otevřených dveří.
• Dne 26.11.2014 představil Robin Obůrka článek Random Access to Fibonacci Codes jehož autory jsou Shmuel Tomi Klein a Dana Shapira.
• Dne 19.11.2014 představil Tomáš Pecka článek Theory of átomata jehož autory jsou Janusz Brzozowski a Hellis Tamm.
• Dne 12.11.2014 představil Ondřej Máca článek Constant-time sorting jehož autorem je Michael Brand.
• Dne 5.11.2014 představil Štěpán Plachý článek Capturing the Drunk Robber on a Graph, jehož autory jsou Natasha Komarov a Peter Winkler.
• Dne 29.10.2014 představil Tomáš Campr článek On Fence Patrolling by Mobile Agents, jehož autory jsou Adrian Dumitrescu, Anirban Ghosh a Csaba D. Tóth.
• Dne 22.10.2014 představil Jan Paprota článek Bubblesort, stacksort and their duals, jehož autorem je Luca S. Ferrari.
• Dne 15.10.2014 představil Stanislav Zubal článek On Bichromatic Triangle Game jehož autory jsou Gordana Manić, Daniel M. Martin a Miloš Stojaković.
• Dne 8.10.2014 představil Petr Kaštánek článek Preprocess, Set, Query!, jehož autory jsou Ely Porat a Liam Roditty.
• Dne 1.10.2014 představil Václav Blažej článek The swap matching problem revisited, jehož autory jsou Pritom Ahmed, Costas S. Iliopoulos, A.S.M. Sohidull Islam a M. Sohel Rahman, a k chybám v něm svoje řešení.
• Dne 24.9. se představovaly a rozdělovaly články na tento semestr.

Články

Volné články

• Landon Rabern: A game generalizing Hall’s Theorem
  Dva hraci spolu hraji hru na mnozinovem systemu. Jeden se snazi umoznit existenci systemu ruznych reprezentantu a hraje tak, ze v jedne mnozine zameni libovolne x za nejake y. Ten druhy se mu to snazi znemoznit a muze zamenit x za y a naopak az v t mnozinach, kde x a y jsou ty, ktere pouzil ten druhy v predchozim tahu. Charakterizuje se, kdy prvni vyhraje.
  PDF
  
  
• Shannon L. Fitzpatrick: Edge-critical cops and robber in planar graphs
  Policajt honi zlodeje po neorientovanem grafu. Kazdy se v kazdem kole hybe o jednu hranu a policajt vzdy vi, kde je zlodej. Zkoumaji se rovinne grafy, kde vyhrava zlodej, ale policajt by vyhral, kdyby se pridala nebo ubrala jedna hrana.
  PDF
  
  
• Paweł Prałat: Almost all k-cop-win graphs contain a dominating set of cardinality k
  Policajti honi zlodeje po neorientovanem grafu. Zlodej, nebo libovolny pocet policajtu se v kazdem kole hybe o jednu hranu a policajti vzdy vi, kde je zlodej. Ukazuje se, ze pokud v nahodnem grafu (kazda hrana s psti 1/2) k policajtu chyti zlodeje, skoro jiste se tak stane uz v prvnim tahu. Take se urcuje kolik je grafu na n vrcholech kde vyhraje k policajtu.
  PDF
  
  
• Paul Dorbeca, Gašper Košmrlj, Gabriel Renault: The domination game played on unions of graphs
  Dominator a Prodluzovac hraji hru na grafu: stridave vybiraji vrcholy tak, aby vybrana mnozina dominovala aspon o 1 vrchol vic nez v predchozim tahu. Hra konci, kdyz uz nelze tahnou, tj. mame dominujici mnozinu grafu. Dominator se snazi hru ukoncit co nejdrive, Prodluzovac ji prodluzuje. Otazka je, jak dlouha hra bude. Clanek se snazi urcit delku hry pro disjunktni sjednoceni grafu na zaklade delek pro jednotlive grafy.
  PDF
  
  
• Walter Kern, Xian Qiu: Note on non-uniform bin packing games
  Hraci se snazi spolecne nandat co nejvice veci do pripravenych boxu. Za tim ucelem se sdruzuji do kolic, pokud je to pro vsechny vyhodne. Ukazuje se, ze vzdy existuji pomerne velke vyhodne koalice.
  PDF
  
  
• Yaojun Chena, T.C.E. Cheng, Yunqing Zhang, Guofei Zhou: The planar Ramsey number PR(C₄, K₈)
  Hleda se nejmensi n tak, ze kazdy rovinny graf na n vrcholech bud obsahuje cyklus na 4 vrcholech, nebo jeho obsahuje doplnek kliku na osmi. Ukazuje se, ze je to 23, coz potvrzuje jednu starsi hypotezu pro l=8.
  PDF
  
  
• Timothy Lewis, Charles A. Cusack, Lisa Dion: The complexity of pebbling reachability and solvability in planar and outerplanar graphs
  Mame dany pocty kaminku na jednotlivych vrcholech neorientovaneho grafu. Muzeme z jednoho vrcholu dva kaminky odebrat a dat jeden na souseda. Cil je rozhodnout, zda lze dostat aspon jeden kaminek na zadany vrchol, pripadne zda je to mozne pro vsechny vrcholy. Ukazuje se, ze je to NP-uplne pro rovinne grafy a polynomialni algoritmy pro vnejskove rovinne a rovinne o prumeru nejvyse dva.
  PDF
  
  
• F. Aurenhammera, B. Sub, Y.-F. Xuc, B. Zhu: A note on visibility-constrained Voronoi diagrams
  Stavime Voronoiuv digram, ale v rovinne jsou navic prekazky a zkoumame nejblizsi viditelny bod.
  PDF
  
  
• Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, Arash Rafiey: Finding clubs in graph classes
  s-klub je graf o prumeru nejvyse s. Ukazuje se, jak najit nejvetsi s-club v chordalnich a v grafech bez asteroidalnich (silne propojenych) trojic vrcholu v polynomialnim case. Pro slabe chordalni grafy to lze v polynomialnim case pro licha s, ale je to NP-uplne pro suda.
  PDF
  
  
• Fabrizio Frati, Serge Gaspers, Joachim Gudmundsson, Luke Mathieson: Augmenting Graphs to Minimize the Diameter
  Zmensovani prumeru grafu pridavanim hran. Ukazuje se 4-aproximace pro pripad, ze je potreba pridat malo hran. Tezkost mozno vynechat.
  PDF
  
  
• Yann Disser, Subir Kumar Ghosh, Matúš Mihalák, Peter Widmayer: Mapping a polygon with holes using a compass
  Robot mapuje mistnost se sloupy, ma problem rozlisit steny. Ukazuje se, ze to lze. Mozna dost zavisi na predchozim vysledku.
  PDF
  
  
• Mieczysław Borowiecki, Ewa Drgas-Burchardt, Elżbieta Sidorowicz: A feedback vertex set of 2-degenerate graphs
  Feedback Vertex Set je mnozina vrcholu po jejichz odebrani zbyde z grafu les. Ukazuje se, ze 2-degenerovane grafy maji FVS o velikosti nejvyse 2n/5 a jak takovou FVS v polynomialnim case najit.
  PDF
  
  
• Hervé Baumann, Pierre Fraigniaud, Hovhannes A. Harutyunyan, Rémi de Verclos: The worst case behavior of randomized gossip protocols
  Sireni zpravy po grafu pomoci pravdepodobnostniho algoritmu. Otazka zni, jak dlouho se bude sirit zprava z s do t. Ukazuje se, ze v nekterych scenarich se to spocita snadno, v jinych tezko.
  PDF
  
  
• B. Balamohan, S. Dobrev, P. Flocchini, N. Santoro: Exploring an unknown dangerous graph with a constant number of tokens
  Prohledavame jeskyni s propastmi, muzeme si ve vrcholech nechavat veci, nebo je zase sbirat a prenaset. Ukazuje se, ze na prohledani je potreba aspon 3 veci a aspon Delta+2 jeskynaru, pak uz to jde.
  PDF
  
  
• Arash Ahadi, Amirhossein Mozafari, Alireza Zarei: Touring a sequence of disjoint polygons: Complexity and extension
  Chceme dojit do nekolika disjunktnich polygonu v rovine. Ukazuje se, ze je to NP-tezke, pokud jimi lze prochazet a polynomialni, pokud skrz projit nelze.
  PDF
  
  
• Yasuaki Kobayashi, Hirokazu Maruta, Yusuke Nakae, Hisao Tamaki: A linear edge kernel for two-layer crossing minimization
  Chceme nakreslit graf tak, ze jeho vrcholy budou umisteny na dvou rovnobeznych primkach a nejvyse k hran se bude krizit. Ukazuje se, ze pak lze snadno vyresit vetsinu grafu, krome O(k) hran, z cehoz plyne take rychly exponencialni algoritmus.
  PDF
  
  
• Pavol Hell, Aurosish Mishra: H-coloring degree-bounded (acyclic) digraphs
  Barvi se (trochu specialne) orientovane grafy. Ukazuje se, ze je to NP-tezke, i kdyz maji vstupni grafy omezeny vstupni i vystupni stupen na velmi male cislo.
  PDF
  
  
• Amr Elmasry, Daniel Dahl Juhl, Jyrki Katajainen, Srinivasa Rao Satti: Selection from read-only memory with limited workspace
  Hledame k ty nejmensi prvek posloupnosti, ale mame malo pameti a vstup smime jen cist.
  PDF
  
  
• Jasine Babu, Manu Basavaraju, L. Sunil Chandran, Deepak Rajendraprasad: 2-Connecting outerplanar graphs without blowing up the pathwidth
  Mame rovinny graf, ktery lze nakreslit tak, ze vsechny vrcholy jsou na vnejsi stene a navic je hodne podlouhly (podobny ceste). Mame pridat hrany tak, aby stale sel tak nakreslit, byl podlouhly (i kdyz uz ne tak uzce) a navic nemel artikulace.
  PDF
  
  
• Yong Zhang, Francis Y.L. Chin, Hing-Fung Ting, Xin Han, Chung Keung Poon, Yung H. Tsin, Deshi Ye: Online algorithms for 1-space bounded 2-dimensional bin packing and square packing
  Skladame obdelnikove zasilky do obdelnikovych aut, muzeme je otacet o pi/4. Kdyz se auto naplni musi odjet. Ukazuje se algoritmus, ktery pouzije jen 5.06 vice aut, nez je potreba.
  PDF
  
  
• Yu-An Lin, Sheung-Hung Poon: Non-planar square-orthogonal drawing with few-bend edges
  Kreslime nerovinne grafy s nizkym maximalnim stupnem do mrizky, tak ze kazda hrana ma nejvyse dva, dva, nebo nejvyse tri ohyby. Ukazuje se O(n⁴) algoritmus a NP-ulpnost v pripade, ze nechceme zadne ohyby.
  PDF
  
  
• Peter Damaschke: Sparse solutions of sparse linear systems: Fixed-parameter tractability and an application of complex group testing
  Ukazuje se, ze pro celociselne linearni programovani, kde kazda nerovnice obsahuje jen malo promenych, lze rychle vypsat vsechny typy minimalnich reseni.
  PDF, PDF
  
  
• Paul Horn, Kevin G. Milans, Vojtěch Rödl: Degree Ramsey Numbers of Closed Blowups of Trees
  Ukazuje se jak omezit Ramseovske cislo pro grafy omezeneho stupne pomoci Ramseovskeho cisla pro nafouknute stromy.
  PDF
  
  
• Unnar Th. Bachmann, Magnús M. Halldórsson, Hadas Shachnai: Online selection of intervals and t-intervals
  Prichazeji objednavky na casove intervaly a sjednoceni t intervalu. Kazdou musite bud prijmout nebo odmitnout tak, abyste jich prijali co nejvice. Ukazuje ze kompetitivni algoritmus.
  PDF
  
  
• Stephan Brandt, Janina Müttel, Dieter Rautenbach: The circumference of the square of a connected graph
  Druha mocnina grafu vznikne tak, ze pridame hranu mezi vrcholy se spolecnym sousedem. Ukazuje se, ze druha mocnina souvisleho grafu obsahuje cyklus delky alespon logaritmicke v poctu vrcholu.
  PDF
  
  
• Igor da Fonseca Ramos, Vinícius F. dos Santos, Jayme L. Szwarcfiter: Complexity aspects of the computation of the rank of a graph
  Rekneme, ze mnozina vrcholu v grafu je konvexni, pokud neexistuje vrchol mimo ni, ktery by mel aspon dva sousedy uvnitr. Mnozina je konvexne nezavisla, pokud zadny jeji vrchol nelezi v konvexnim obalu ostatnich. Zkouma se, jak tezke je urcit velikost nejvetsi konvexne nezavisle mnoziny v grafu.
  PDF
  
  
• Jarosław Kutyłowski, Friedhelm Meyer auf der Heide: Optimal strategies for maintaining a chain of relays between an explorer and a base camp
  Sada jednoduchych robotu umoznuje komunikaci mezi zakladnou a pohybujicim se robotem. Analyzuji se strategie, jak udrzovat vzdalenosti mezi roboty na trase omezene.
  PDF
  
  
• Kojiro Kobayashi: The minimum firing time of the generalized firing squad synchronization problem for squares
  Vojaci se maji domluvit, aby vystrelili ve stejnou chvili, komunikovat mohou pouze se sousedy. Ukazuje se, jak nejrychleji se mohou domluvit, pokud jsou organizovani do ctverce o n radach a n zastupech.
  PDF
  
  
• Jamie Simpson: Palindromes in circular words
  Ukazuje se, ze v cyklickem slove delky n muze byt nejvyse 5n/3 ruznych palindromu (slov ktera zni od konce stejne jako od zacatku) a ze to take lze skoro dosahnout.
  PDF
  
  
• Eyal Ackerman, János Pach, Rom Pinchasi, Rados Radoicic, Géza Tóth: A Note on Coloring Line Arrangements
  Barvime primky v rovine tak, aby kazda stena sousedila s primkami aspon dvou ruznych barev. Vylepsuje se predchozi mez na to kolik barev potrebujeme. Vhodne doplnit o dolni odhad.
  PDF
  
  
• Šárka Petříčková: Online Ramsey Theory for Planar Graphs
  Dva hraci spolu hraji hru. Stavec pridava hrany a barvic pridanou hranu obarvi. Graf musi zustat stale rovinny. Cilem stavece je donutit barvice vytvorit jednobarevnou kopii nejakeho grafu G. Byla hypoteza, ze je to mozne prave pro G vnejskove rovinny. Ukazuje se, ze pro ne to mozne je, ale i pro jine.
  PDF
  
  
• Vida Dujmovic, Pat Morin, Adam Sheffer: Crossings in grid drawings
  Kreslime graf do d-dimensionalni mrizky o objemu N. Ukazuji se odhady na to, kolik hran se v takovem grafu musi krizit a take na to, kolik takovych grafu je bez krizeni.
  PDF
  
  
• John Bodeen, Steve Butler, Taekyoung Kim, Xiyuan Sun, Shenzhi Wang: Tiling a strip with triangles
  Mame prouzek trojuhelnikove mrizky o rozmerech 2 x n a dlazdime ho trojuhelniky. Ukazuji se rekurence pro pocty takovych dlazdeni a souvislosti s Fibonacciho posloupnosti a jinymi.
  PDF
  
  
• Bing He: Some identities involving the partial sum of q-binomial coefficients
  q-binomialni koeficient je zalozeny na odlisne definici faktorialu, zavislem na parametru q. Dokazuji se rovnosti pro soucty mocnin castecnych souctu nekolika q-binomialnich koeficientu, ktere zobecnuji ty zname pro normalni binomialni koeficienty.
  PDF
  
  
• Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, Bryan T. Wilkinson: Linear-Space Data Structures for Range Mode Query in Arrays
  Mod multimnoziny je prvek, ktery se vyskytuje nejcasteji. Ukolem je pro zadane pole pripravit strukturu, ktera bude pro zadane indexy i a j urcovat mod posloupnosti prvku mezi i a j. Ukazuje se struktura linearni velikosti, ktera odpovida rychleji nez predchozi zname.
  PDF
  
  
• Philip Bille, Inge Li Gortz, Hjalte Wedel Vildhoj, Soren Vind: String Indexing for Patterns with Wildcards
  Vytvari se index pro retezec, ktery rychle urci seznam vyskytu nejakeho vzorku, ktery muze byt tvoreny danym poctem pismen a danym poctem zastupnych znaku. Ukazuji se dve reseni, jedno s mensimi pametovymi naroky, druhe rychlejsi a nakonec moznost si mezi temito dvema plynule vybrat kompromis.
  PDF
  
  
• Michael T. Goodrich: Spin-the-Bottle Sort and Annealing Sort: Oblivious Sorting via Round-Robin Random Comparisons
  Zkoumaji se dva tridici algoritmy zalozene na porovnavani nahodne vybranych prvku, lisici se zpusobem jejich vyberu. Vyhodou je moznost vyuziti v pripade prace s citlivymi udaji pri ochrane soukromi. Ukazuje se, ze zatimco prvni pracuje hure nez kvadraticky, druhy obvykle v n log n.
  PDF
  
  
• Funda Ergun, Hossein Jowhari: On The Monotonicity Of A Data Stream
  Na vstupu je proud cisel (tj. kazde vidime jen jednou) a mame velmi malo pameti vzhledem k poctu cisel v tom proudu. Ukolem je urcit jak daleko je vstupni posloupnost od monotonni a delku nejdelsi rostouci podposloupnosti. Ukazuji se algoritmy a dolni odhady na potrebne mnozstvi pameti pro dosazeni urcite presnosti.
  PDF
  
  
• Vida Dujmović, Daniel J. Harvey, Gwenaël Joret, Bruce Reed, and David R. Wood: A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
  Novy jeste rychlejsi algoritmus pro nalezeni minoru (neco jako podgraf) v hustem grafu. Asi potreba doplnit uvodem do toho, co je to minor.
  PDF PDF
  
  
• Vladimir I. Benediktovich: On rational approximation of a geometric graph
  Geometrický graf je nakreslení grafu do roviny pomocí úseček bez křížení. Geometrický graf je racionální, pokud jsou všechny délky úseček racionální čísla. Otázka zní, u jakých grafů lze perturbovat pozice vrcholů tak, aby byl graf racionální a aby všechny vrcholy měly zároveň racionální souřadnice. Článek dává kladnou odpověď pro jistou třídu grafů.
  PDF
  
  
• Heidi Gebauer: On the construction of 3-chromatic hypergraphs with few edges
  Slavný problém v kombinatorice se ptá, kolik minimálně musí být číslo m(N) tak, aby šlo zkonstruovat hypergraf na N vrcholech s m(N) hranami, který je 3-barevný. V článku se ukazuje nový horní odhad na číslo m(N).
  PDF
  
  
• Weigen Yan: On the number of spanning trees of some irregular line graphs
  Pro graf G dává smysl počítat, kolik různých koster obsahuje, a pro speciální třídy grafů existují i explicitní vzorce pro tyto počty. Článek studuje počet koster line-grafu od grafu G, který není regulární. (Line-graf vznikne prohozením pojmů vrchol a hrana.)
  PDF
  
  
• Leah Epstein, Michal Feldman, Tami Tamir, Lukasz Witkowski, Marcin Witkowski: Approximate strong equilibria in job scheduling games with two uniformly related machines
  Problém rozvrhování úkolů ke zpracování na paralelně běžící stroje má mnoho variant a je studován v různých kontextech. V článku se uvažuje konkurenční prostředí, kdy jednotlivé úkoly platí za to, aby byly zpracovány, nicméně cena se odvíjí od nabídky a poptávky. Každý úkol chce být zpracován, ale zároveň na tom chce co nejvíc ušetřit. Ukazují se vlastnosti ekvilibrií této hry.
  PDF
  
  
• Vladimir G. Deineko, Gerhard J. Woeginger: Two hardness results for core stability in hedonic coalition formation games
  Téma z klasické teorie her: hráči se stávají členy koalic, za což jsou nějak odměňováni. Odměna hráče se odvíjí pouze od toho, s kým jsou v koalici, a nezávisí na hráčích mimo koalici. Otázka zní, zda je daný stav této hry stabilní, tedy zda žádný hráč nechce změnit koalici. Článek ukazuje NP-úplnost této otázky.
  PDF
  
  
• Daniel W. Cranston, William B. Kinnersley, Suil O, Douglas B. West: Game matching number of graphs
  Dva hráči vybírají hrany grafu, aby průběžně tvořily párování. Jeden hráč se snaží vyrobit co největší párování, druhý co nejmenší. Jak hra dopadne? Článek dává odpověď.
  PDF
  
  
• Toufik Mansour, Mark Shattuck: A combinatorial approach to a general two-term recurrence
  Článek studuje metody řešení jistého speciálního typu lineárních dvojitě rekurzivně definovaných posloupností.
  PDF
  
  
• R.D. Malikiosis, M. Matolcsi, I.Z. Ruzsa: A note on the pyjama problem
  Uvažme sadu vertikálních proužků v rovině, kde střed proužků leží na celočíselných bodech osy x. Otázka zní, kolik musím sjednotit rotací, abych pokryl těmito množinami celou rovinu. Pro dostatečně široké proužky jich stačí konečně mnoho, pro příliš úzké už je jich třeba nekonečně.
  PDF
  
  
• Shi-Mei Ma: Some combinatorial arrays generated by context-free grammars
  Článek ukazuje, že některé kombinatorické posloupnosti, například Catalanův trojúhelník, lze vygenerovat bezkontextovou gramatikou.
  PDF
  
  
• Máté Matolcsi, Imre Z. Ruzsa: Sets with no solutions to x + y = 3z
  Jak velká je množina A\subset [0,1], jejíž prvky řeší rovnici x+y=3z? Bude třeba nastudovat pojmy okolo Lebesgueových měr.
  PDF
  
  
• Ming Liu, Feifeng Zheng, Shijin Wang, Yinfeng Xu: Approximation algorithms for parallel machine scheduling with linear deterioration
  Článek studuje několik metod, jak rozvrhovat úlohy na paralelní počítače, aby se minimalizoval čas zpracování všech úloh. U metod analyzuje jejich aproximační faktor.
  PDF
  
  
• Takuya Umesato, Toshiki Saitoh, Ryuhei Uehara, Hiro Ito, Yoshio Okamoto: The complexity of the stamp folding problem
  Něco pro milovníky origami: chceme ohýbat papír tak, aby počet vrstev papíru mezi každou dvojicí ohýbaných částí je minimální. Studuje se výpočetní složitost problému.
  PDF
  
  
• Pär Kurlberg, Jeffrey C. Lagarias, Carl Pomerance: On sets of integers which are both sum-free and product-free
  Množina přirozených čísel M je součtuprostá a násobkuprostá, pokud pro každé dvě x,y \in M neleží x+y a x.y v M. Článek studuje maximální hustotu takových množin.
  PDF
  
  
• John M. Freeman, Tomas Schonbeki, Wandi Wei: On the tennis ball problem
  Dostali jsme dva míčky, z nich jeden vybereme a odhodíme. Dostaneme další dva, máme tedy tři, z nichž jeden opět odhodíme. A tak dále. Otázka je, kolik je všech tímto způsobem vyrobitelných posloupností odhozených míčků. Článek studuje zobecnění tohoto problému.
  PDF
  
  
• András Csernenszky, Ryan R. Martin, András Pluhár: On the complexity of chooser-picker positional games
  Dva hráči zabírají střídavě prvky množiny, nad kterou jsou definovány vyhrávající podmnožiny kdo obsadil nějakou z nich, vyhrál. Uvažme variantu, kdy jeden hráč vybere dva prvky a druhý hráč určí, který prvek z těch dvou komu připadne. Článek ukazuje výpočetní složitost problému určit, kdo danou hru vyhraje.
  PDF
  
  
• Fraser Stewart: Pirates and treasure
  Na grafu jsou dvě konkurenční party pirátu, kteří na střídačku chodí po vrcholech a sbírají na nich poklady. Otázka je, kdo v této hře je schopen nasbírat větší poklad. Článek studuje strukturu této hry a její výpočetní složitost.
  PDF
  
  
• Herbert Fleischner: Uniquely Hamiltonian Graphs of Minimum Degree 4
  Článek konstruuje nekonečnou rodinu grafů s jistými požadavky na stupně vrcholů, které obsahují právě jednu hamiltonovskou kružnici.
  PDF
  
  
• Luke Postle: Pebbling Graphs of Fixed Diameter
  Pebbling na grafu je solitér, kdy jsou na vrcholech rozmístěny kamínky a tah spočívá v tom, že se z vrcholu vezmou dva, jeden zahodí a druhý přemístí na nějaký sousední vrchol. Otázka je, kolik minimálně potřebuje kamínku, aby pro libovolné počáteční rozmístění šlo dopravit kamínek do nějakého cílového vrcholu. Článek podáva nový horní odhad.
  PDF
  
  
• Pierre Aboulker: Excluding 4-Wheels
  4-kolo je kružnice plus vrchol napojený na kružnici čtyřmi hranami. Článek ukazuje, že každý graf neobsahujíci 4-kolo jako podgraf je vrcholově 4-obarvitelný.
  PDF
  
  
• Hongliang Lu, David G. L. Wang, and Qinglin Yu: On the Existence of General Factors in Regular Graphs
  Ukazuje se za jakych podminek ma nebo nema regularni graf faktor se stupni z dane mnoziny.
  PDF
  
  
• Graham Brightwell and Mareike Massow: Diametral Pairs of Linear Extensions
  Kolik maximalne prvku muzou radit ruzne dve linearni rozsireni daneho castecneho usporadani. Ukazuje se NP-uplnost a vyvraci starsi domnenka na to jak takova rozsireni vypadaji. Delsi, asi by nebyl problem neco vybrat.
  PDF
  
  
• Sariel Har-Peled and Bernard Lidicky: Peeling the Grid
  Rozebirame mrizku n x n tak, ze vzdy obereme vrcholy konvexniho obalu totho, co nam zbyva. Ukazuje se, ze to jde prekvapive rychle. Kratsi.
  PDF
  
  
• Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Tom Leighton: Basic Network Creation Games
  Mame graf a kazdy vrchol se ho snazi vylepsit tim, ze vzdy prepoji jednu hranu tak, aby zlepsil svoji vzdalenost od ostatnich. Jak dobre to v globalu dopadne, az se to ustali? Ukazuji se horni a dolni meze.
  PDF
  
  
• Balázs Keszegh, János Pach, Dömötör Pálvölgyi: Drawing planar graphs of bounded degree with few slopes
  Kresli se graf do roviny, tak aby hrany pouzivali co nejmene ruznych uhlu (smernic). Ukazuje se, ze pocet potrebnych uhlu lze omezit nejvyssim stupnem grafu a pokud povolime na kazde hrane jeden zlom, vyjde i hezka mez.
  PDF
  
  
• Sam Buss,Michael Soltys: Unshuffling a square is NP-hard
  Retezec je mixem dvou retezcu, pokud vznikne prokladanim pismenek z tech dvou retezcu tak, ze zustanou v puvodnim poradi (jako pri michani karet). Ukazuje, ze je NP-tezke rozhodnout, zda dany string vznikl smichanim nejakeho retezce sama se sebou.
  PDF
  
  
• Telikepalli Kavitha: Dynamic Matrix Rank with Partial Lookahead
  Jak si prubezne udrzovat hodnost matice ktera se meni. Dosahuji amortizovane O(n^{w-1}) na zmenu, ale potrebuji znat co se bude priste menit (neni potreba vedet jak).
  PDF
  
  
• Dominik Gall, Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, Hanjo Täubig: A Note on the Parallel Runtime of Self-Stabilizing Graph Linearization
  Zkouma se jak narovnat graf na primku pomoci jednoduchych lokalnich ooperaci iniciovanych primo vrcholy. Netrivialne se analyzuje nekolik scenaru a algoritmu.
  PDF
  
  
• Helmut Alt, Esther M. Arkin, Alon Efrat, George Hart, Ferran Hurtado, Irina Kostitsyna, Alexander Kröller, Joseph S. B. Mitchell, Valentin Polishchuk: Scandinavian Thins on Top of Cake: New and Improved Algorithms for Stacking and Packing
  Jak velky kufr potrebujeme, abychom do nej mohli nandat vsechny zadane veci (pokud je smime/nesmime otacet apod.). NP-tezkost, trocha geometrie, PTAS, ilustrovane.
  PDF
  
  
• Stefan Dobrev, Lata Narayanan, Jaroslav Opatrny: Optimal Sensor Networks for Area Monitoring Using Rotating and Beam Sensors
  Monitorovani prostoru pomoci statickych a otocnych pohybovych cidel. Jak sestavit sit s nejmensim poctem cidel? Ilustrovano.
  PDF
  
  
• Timothy M. Chan, Stephane Durocher, Kasper Green Larsen, Jason Morrison, Bryan T. Wilkinson: Linear-Space Data Structures for Range Mode Query in Arrays
  Je zadano pole a stavi se struktura, ktera umi efektivne odpovidat na dotazy typu: Ktera hodnota se vyskytuje mezi indexy i a j nejcasteji? Mozna bude potreba nacist i neco z odkazovane literatury, nejspis by stacila ta staticka struktura.
  PDF
  
  
• Johan M. M. van Rooij, Marcel E. van Kooten Niekerk, Hans L. Bodlaender: Partition Into Triangles on Bounded Degree Graphs
  Cilem je rozdelit graf na vrcholove disjunktni trojuhelniky. Ukzauje se, ze je to linerane resitelne pro grafy stupne 3 a NP-uplne pro grafy stupne 4. Dale se ukazuje rychly exponencialni algoritmus pro grafy stupne 4, ten je asi nejzajimavejsi. Delsi.
  PDF
  
  
• Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk: Solving the 2-Disjoint Connected Subgraphs Problem Faster than 2^n
  Mame dany dve mnoziny vrcholu a hledame rozdeleni vsech vrcholu grafu na dve mnoziny tak, aby byly souvisle a kazda z nich obsahovala jednu ze zadanych mnozin. V clanku je 1.93^n algoritmus pro tenhle problem, prvni ktery prolomil 2^n. Dlasi vysledky mozno vynechat.
  PDF
  
  
• Jean-François Couturier, Petr A. Golovach, Dieter Kratsch, Daniël Paulusma: List Coloring in the Absence of a Linear Forest
  Ukazuje se, ze rozhodnout, zda lze graf obarvit k barvami lze v polynomialnim case pro grafy, ktere neobsahuji urcite lesy jako indukovany podgraf.
  PDF
  
  
• Anil Maheshwari, Jörg-Rüdiger Sack, Kaveh Shahbaz, Hamid Zarrabi-Zadeh: Improved Algorithms for Partial Curve Matching
  Mame zadanou malou a velkou krivku a otazka zni, jestli ta vetsi obsahuje cast podobnou te mensi. Ukazuje se O(nm) algoritmus pomoci zajimave datove struktury, kde n a m jsou pocty segmentu v tech krivkach.
  PDF
  
  
• Romeo Rizzi, David Cariolaro: Polynomial Time Complexity of Edge Colouring Graphs with Bounded Colour Classes
  Barveni hran grafu minimalnim poctem barev tak, ze (dve sousedni hrany nejsou obarveny stejnou barvou a) kazda barva je pouzita pouze nekolikrat. Polynomialni algoritmus, kratsi, ale spoleha na starsi algoritmy, ktere by asi bylo dobre nastudovat.
  PDF
  
  
• Keren Cohen, Raphael Yuster: On Minimum Witnesses for Boolean Matrix Multiplication
  Matice svedku pri nasobeni booleovskych matic je matice indexu, ktere dokazuji, ze to prislusne policko ma byt jedna. Ukazuji se rychle algoritmy pro vypocet takove matice svedku.
  PDF
  
  
• Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Charis Papadopoulos, Yngve Villanger: Enumerating Minimal Subset Feedback Vertex Sets
  Hleda se mnozina vrcholu grafu, ktera prerusi vsechny cykly v nejake dane podmozine vrcholu. Ukazuje se, jak najit vsechny takove mnoziny v case 1.8^n. K analyze se vyuziva velmi jednoducha Measure and Conquer.
  PDF
  
  
• Giovanni Viglietta: Lemmings is PSPACE-complete
  Ukzauje se, ze znama hra Lemmings, je (za urcitych podminek) PSPACE-uplna.
  PDF
  
  
• Arash Asadpour, Uriel Feige, Amin Saberi: Santa Claus Meets Hypergraph Matchings
  Santa Claus rozdeluje darecky ktere maji ruznou cenu pro ruzne deti a snazi se to udelat tak, aby vsechny deti dostali co nejvic. Ukazuje se vylepseny approximacni algoritmus, zalozeny na LP a lokalnim vyhledavani. Prevdepodobne narocne, i kdyz nijak dlouhe.
  PDF
  
  
• 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
  
  
• 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
  
  
• 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
  
  
• M. Reza Khani, Mohammad R. Salavatipour: Improved Approximation Algorithms for the Min-max Tree Cover and Bounded Tree Cover Problems
  Pokryvame vrcholy grafu podstromama grafu, bud mame dany pocet a snazime se minimalizovat nejvetsi, nebo mame danou maximalni velikost a snazime se minimalizovat pocet. Ukazuji se approximace.
  PDF
  
  
• Elliot Anshelevich, Bugra Caskurlu, Ameya Hate: Strategic Multiway Cut and Multicut Games
  Zkouma se hra, ve ktere se vrcholy grafy snazi odrezat od nejake casti grafu. Porovnavaji se equilibria s centralnimi rozhodnutimi a ukazuje se, ze pro nektere scenare mohou byt dokonce stejne dobra. Delsi.
  PDF
  
  

Zamluvené články

• Binay Bhattacharya, Soudipta Chakraborty, Ehsan Iranmanesh, Ramesh Krishnamurti: The cyclical scheduling problem
  Planovani smen pro delniky v cyklickem provozu. Ukazuje se novy rychlejsi algoritmus, ktery neni zalozeny na tocich.
  PDF
  Zamluveno pro: Milan Resch
  
  

Články, které už byly

• Ely Porat, Liam Roditty: Preprocess, Set, Query!
  Jak si pripravit graf tak, abych byl schopen priblizne odpovidat na dotazy na vzdalenost rychleji nez linearne.
  PDF
  Představil: Petr Kaštánek
  
  
• Pritom Ahmed, Costas S. Iliopoulos, A.S.M. Sohidull Islam, M. Sohel Rahman: The swap matching problem revisited
  Hledani vzorku v textu s otacenim. Ukazuje se novy model zalozeny na grafech, ktery umoznuje dosahnout za jistych okolnosti linearni algoritmus. Podezrele mnoho kodu a malo dukazu.
  PDF
  Představil: Václav Blažej
  
  
• Gordana Manić, Daniel M. Martin, Miloš Stojaković: On Bichromatic Triangle Game
  Jsou dany body v rovine a cerveny a modry hrac se stridaji v pridavani usecek spojujicich dva ze zadanych bodu. Usecky se nesmi krizit. Ten, kdo prvni vytvori svuj trojuhelnik, vyhrava. Ukazuje se, ze pokud body jsou v konvexni poloze (nebo az na jeden), pak kazdy muze uhrat remizu.
  PDF
  Představil: Stanislav Zubal
  
  
• Luca S. Ferrari: Bubblesort, stacksort and their duals
  Uvazujeme bubblesort a trideni pomoci zasobniku a jejich varianty kdy jdeme zprava doleva. Zkouma se, jak spolu jednotlive operace komutuji. Take se ukazuje, ze permutace, ktere lze setridit na dany pocet iteraci techto algoritmu lze charakterizovat pomoci zakazanych podpermutaci.
  PDF
  Představil: Jan Paprota
  
  
• Adrian Dumitrescu, Anirban Ghosh, Csaba D. Tóth: On Fence Patrolling by Mobile Agents
  Sada robotu o ruznych maximalnich rychlostech ma hlidat kruhovy plot tak, aby zadne misto nezustalo dlouho bez dozoru. Zkoumaji se algoritmy pro tvorbu casoveho rozvrhu pro jednotlive roboty.
  PDF
  Představil: Tomáš Campr
  
  
• Michael Brand: Constant-time sorting
  Tridi se na RAMu s dosti omezenou instrukcni sadou.
  PDF
  Představil: Ondřej Máca
  
  
• Janusz Brzozowski, Hellis Tamm: Theory of átomata
  Definuje se vyznacny nedeterministicky konecny automat pro regularni jazyk zalozeny na "atomech" tohoto jazyka a zkoumaji se jeho vlastnosti.
  PDF
  Představil: Tomáš Pecka
  
  
• Natasha Komarov, Peter Winkler: Capturing the Drunk Robber on a Graph
  Policajtka se snazi chytit zlodeje, ktery se pohybuje po grafu nahodne. Jak dlouho to bude ve stredni hodnote trvat?
  PDF
  Představil: Štěpán Plachý
  
  
• Shmuel Tomi Klein, Dana Shapira: Random Access to Fibonacci Codes
  Pouziti vlnovyuch stromu k primemu pristupu k souboru zkomprimovanemu pomoci Fibonacciho kodu.
  PDF
  Představil: Robin Obůrka
  
  
• Luca Manzoni, Hiroshi Umeo: The Firing Squad Synchronization Problem on CA with Multiple Updating Cycles
  Mohou se vojaci domluvit, aby vystrelili ve stejnou chvili, pokud ani nejdou spolecnym krokem?
  PDF
  Představil: Josef Malík