Teoretický seminář si klade za cíl přiblížit studentům současnou vědeckou práci.
V zimním semestru 2016/17 měl kód MI-TS3 (případně BI-TS3) a konal se každé úterý od 16:15 v místnosti TH:A-1242, tedy na dvanáctém patře budovy A. Navíc se ještě několikrát uskutečnil v pátek od 14:30 v místnosti TH:A-1342.
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 2016/17 skončil. Těšíme se na setkání s Vámi opět v letním semestru, tentokrát pod kódem MI-TS4, případně BI-TS4.
Minulý program
Dne 3.1.2017 představil Štěpán Plachý článek The Černý conjecture and 1-contracting automata jehož autorem je Henk Don.
Dne 20.12.2016 představil Václav Blažej článek Ramsey numbers of trees versus odd cycles jehož autorem je Matthew Brennan.
Mimořádně v pátek 16.12.2016 od 14:30 v místnosti TH:A-1342 představil Alexander Bublik článek Fast construction of wavelet trees jehož autory jsou J.Ian Munro, Yakov Nekrich a Jeffrey S.Vitter.
Dne 13.12.2016 představil Šimon Lomič článek Longest common extensions in trees jehož autory jsou Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau a Oren Weimann.
Mimořádně v pátek 9.12.2016 od 14:30 v místnosti TH:A-1342 představil Miloslav Brožek článek Regular Graphs are Antimagic jehož autory jsou Kristóf Bérczi, Attila Bernáth a Máté Vizer.
Dne 6.12.2016 představil Radovan Červený článek Complexity of the game domination problem jehož autory jsou Boštjan Brešar, Paul Dorbec, Sandi Klavžar, Gašper Košmrlj a Gabriel Renault.
Dne 29.11.2016 se seminář nekonal, byl zrušen.
Dne 22.11.2016 se seminář nekonal, byl zrušen.
Dne 15.11.2016 představil Martin Paňko článek A deterministic version of the game of zombies and survivors
on graphs jehož autory jsou S.L. Fitzpatrick, J. Howell, M.E. Messinger a D.A. Pike.
Dne 8.11.2016 představila Markéta Jůzlová článek Set Intersection and Sequence Matching with mismatch counting jehož autory jsou Ariel Shiftan a Ely Porat.
Dne 1.11.2016 představil Jakub Průša článek Upper Bounds on Number of Steals in Rooted Trees jehož autory jsou Charles E. Leiserson, Tao B. Schardl a Warut Suksompong.
Dne 25.10.2016 představil Peter Mitura článek Vizing's conjecture for graphs with domination number 3 - a new proof jehož autorem je Boštjan Brešar.
Dne 18.10.2016 představil Jakub Puchýř článek Linear-size suffix tries jehož autory jsou Maxime Crochemore, Chiara Epifanio, Roberto Grossi a Filippo Mignosi.
Dne 11.10.2016 představila Klára Drhová článek On computing the degree of convexity of polyominoes jehož autory jsou Stefano Brocchi, Giusi Castiglione a Paolo Massazza.
Dne 4.10.2016 se představovaly a rozdělovaly články.
William B.Kinnersley, Paweł Prałat, Douglas B.West: To catch a falling robber PDF
Joshua Erde, Mark Walters: An n-in-a-row type game PDF
Dennis Clemens, Julia Ehrenmüller, Yury Person, Tuan Tran: Keeping Avoider's graph almost acyclic PDF
Manuel Vázquezde Parga, Pedro García, Damián López: Minimal consistent DFA revisited PDF
Tsvi Kopelowitz: The property suffix tree with dynamic properties PDF
Payam Khanteimouri, Ali Mohades, Mohammad Ali Abam, Mohammad Reza Kazemi: Efficiently approximating color-spanning balls PDF
Shinya Fujita, Gary MacGillivray, Tadashi Sakuma: Safe set problem on graphs PDF
Michael Gentner, Michael A. Henning, Dieter Rautenbach: Largest domination number and smallest independence
number of forests with given degree sequence PDF
Aistis Atminas, Marcin Kaminski, Jean-Florent Raymond: Scattered packings of cycles PDF
Minghui Jianga, Ge Xia, Yong Zhang: Edge-disjoint packing of stars and cycles PDF
André G.Pereira, Marcus Ritt, Luciana S. Buriol: Pull and PushPull are PSPACE-complete PDF
G. Konstantinidis, Ath. Kehagias: Simultaneously moving cops and robbers PDF
A. Hillebrand, C. McDiarmid: Colour degree matrices of graphs with at most one cycle PDF
Minghui Jiang, Yong Zhang: Kernelization of edge perfect code and its variants PDF
Éric Sopena: i-Mark: A new subtraction division game PDF
Djamal Belazzougui, Roman Kolpakov, Mathieu Raffinot: Indexing and querying color sets of images PDF
Michael A. Henning, William F. Klostermeyer: Trees with large m-eternal domination number PDF
Binay K. Bhattacharya, Minati De, Anil Maheshwari, Subhas C. Nandy, Sasanka Roy: Rectilinear path problems in restricted memory setup PDF
Cristina G.Fernandes, Marcio T.I.Oshiro: Kinetic clustering of points on the line PDF
Tiago Januario, Sebastián Urrutia, Dominique de Werra: Sports scheduling search space connectivity: A riffle shuffle
driven approach PDF
Carl Feghali, Matthew Johnson, Daniël Paulusma: Kempe equivalence of colourings of cubic graphs PDF
Petr A.Golovach, Daniël Paulusma, Erik Jan van Leeuwen: Induced disjoint paths in circular-arc graphs in linear time PDF
Pinar Heggernes, Daniel Meister, Charis Papadopoulos, Udi Rotics: Clique-width of path powers PDF
P. Flocchini, N. Santoro, G. Viglietta, M. Yamashita: Rendezvous with constant memory PDF
Amr Elmasry, Meng He, J. Ian Munro, Patrick K. Nicholson: Dynamic range majority data structures PDF
Naoki Matsumoto, Atsuhiro Nakamoto, Shin-ichi Yonekura: Minor relation for quadrangulations on the projective plane PDF
Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams: Deterministic Time-Space Tradeoffs for k-SUM PDF
Nir Halman: A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy PDF
Volker Diekert, Armin Weiß: QuickHeapsort: Modifications and Improved Analysis PDF
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
Články, které už byly
Maxime Crochemore, Chiara Epifanio, Roberto Grossi, Filippo Mignosi: Linear-size suffix tries PDF
Představil: Jakub Puchýř
Stefano Brocchi, Giusi Castiglione, Paolo Massazza: On computing the degree of convexity of polyominoes PDF
Představila: Klára Drhová
Boštjan Brešar: Vizing's conjecture for graphs with domination number 3 - a new proof PDF
Představil: Peter Mitura
Charles E. Leiserson, Tao B. Schardl, Warut Suksompong: Upper Bounds on Number of Steals in Rooted Trees PDF
Představil: Jakub Průša
Ariel Shiftan, Ely Porat: Set Intersection and Sequence Matching with mismatch counting PDF
Představila: Markéta Jůzlová
S.L. Fitzpatrick, J. Howell, M.E. Messinger, D.A. Pike: A deterministic version of the game of zombies and survivors
on graphs PDF
Představil: Martin Paňko
Boštjan Brešar, Paul Dorbec, Sandi Klavžar, Gašper Košmrlj, Gabriel Renault: Complexity of the game domination problem PDF
Představil: Radovan Červený
Kristóf Bérczi, Attila Bernáth, Máté Vizer: Regular Graphs are Antimagic PDF
Představil: Miloslav Brožek
Philip Bille, Paweł Gawrychowski, Inge Li Gørtz, Gad M. Landau, Oren Weimann: Longest common extensions in trees PDF
Představil: Šimon Lomič
J.Ian Munro, Yakov Nekrich, Jeffrey S.Vitter: Fast construction of wavelet trees PDF
Představil: Alexander Bublik
Matthew Brennan: Ramsey numbers of trees versus odd cycles PDF
Představil: Václav Blažej
Henk Don: The Černý conjecture and 1-contracting automata PDF
Představil: Štěpán Plachý