Teoretický seminář si klade za cíl přiblížit studentům současnou vědeckou práci.
V letním semestru 2016/17 měl kód MI-TS4 (případně BI-TS4) a konal se každý čtvrtek od 11:00 v místnosti TH:A-1442.
Povinností každého přednášejícího je připravit k přednášce handout, můžete využít šablonu od Radovana Červeného (příklad použití).
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 2016/17 skončil.
Těšíme se na setkání v zimním semestru 2017/18, tentokrát pod kódy BI-TS1 a MI-TS1.
Nezapomeňte se také přihlásit na konferenci STIGMA.
Minulý program
Dne 18.5.2017 představil Vladislav Martyniuk článek QuickHeapsort: Modifications and Improved Analysis jehož autory jsou Volker Diekert a Armin Weiß (viz handout).
Dne 11.5.2017 byl rozvrh jako v liché pondělí, seminář se tedy nekonal.
Dne 4.5.2017 představil Alexander Bublik článek A probabilistic version of the game of Zombies and Survivors on graphs jehož autory jsou Anthony Bonatoa, Dieter Mitsche, Xavier Pérez-Giménez a Paweł Prałat (viz handout).
Dne 27.4.2017 představí Jakub Vašíček článek To catch a falling robber jehož autory jsou William B.Kinnersley, Paweł Prałat a Douglas B.West (viz handout).
Dne 20.4.2017 představil Peter Mitura článek Simple and efficient fully-functional succinct trees jehož autory jsou Joshimar Cordova, Gonzalo Navarro (viz handout).
Ve dnech 6. a 13.4.2017 se seminář nekonal, byl zrušen.
Dne 30.3.2017 představil Radovan Červený článek Edge-coloring of 3-uniform hypergraphs jehož autory jsou Paweł Obszarski a Andrzej Jastrzębski (viz handout).
Dne 23.3.2017 mluvil Václav Blažej o Online Ramsey Theory.
Dne 16.3.2017 se seminář nekonal, byl zrušen.
Dne 9.3.2017 představil Miloslav Brožek článek Efficient Dynamic Range Minimum Query jehož autory jsou Alice Heliou, Martine Léonard, Laurent Mouchard a Mikael Salson (viz handout).
Dne 2.3.2017 představil Radovan Červený článek On the Shortest Path Game jehož autory jsou Andreas Darmann, Ulrich Pferschy a Joachim Schauer (viz handout).
Dne 23.2.2017 se představovaly a rozdělovaly články.
Michał Karpinski: Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete PDF
Darryn Bryant, Andrea Burgess, Peter Danziger: Decompositions of complete graphs
into bipartite 2-regular subgraphs PDF
János Csányi, Péter Hajnal, Gábor V. Nagy: On the staircases of Gyárfás PDF
Matthew Farrell, Lionel Levine: Multi-Eulerian tours of directed graphs PDF
Jaromy Kuhl, Michael W. Schroeder: Completing partial latin squares with one nonempty row, column, and symbol PDF
Reinhard Diestel: A simple existence criterion for normal spanning trees PDF
Lech Duraj, Grzegorz Gutowski, Jakub Kozik: Chip games and paintability PDF
Matthew Brennan: Ramsey numbers of trees versus odd cycles PDF
Gábor N. Sárközy: On the multi-colored Ramsey numbers of paths and even cycles PDF
Dhruv Mubayi, Jacques Verstraëte: Counting trees in graphs PDF
Daniel Johnston, Cory Palmer, Amites Sarkar: Rainbow Turán problems for paths and forests of stars PDF
Barnaby Roberts: Ramsey Numbers of Connected Clique Matchings PDF
Witold Szczechla: The three colour hat guessing game on cycle graphs PDF
Tomasz Luczak, Joanna Polcyn: On the multicolor Ramsey number for 3-paths of length three PDF
Justyna Banaszak: On matchings in stochastic Kronecker graphs PDF
András Gyárfás, Gábor N. Sárközy: Induced colorful trees and paths in large chromatic graphs PDF
Youngho Kim, Joong Chae Na, Heejin Park, Jeong Seop Sim: A space-efficient alphabet-independent Four-Russians’ lookup table and a multithreaded Four-Russians’ edit distance algorithm PDF
Rogério Reis, Emanuele Rodaro: Ideal regular languages and strongly connected synchronizing automata PDF
Luis Pedro Montejano, Ignasi Sau: On the complexity of computing the k-restricted edge-connectivity of a graph PDF
Gyorgy Dosa, Zsolt Tuza: Multiprofessor scheduling PDF
Paul Bonsma: Rerouting shortest paths in planar graphs PDF
Binay K. Bhattacharya, Minati De, Anil Maheshwari, Subhas C. Nandy, Sasanka Roy: Rectilinear path problems in restricted memory setup PDF
Valentin Garnero, Ignasi Sau, Dimitrios M. Thilikos: A linear kernel for planar red–blue dominating set PDF
Dániel Gerbner, Balázs Keszegh, Dömötör Pálvölgyi, Balázs Patkós, Máté Vizer, Gábor Wiener: Finding a non-minority ball with majority answers PDF
John Haslegrave, Chris Cannings: Majority dynamics with one nonconformist PDF
Pritam Bhattacharya, Subir Kumar Ghosh, Bodhayan Roy: Approximability of guarding weak visibility polygons PDF
H. B. de Macedo Filho, C. M. H. de Figueiredo, Z. Li, R. C. S. Machado: Using SPQR-trees to speed up recognition algorithms based
on 2-cutsets 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
É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
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
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
Andreas Darmanna, Ulrich Pferschy, Joachim Schauer: On the Shortest Path Game PDF
Představil: Radovan Červený
A. Helioua, M. Léonard, L. Mouchard, M. Salson: Efficient dynamic range minimum query PDF
Představil: Miloslav Brožek
Joshimar Cordova, Gonzalo Navarro: Simple and efficient fully-functional succinct trees PDF
Představil: Peter Mitura
William B.Kinnersley, Paweł Prałat, Douglas B.West: To catch a falling robber PDF
Představil: Jakub Vašíček
Anthony Bonatoa, Dieter Mitsche, Xavier Pérez-Giménez, Paweł Prałat: A probabilistic version of the game of Zombies and Survivors on graphs PDF
Představil: Alexander Bublik
Volker Diekert, Armin Weiß: QuickHeapsort: Modifications and Improved Analysis PDF
Představil: Vladislav Martyniuk