Teoretický seminář si klade za cíl přiblížit studentům současnou vědeckou práci.
V letním semestru 2015/16 měl kód MI-TS2 (případně BI-TS2) a konal se vždy v místnosti TH:A-1242, tedy na dvanáctém patře budovy A, a to každou středu od 14:30 a několikrát také ve čtvrtek od 12:45.
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 letním semestru 2015/16 skončil.
Těšíme se na setkání v zimním semestru 2016/17, tentokrát pod kódy BI-TS3 a MI-TS3.
Nezapomeňte se také přihlásit na konferenci STIGMA.
Minulý program
Dne 18.5.2016 představí Jiří Stránský článek Quad-kd trees: A general framework for kd trees and quad trees jehož autory jsou Nikolett Bereczky, Amalia Duch, Krisztián Németh a Salvador Roura.
Dne 11.5.2016 (rektorský den) představil Alexander Bublik článek The Robber Locating game jehož autory jsou John Haslegrave, Richard A.B. Johnson a Sebastian Koch.
Dne 4.5.2016 představil Jan Cejhon článek Another exploration problem jehož autory jsou Takayasu Kuwata a Hiroshi Maehara.
Dne 27.4.2016 představil Bogoljub Jakovcheski článek Locating a backtracking robber on a tree jehož autorkou je Suzanne Seager.
Dne 20.4.2016 představila Ksenia Shakurova článek On obstacle numbers jehož autory jsou Vida Dujmovic a Pat Morin.
Dne 13.4.2016 představila Evgeniya Nenenko článek Fast Rendezvous with Advice jehož autory jsou Avery Miller a Andrzej Pelc.
Dne 6.4.2016 představil Peter Mitura článek A 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves jehož autory jsou Roberto Solis-Oba, Paul Bonsma a Stefanie Lowski.
Dne 30.3.2016 představil Tomáš Pecka článek From Regular Tree Expression to Position Tree Automaton jehož autory jsou Eric Laugerotte, Nadia Ouali Sebti a Djelloul Ziadi.
Dne 23.3.2016 představil Jakub Puchýř článek Hollow Heaps jehož autory jsou Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan a Uri Zwick.
Dne 16.3.2016 představil Štěpán Plachý článek Linear-Space Data Structures for Range Minority Query in Arrays jehož autory jsou Timothy M. Chan, Stephane Durocher, Matthew Skala a Bryan T. Wilkinson.
Dne 10.3.2016 představil Radovan Červený článek The firefighter problem on graph classes jehož autory jsou Fedor V. Fomin, Pinar Heggernes a Erik Jan van Leeuwen.
Dne 9.3.2016 představil Miroslav Hrončok článek Tiling a strip with triangles jehož autory jsou John Bodeen, Steve Butler, Taekyoung Kim, Xiyuan Sun a Shenzhi Wang.
Dne 2.3.2016 představil Václav Blažej článek Using swaps and deletes to make strings match jehož autorem je Daniel Meister.
Dne 24.2.2016 se představovaly a rozdělovaly články.
Neil A. McKay, Rebecca Milley, Richard J. Nowakowski: Misère-play Hackenbush Sprigs
Hackenbush je známá kombinatorická hra, kde je dán hranově obarvený
graf připojený nějak k podložce, který dva hráči na střídačku
"osekávají". V této verzi se studuje jistý speciální tvar herních grafů
s tzv. misere pravidly, neboli kdo nemůže táhnout, vyhrál.
Přehledová znalost teorie kombinatorických her je výhodou. PDF
Lars Arge,Mikkel Thorup: RAM-Efficient External Memory Sorting
Zkoumaji se tridici algoritmy pro externi pamet jak z pohledu poctu vstupnevystupnich operaci, tak z pohledu optimalniho vyuziti vnitrni pameti. Ukazuje se, ze MergeSort z tohoto pohledu neni idelani a ktery algoritmus je. PDF
Philip Bille, Patrick Hagge Cording, Inge Li G?rtz: Compressed Subsequence Matching and Packed Tree Coloring
Hledame vzorek v retezci, ale oba jsou zadany prostrednictvim gramatiky, ktera je generuje. Autori ukazuji novy algoritmus zalozeny na nove datove strukture, ktery ma mensi pametove naroky a, pokud je vyskytu malo, je i rychlejsi. PDF
Saverio Caminiti, Irene Finocchi, Emanuele G. Fusco, Francesco Silvestr: Resilient Dynamic Programming
Predstavme si, ze v pocitaci je skryt zloduch, ktery muze zpusobit zmenu obsahu pameti v tu nejnevhodnejsi chvili a to nekolikrat behem vypoctu. V clanku se ukazuje, jak upravit zname algoritmy zalozene na dynamickem programovani tak, aby vysledek byl s velkou pravdepodobnosti spravny a asymptoticky cas zustal nezmenen. PDF
Michael A. Bekos, Thomas C. van Dijk, Martin Fink, Philipp Kindermann, Stephen Kobourov, Sergey Pupyrev, Joachim Spoerhase, Alexander Wolff: Improved Approximation Algorithms for Box Contact
Representations
Je dan graf a kazdemu vrcholu je prirazen obdelnicek danych rozmeru. Cilem je rozmistit obdelniky v rovinne tak, aby se dotykali prave ty obdelniky, mezi jejimiz vrcholy je hrana. Ukazuje se O(1)-approximace poctu realizovatelnych hran pro obecne a pro nektere specialni rovinne grafy a dale, ze problem nelze aproximovat s libovolnou presnosti. PDF
Pu Gao: On the geometric Ramsey numbers of trees
Vezmeme body v rovine v obecne poloze a obarvime usecky jimi urcene pomoci dvou barev. Pro zadany vnejskove rovinny graf a strom se ptame, kolik bodu muselo na zacatku byt, abychom pro kazde obarveni nasli bud ten vnejskove rovinny graf v prvni barve, nebo ten strom v te druhe. Ukazuji se presne hodnoty, pokud ten vnejskove rovinny graf je Hamiltonovsky a ten strom je bud housenka, nebo ma jen dva vnitrni vrcholy. PDF
Kazuya Haraguchi: On a generalization of "Eight Blocks to Madness" puzzle
Je k dispozici sada kostek velikosti jedna, jejichz kazda stena je obarvena jinou ze sesti barev. Cilem je vybrat osm kostek a sestavit z nich kostku o hrane dva tak, ze kazda jeji stena je obarvena jednou barvou a barvy ruznych sten jsou ruzne. Je 30 zpusobu jak by reseni mohlo vzniknout. Pro kazdou podmnozinu tech zpusobu se konstruuje vstup ktery umozni presne ty. Konstruuji se co nejmensi vstupy resitelne vsemi zpusoby a co nejvetsi neresitelne vstupy. PDF
Mikio Kano, Zheng Yan: Spanning trees with bounded degrees and leaves
Hledame kostru, ktera ma maly pocet listu a zaroven male stupne vnitrnich vrcholu (extremnim pripadem je Hamiltonovska cesta). Ukazuje se, ze takova kostra existuje vzdy, kdyz je splnena urcita podminka na velikost nezavisle mnoziny grafu. PDF
Nicolás Sanhueza-Matamala: Stability and Ramsey numbers for cycles and wheels
Zkouma se, jak vypada obarveni uplneho grafu cervenou a modrou barvou, v nemz se nevyskytuje ani cervena kruznice na n vrcholech, ani modre koleso na m vrcholech. Pro jake velikosti puvodniho grafu takova obarveni vubec existuji? PDF
Sleszynska-Nowak: Clique number of the square of a line graph
Článek ukazuje odhad na klikovost hranového grafu grafu G a na jeho fractional strong chromatic index.
PDF
Bresar, Henning, Rall: Total dominating sequences in graphs
Mnozina vrcholu grafu je totalne dominujici, pokud v ni kazdy vrchol (vcetne tech, ktere v ni sami jsou) ma souseda. Snazime se postavit co nejvetsi totalne dominujici mnozinu, ve ktere vsak zadny vrchol neni zbytecny. Lepe receno vrcholy pridavame postupne a vzdy chceme, aby byl nekdo nove dominovan. Charakterizuji se grafy u kterych lze vzit vsechny vrcholy do takove mnoziny a takove, u kterych nelze vic nez dva. Ukazuje se dolni mez pro (nektere) stromy a ktere stromy jsou extrem a dalsi, napr., ze je to NP-uplne. PDF
Queiroz, Garnero, Ochem: On interval representations of graphs
Studuje se otázka reprezentace rovinných grafů pomocí průnikového grafu systému intervalů.
Ukazuje se velikost minimální reprezentace pro speciální rovinné grafy a obtížnost rozpoznávání.
PDF
Brimkov, Hicks: Memory efficient algorithms for cactus graphs and block graphs
Pro třídu kaktusových a blokových grafů se ukazuje, jak realizovat nejběžnější
grafové algoritmy (jako třeba nejkratší cesta) v konstantní paměti.
PDF
Holzer, Jakobi: Boundary sets of regular and context-free languages
Zavádí se pojem tzv. hranice regulárních a bezkontextových jazyků.
Článek studujte vlastnosti této hranice a otázky okolo jejího rozpoznávání, rozhodnutí
zda je konečná a další věci.
PDF
Demaine a spol.: Linear-time algorithm for sliding tokens on trees
Na nezávisle množině v grafu leží žetony a je třeba je všechny jedním tahem přesouvat na nějakou
jinou nezávislou množinu. Nalezení posloupnosti tahů je těžký problém a článek to
řeší v polynomiálním čase pro stromy.
PDF
Enright, Stewart: Games on interval and permutation graph representations
Dva protihráči staví reprezentaci průnikového grafu. Článek ukazuje, že rozhodnout vítěze
je pro některé třídy grafů PSPACE-těžký problém a pro stromy je to polynomiální.
PDF
Miller, Pelc: Fast rendezvous with advice
Na grafu se mají navzájem najít dva roboti.
Jaké je minimální množství informace, která se robotům poradí, aby se našli v optimálním čase?
PDF
Chak, Freivalds, Stephan, Yik: On block pumpable languages
Článek rozvádí pojem tzv. block pumping vlastnosti jazyků. Pro regulární
jazyky už byl prozkoumán. Při dalším rozšíření tohoto pojmu dostáváme
novou třídu jazyků, kterou článek studuje.
PDF
Kratsch, Le: Algorithms solving the Matching Cut problem
Cílem je rozhodnout, zda daný graf obsahuje hranový řez, který je zároveň párování.
Je to NP-úplné, takže článek ukazuje alespoň algoritmus v čase O(1.4143^n).
PDF
Kucherov, Salikhov, Tsur: Approximate string matching using a bidirectional index
Řeší se problém matchování stringů, kde je povolen určitý počet chyb.
Článek studuje matchovací algoritmy na tento problém postavené na principu obousměrného indexu.
PDF
Grippo, Matamala, Safe, Stein: Convex p-partitions of bipartite graphs
Množina vrcholů je konvexní, když žádná nejkratší cesta mezi jejími dvěma vrcholy z ní nevyběhne.
Ukazuje se polynomiální algoritmus na rozdělení bipartitního grafu na konvexní množiny.
PDF
Meyer: Generalized Pete's Pike is PSPACE-complete
Ukazuje se PSPACE-úplnost logické hry Pete's Pike.
PDF
Bhattacharya, Nandy, Roy: Space-efficient algorithm for computing a centerpoint of a set of points in R2
Cílem je spočítat střed z množiny bodů. Článek ukazuje jak to udělat s velmi malou pamětí.
PDF
Schmid: Computing equality-free and repetitive string factorisations
Článek ukazuje, že rozřezat string na jistý speciální systém souvislých úseků je NP-úplný problém,
a studuje nějaké další algoritmické aspekty.
PDF
Su, Lin, Tee : Broadcasting in weighted trees under the postal model
Studuje se model vysílání informace po váženém stromu.
Hlavní problém je nalezení centra vysílání minimalizující čas.
Článek ukazuje lineární algoritmus.
PDF
Dvorak, Sereni, Volec: Fractional coloring of triangle-free planar graphs
Zlomkové barvení je známé zobecnění barevnosti.
Článek ukazuje horní odhad pro rovinné grafy bez trojúhelníku.
PDF
Golowich, Rolnich: Acyclic Subgraphs of Planar Digraphs
Pro podtřídu rovinných orientovaných grafů se ukazuje, že obsahují velkou
acyklickou podmnožinu.
PDF
Delcourt, Ferber: On a Conjecture of Thomassen
Je pravda, že existuje funkce f(k) tak, že každý f(k)-souvislý graf
je pokryt bipartitním k-souvislým podgrafem?
V článku se ukazuje, že to platí až na faktor velikost log n.
PDF
Macajova, Raspaud, Skoviera: The chromatic number of a signed graph
Článek studuje jisté rozšíření problému vrcholového barvení, tzv. signed coloring.
Ukazují se základní vlastnosti, signed barevnost rovinných grafů a rozšíření
známé Brooksovy věty.
PDF
Grosu: A New Lower Bound for the Towers of Hanoi Problem
Hanojské věže zobecněné na více než 3 tyčky, kde otázka je minimální počet operací
potřebných k přesunu, je otevřený problém. Článek vylepšuje asymptotické odhady
pro 5 a více tyček.
PDF
Jean Cardinal, Gwenaël Joret: Hitting All Maximal Independent Sets of a Bipartite
Graph
Hledame podmonozinu vrcholu bipartitniho grafu, ktera obsahuje aspon jeden vrchol z kazde maximalni nezavisle mnoziny v tomto grafu. Ukazuje se, ze je to uplne pro druhou uroven polynomialni hierarchie.
PDF
Klein, Suri: Pursuit Evasion on Polyhedral Surfaces
Na povrchu polyedru uniká kořist a honí ho určitý počet lovců.
Otázka zní, kolik je potřeba lovců, aby vždy chytili kořist.
Hra je diskretizovaná a ukazuje se, že 4 lovci vždy stačí.
PDF
Mateusz Gorczyca, Adam Janiak, Wladyslaw Janiak, Marcin Dymański: Makespan optimization in a single-machine scheduling problem with dynamic job ready times-Complexity and algorithms
Varianta rozvrhovaní na jednom procesoru, kde lze měnit časy na přípravu jednotlivých úkolů. Jejich zkracovaní je ovšem nákladné. Jako obvykle je třeba najít rozvrh, kdy bude vše hotové co nejdříve. Ukazuje se NP-těžkost a zkoumají se výsledky dvou heuristik. PDF
Sergey Bereg, Ferran Hurtado, Mikio Kano, Matias Korman, Dolores Lara, Carlos Seara, Rodrigo I. Silveira, Jorge Urrutia, Kevin Verbeek: Balanced partitions of 3-colored geometric sets in the plane
Ukazuje se například, že pro každé rozložení přímek obarvených třemi barvami v rovině existuje úsečka, která protíná právě jednu přímku od každé barvy, a pokud je přímek každé barvy stejně, pak existuje také úsečka, která protíná právě polovinu přímek každé barvy. Podobné věci s body na kruhu. PDF
Dvir Shabtay, George Steiner, Liron Yedidsion: A pseudo-polynomial time algorithm for solving the resource dependent assignment problem
Úkoly se přídělují agentům a těm potom prostředky. Cena je součinem ceny úkolu a ceny agenta, která závisí na množství prostředků mu přidělených. Bylo známo, že problém je NP-těžký pro všechny možné váhy úkolů, tady se ukazuje pseudo-polynomiální algoritmus. Problém je tedy jen slabě NP-těžký. PDF
Trevor Fenner, Oded Lachish, Alexandru Popa: Min-Sum 2-Paths Problems
Je dán neorientovaný graf a dva páry vrcholů. Cílem je graf zorientovat tak, aby součet vzdáleností byl minimální. Ukazuje se aproximační schéma pro tento problém. Jeho důsledkem je také redukce na problém, kde se hledají dvě nejkratší disjunktní cesty mezi danými páry vrcholů. PDF
Márcia R. Cappelle, Felix Joos, Janina Müttel, Dieter Rautenbach: Badly-covered graphs
Pro nějaký velký graf uvažme jeho maximální indukované podgrafy, které jsou úplné k-partitní. Kolik ruzných velikostí mohou mít? Ukazuje se horní a dolní odhad, které nejsou daleko od sebe a souvislosti s dalsimi veličinami, také na speciálních třídách grafů. PDF
Vadim Lozin, Raffaele Mosca, Christopher Purcell: Independent domination in finitely defined classes of graphs: Polynomial algorithms
V grafu se hledá množina, která je zároveň nezávislá a dominující. Ukazuje se v třídách grafů neobsahujících jisté indukované podgrafy lze takovou množinu najít v polynomiálním čase. Spolu s předchozím článkem autorů dává P/NP-c dichotomii. PDF
Richard Hoshino, Ken-Ichi Kawarabayashi: The edge density of critical digraphs
Graf je barevně k-kritický, pokud k jeho obarvení je potřeba k barev, ale každý jeho podgraf lze obarvit k-1 barvami.
Kolik takový graf na n vrcholech může mít hran? V článku se zkoumá obdoba pro orientované grafy a konstrují grafy posouvající dolní mez dolů a horní nahoru. Také se konstruují digrafy s velkou barevností a bez krátkých cyklů. PDF
Pierre Aboulkera, Pierre Charbita, Nicolas Trotignonb, Kristina Vušković: Vertex elimination orderings for hereditary graph classes
Řada dědičných tříd grafů přpouští vyřazovací schéma pro vrcholy takové, že o sousedství právě vyřazovaného vrcholu lze řící něco zajímaveho. Článek sjednocuje několik starších postupů, jak takové schéma najít. PDF
Daniel Reidenbach, Markus L. Schmid: Patterns with bounded treewidth
Vzor je řetězec obsahující symboly a proměnné. Rozpoznat, zda řetezec vyhovuje zadanému vzoru je NP-úplné. Ukazuje se, že pokud se omezíme na vzorky, které (interpretovány jako jistá relační struktura) jsou podobné stromu, lze problém řešit v polynomiálním čase. PDF
E.V. Brazil, C.M.H. de Figueiredo, G.D. da Fonseca, D. Sasaki: The cost of perfection for matchings in graphs
Zkoumá se poměr mezi vahou nejtěžšího párování v grafu a nejtěžšího perfektního párování. Ukazují se těsné meze pro jisté třídy kubických grafů bez mostů, které jsou důležité pro aplikace v počítačové grafice. PDF
Tobias Friedrich, Anton Krohmer: Parameterized clique on inhomogeneous random graphs
Ukazuje se, že na (některých) grafech s exponenciální distribucí stupňů (sociální sítě) lze rozhodnout o existenci kliky o velikosti k v lineárním čase pro každé pevné k, což obecně nejspíše možné není. PDF
Antonio J. Lozano, Juan A. Mesa, Frank Plastria: Location of weighted anti-ordered median straight lines with Euclidean distances
V rovině je zadán mnohoúhelník a množina vážených bodů. Cílem je najít přímku, která protíná mnohoúhelník a maximalizuje součet vážených vzdáleností od bodů. Ukazuje se, že pro eukleidovskou vzdálenost ji lze najit v čase O(n4). PDF
Konrad K. Dabrowski, Vadim V. Lozin, Juraj Stacho: Stable-Π partitions of graphs
Hledá se nezavislá množina v grafu taková, že zbytek grafu má vlastnost Π. Ukazuje se, že pro většinu dědičných vlastností Π je problém polynomiální, kdežto pro nedědíčné může být NP-úplný. PDF
Susan A. van Aardt, Alewyn P. Burger, Jean E. Dunbar, Marietjie Frick, Bernardo Llano, Carsten Thomassen, Rita Zuazua: Destroying longest cycles in graphs and digraphs
Ukazuje se, že pro grafy průměru k ≤ 8 z nich stačí odebrat k-tinu vrcholů abychom zničili všechny nejdelší kružnice. Podobně to funguje pro orientované grafy průměru nejvýše 3. Pro vyšší průměry to nefunguje. PDF
John Fearnley, Marcin Jurdziński: Reachability in two-clock timed automata is PSPACE-complete
Ukazuje, že rozhodnout zda nedeterministický automat s jedním omezeným čítačem může dosáhnout určitého stavu je PSPACE-úplný problém. PDF
Marek Cygan, Marcin Pilipczuk: Faster exponential-time algorithms in graphs of bounded average degree
Ukazuje se rada exponenciálních algoritmů pro řídké grafy a matice. Konkrétně s konstantním průměrným stupněm. Permanent (obdoba determinantu, jen bez střídaní znamének) v řídké matici rychleji než 2n, počet perfektních párování v obecném grafu za 2n/2 a v řídkém ještě rychleji, Hamiltonovské kružnice, atd. PDF
Markus Bläser: Noncommutativity makes determinants hard
Ukazuje se, že počítat determinant je snadné nad komutativními poli a těžké nad nekomutativními poli. Možná bude trochu výzva kvůli té algebře, ale určitě by se dalo něco vybrat. PDF
Tong-Wook Shinn, Tadao Takaoka: Variations on the bottleneck paths problem
Máme graf s kapacitami hran. Úzké hrdlo cesty je kapacita hrany s nejnižší kapacitou na této cestě. Úzké hrdlo mezi dvěma vrcholy je maximum z úzkých hrdel přes všechny cety mezi těmito vrcholy. Úzké hrdlo grau je minimu z úzkých hrdel mezi dvojicemi vrcholů. Ukazjí se rychlé algoritmy, jak spočítat úzké hrdlo grafu a úzká hrdla z jednoho vrcholů a mezi všemi páry vrcholů. PDF
F. Giroire, I. Lamprou, D. Mazauric, N. Nisse, S. Pérennes, R. Soares: Connected surveillance game
Jedná se o hru na grafu pro dva hráče. První hráč v každém kole označí nějaký pevně stanovený počet vrcholů. Druhý hráč se v každém kole posune na nějakého souseda vrcholu v němž byl a snaží se dostat na nějaký neoznačený vrchol. První hráč se mu v tom snaží zabránit. Dohledové číslo grafu je minimální počet označovaných vrcholů, při kterém ještě vyhraje první hráč. V souvislé variantě je možné označovat vrcholy poze tak, že jimi indukovaný podgraf je vždy souvislý. ZKoumá se poměr mezi dohledovým číslem a souvislým dohledovým číslem a ukazují se odhady z obou stran. PDF
Jia Xu, Zhaohui Liu: Online scheduling with equal processing times and machine eligibility constraints
Máme m ekvivalentních strojů, na které rozvrhujeme úkoly, které poostupně přicházejí. Úkoly ovšem nemohou být zpracovány na všech strojích, pro každý máme množinu strojů na kterých ho lze zpracovat. Cílem je dokončit všechny úkoly co nejdříve. Ukazují se optimální deterministické algoritmy pro případy, kdy množiny strojů nejsou libovolné, ale jsou mezi nimi určité vztahy. PDF
Jozef Jirásek, Galina Jirásková: On the boundary of regular languages
Představme si, že máme regulární jazyk L, přijímaný deterministickým automatem o n stavech. Kolik stavů má minimální deterministický automat přijímající jazyk, který je průnikem iterace L a iterace doplňku L? Ukazuje se, že nejvýše O(4n). Dále se ukazují jazyky nad dvou a tříprvkouvou abecedou, které tuto mez dosahují a že jazyky nad víceprvkouvou abecedou ji dosáhnout nemohou. PDF
Klaus Jansen, Stefan Kratsch, Dániel Marx, Ildikó Schlotter: Bin packing with fixed number of bins revisited
Ukazuje se, že pro bin packing s čísly zadanými v unárním kódování (pravděpodobně) neexistuje lepší algoritmus než ten jednoduchý známý.
Naopak, pokud dovolíme jeden bin navíc, lze algoritmus značně zrychlit. PDF
Rahul Garg, Sanjiv Kapoor: Auction Algorithms for Market Equilibrium
Máme trh s různými dodavateli a kupujícími, kteří mají zájem o určité zboží. Úkolem je nastavit ceny a přiřadit zboží kupujícím tak, aby se vše prodalo a nikdo neměl touhy koupit spíš něco jiného. PDF
Noga Alon and Abbas Mehrabian: Chasing a Fast Robber on Planar Graphs and Random Graphs
Kolik policajtů je potřeba k chycení zloděje na rovinném grafu, pokud se zloděj pohybuje nekonečnou rychlostí, ale nemůže projít místem, kde stojí policajt. Zkoumá se vztah s běžnou stromovou šířkou a aproximační algoritmus. PDF
Alex Fink, Aviezri S. Fraenkel, Carlos Santos: LIM is not slim
Zkoumá se hra LIM, která je blízká známé hře nim. Konkrétně jde o to při jakých počtech kdo vyhrává. PDF
Alan Frieze, Wesley Pegden: The Topology of Competitively Constructed Graphs
Hráči se střídají v přidávání hran do grafu, ale nesmí překročit stupeň k u žádného vrcholu. Pro k ≤ může jeden hráč udržet graf rovinný, zatímco pro k=4 může jeden hráč v grafu vyrobit libovolně velké klikové minory. PDF
Tri Lai: A simple proof for the number of tilings of quartered Aztec diamonds
Kolika způsoby lze vydláždit "kosočtverec" dominovými kostkami. PDF
Yoshimi Egawa and Kenta Ozeki: Spanning Trees with Vertices Having Large Degrees
Ukazuje se postačující podmínka na to kdy má souvislý graf kostru, v níž stupně jednotlivých vrcholů jsou aspoň tolik kolik jim bylo předepsáno. PDF
Tomasz Kociumaka, Jakub Pachocki, Jakub Radoszewski, Wojciech Rytter, Tomasz Waleń: Efficient counting of square substrings in a tree
Hledají se čtverce ve stromě, tedy dvě po sobě jdoucí naprosto schodné části (druhá mocnina ve zřetězení). Algoritmus pracuji rychleji, než kolik může být výsledků, proto se využívá nově vyvinutá kompaktní reprezentace čtverců. PDF
Daniel J. Harvey and David R. Wood: Treewidth of the Line Graph of a Complete Graph
Určuje se stromová šířka (podobnost se stromem) hranového grafu úplného grafu, který je velmi důležitý v mnoha nedávných konstrukcích. PDF
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(C4, K8)
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
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(n4) 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
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
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
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. PDFPDF
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
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
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
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
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
Články, které už byly
Daniel Meister: Using swaps and deletes to make strings match
Lze z jednoho zadaného řetězce vyrobit druhý pomocí prohazování sousedních symbolů a mazání? Ukazuje se polynomialní algoritmus který určí nejmenší nutný počet takových operací. PDF
Představil: Václav Blažej
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
Představil: Miroslav Hrončok
Fomin, Heggernes, Leeuwen: The Firefighter problem on graph classes
Oheň na grafu se šíří po vlnách a v každém tahu je možné umístit někam hasiče.
Cílem je zachránit co největší část grafu. Problém je NP-těžký a nejde ani rozumně aproximovat.
Článek dává polynomiální algoritmus pro některé třídy průnikových grafů.
PDF
Představil: Radovan Červený
Timothy M. Chan, Stephane Durocher, Matthew Skala, Bryan T. Wilkinson: Linear-Space Data Structures for Range Minority Query in Arrays
V poli zodpovídáme intervalové dotazy "jaký je tu nejméně četný prvek".
Článek konstruuje pouze O(n) velkou datovou strukturu na tyto dotazy
a O(sqrt(n)) na dotaz. PDF
Představil: Štěpán Plachý
Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan, Uri Zwick: Hollow Heaps
Ukazuje se nova datova struktura, ktera je stejne efektivni jako Fibonacciho haldy, ale jednodussi. PDF
Představil: Jakub Puchýř
Eric Laugerotte, Nadia Ouali Sebti, Djelloul Ziadi: From Regular Tree Expression to Position Tree Automaton
Metoda sousedu pro prevod regularnich vyrazu na konecny automat se zobecnuje na regularni vyrazy pro stromy. PDF
Představil: Tomáš Pecka
Roberto Solis-Oba, Paul Bonsma, Stefanie Lowski: A 2-Approximation Algorithm for Finding a Spanning Tree with Maximum Number of Leaves
Hledame kostru s nejvice listy. Ukazuje se jednoducha linearni 2-aproximace, drive se znala pozue 3-aproximace. PDF
Představil: Peter Mitura
Avery Miller, Andrzej Pelc: Fast Rendezvous with Advice
Na grafu se mají navzájem najít dva roboti.
Jaké je minimální množství informace, která se robotům poradí, aby se našli v optimálním čase?
PDF
Představila: Evgeniya Nenenko
Dujmovic, Morin: On obstacle numbers
Překážkové číslo grafu je minimální velikost viditelnostního grafu v systému rovinných překážek.
Článek ukazuje vylepšení dolní meze.
PDF
Představila: Ksenia Shakurova
Suzanne Seager: Locating a backtracking robber on a tree
Policistka honí zloděje na grafu a vždy když vstoupí do vrcholu, dozví se, jak daleko zloděj je. Zloděj se pohybuje jen na sousední vrcholy. Policistka vyhrává, když zjistí, kde přesně zloděj je. Charakterizují se stromy, na kterých policistka vyhrává. PDF
Představil: Bogoljub Jakovcheski
Takayasu Kuwata, Hiroshi Maehara: Another exploration problem
Variace na znamou hricku s velbloudem, ktery zere svuj naklad a snazi se dojit co nejdale do pouste. PDF
Představil: Jan Cejhon
John Haslegrave, Richard A.B. Johnson, Sebastian Koch: The Robber Locating game
Policajt se snazi zjistit, kde se v grafu skryva zlodej tak, ze se pta na vrcholy a dozvi se vzdalenost zlodeje. Ten se muze mezi kazdymi dvema dotazy posunout na sousedni vrchol. Ukazuje se, kdy policajt vyhraje na podrozdelenich grafu, jak to dopadne na uplnych bipartitnich grafech a jak na grafech bez kratkych kruznic. PDF
Představil: Alexander Bublik
Bereczky, Duch, Nemeth, Roura: Quad-kd trees: A general framework for kd trees and quad trees
Článek uvádí novou datovou strukturu pro ukládání bodů v mnoharozměrném prostoru.
Ukazuje se jak exaktní, tak experimentální analýza.
PDF
Představil: Jiří Stránský