Teoretický seminář si klade za cíl přiblížit studentům současnou vědeckou práci.
V zimním semestru 2017/18 měl kód MI-TS1 (případně BI-TS1) a konal se každé úterý od 12:45 v místnosti TH:A-1342. Navíc se ještě několikrát uskutečnil ve čtvrtek od 11:00 v místnosti TH:A-1252.
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 zimním semestru 2017/18 skončil.
Těšíme se na setkání v letním semestru 2017/18, tentokrát pod kódy BI-TS2 a MI-TS2.
Minulý program
Dne 19.12.2017 představil Radovan Červený článek Unavoidable sets of constant length jehož autory jsou Jean-Marc Champarnaud, Georges Hansel a Dominique Perrin (viz handout).
Dne 12.12.2017 se seminář nekonal, byl zrušen.
Dne 5.12.2017 představil Igor Rosocha článek On the multicolor Ramsey number for 3-paths of length three jehož autory jsou Tomasz Luczak a Joanna Polcyn (viz handout).
Dne 28.11.2017 představil Jan Matyáš Křišťan článek Minimal dominating sets in interval graphs and trees jehož autory jsou Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch a Yngve Villanger (viz handout).
Mimořádně dne 23.11.2017 představil Martin Kostelanský článek Approximately counting paths and cycles in a graph jehož autorem je Masaki Yamamoto (viz handout).
Dne 21.11.2017 představil Tung Anh Vu článek Decompositions of complete graphs into bipartite 2-regular subgraphs jehož autory jsou Darryn Bryant, Andrea Burgess a Peter Danziger (viz handout).
Dne 14.11.2017 se seminář nekonal, byl zrušen.
Dne 7.11.2017 se pokusil Patrik Nikl představit článek Induced colorful trees and paths in large chromatic graphs jehož autory jsou Andras Gyarfas a Gabor N. Sarkozy (viz handout).
Dne 31.10.2017 představil Miroslav Sochor článek Solving the train marshalling problem by inclusion–exclusion jehož autory jsou Franca Rinaldi a Romeo Rizzi (viz handout).
Dne 24.10.2017 představil Josef Erik Sedláček článek 1.5-approximation algorithm for the 2-Convex Recoloring problem jehož autory jsou Reuven Bar-Yehuda, Gilad Kutiel a Dror Rawitz (viz handout).
Dne 17.10.2017 představil Ondřej Bíža článek Waiter-Client and Client-Waiter colourability and k-SAT games jehož autorem je Wei En Tan (viz handout).
Dne 10.10.2017 představil Peter Mitura článek Small feedback vertex sets in planar digraphs jehož autory jsou Louis Esperet, Laetitia Lemoine a Frederic Maffray (viz handout).
Dne 3.10.2017 se představovaly a rozdělovaly články.
Zoltán Füredi, Lale Özkahya: On 3-uniform hypergraphs without a cycle of a given length PDF
Dušan Knop, Tomáš Masařík: Computational complexity of distance edge labeling PDF
Andreas Darmann, Ulrich Pferschy, Joachim Schauer: The shortest connection game PDF
Simone Dantas, Luerbio Faria, Celina M.H. de Figueiredo,
Rafael B. Teixeira: The (k,ℓ)partitioned probe problem: NP-complete versus
polynomial dichotomy PDF
A. Collins, J. Foniok, N. Korpelainen, V. Lozin, V. Zamaraev: Infinitely many minimal classes of graphs of unbounded
clique-width PDF
Marcin Kamiński, Jean-Florent Raymonda, Théophile Trunck: Well-quasi-ordering H-contraction-free graphs PDF
Stefan Kratsch, Martin Milanič: On the complexity of the identifiable subgraph problem,
revisited PDF
Nour El Houda Tellache, Mourad Boudhar: Open shop scheduling problems with conflict graphs PDF
Petr A. Golovach, Daniël Paulusmab, Iain Stewart: Graph editing to a fixed target PDF
Md. Jawaherul Alama, Steven Chaplick, Gašper Fijavž, Michael Kaufmannc,
Stephen G. Kobourova, Sergey Pupyrev, Jackson Toeniskoetter: Threshold-coloring and unit-cube contact representation of
planar graphs PDF
Guillaume Fertin, Joseph G. Peters, Lynette Raabeb, Charlie Xu: Odd gossiping PDF
Emma Barmea, Julien Bensmail, Jakub Przybyło, Mariusz Woźniak: On a directed variation of the 1-2-3 and 1-2 Conjectures PDF
Sh. Haghi, H.R. Maimani, A. Seify: Star-critical Ramsey number of Fn versus K4 PDF
Jiří Fiala, Tomáš Gavenčiak, Dušan Knop, Martin Koutecký, Jan Kratochvíl: Parameterized complexity of distance labeling and uniform channel assignment problems PDF
Joan Boyar, Christian Kudahl: Adding isolated vertices makes some greedy online
algorithms optimal PDF
Bastien Cazaux, Eric Rivals: Relationship between superstring and compression
measures: New insights on the greedy conjecture PDF
D.V. Gribanov, D.S. Malyshev: The computational complexity of three graph problems for
instances with bounded minors of constraint matrices PDF
Manfred Cochefert, Jean-François Couturier, Petr A. Golovach,
Dieter Kratsch, Daniël Paulusmad, Anthony Stewart: Computing square roots of graphs with low maximum
degree PDF
Josep M. Aroca, Anna Lladó: On star forest ascending subgraph decomposition PDF
Barnaby Roberts: Ramsey Numbers of Connected Clique Matchings PDF
Stephan Kreutzer, Sang-il Oumz, Paul Seymour,
Dominic van der Zypen, David R. Wood: Majority Colourings of Digraphs PDF
Daniel Johnston, Cory Palmer, Amites Sarkar: Rainbow Turan problems for
paths and forests of stars PDF
Leszek Gasieniec, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas,
Jie Min, Tomasz Radzik: Bamboo Garden Trimming Problem PDF
Michał Karpinski: Vertex 2-coloring without monochromatic cycles of fixed size is NP-complete 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
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
Zamluvené články
Fangxia Wang, Baoyindureng Wu, Xinhui An: A
P3-decomposition of tournaments and bipartite digraphs PDF
Zamluveno pro: Václav Rechtberger
Sylvia A. Hobart, Jason Williford: New feasibility conditions for directed
strongly regular graphs PDF
Zamluveno pro: Petr Tománek
Články, které už byly
Louis Esperet, Laetitia Lemoine, Frederic Maffray: Small feedback vertex sets in planar digraphs PDF
Představil: Peter Mitura
Wei En Tan: Waiter-Client and Client-Waiter colourability and k-SAT games PDF
Představil: Ondřej Bíža
Reuven Bar-Yehuda, Gilad Kutiel, Dror Rawitz: 1.5-approximation algorithm for the 2-Convex Recoloring
problem PDF
Představil: Josef Erik Sedláček
Franca Rinaldi, Romeo Rizzi: Solving the train marshalling problem by inclusion–exclusion PDF
Představil: Miroslav Sochor
Andras Gyarfas, Gabor N. Sarkozy: Induced colorful trees and paths
in large chromatic graphs PDF
Pokusil se představit: Patrik Nikl
Darryn Bryant, Andrea Burgess, Peter Danziger: Decompositions of complete graphs
into bipartite 2-regular subgraphs PDF
Představil: Tung Anh Vu
Masaki Yamamoto: Approximately counting paths and cycles in a graph PDF
Představil: Martin Kostelanský
Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté,
Dieter Kratsch, Yngve Villanger: Minimal dominating sets in interval graphs and trees PDF
Představil: Jan Matyáš Křišťan
Tomasz Luczak, Joanna Polcyn: On the multicolor Ramsey number for 3-paths of length three PDF
Představil: Igor Rosocha