Publications 2017
- Moravčík, Matej, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. "DeepStack: Expert-level artificial intelligence in heads-up no-limit poker." Science 356, no. 6337 (2017): 508-513.
- Masařík, Tomáš, and Tomáš Toufar. "Parameterized complexity of fair deletion problems." International Conference on Theory and Applications of Models of Computation (TAMC). Springer, Cham, (2017).
- Knop, Dušan, and Koutecký, Martin, and Masařík, Tomáš, and Tomáš Toufar "Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity." 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers (2017).
- Knop, Dušan, and Tomáš Masařík. "Computational complexity of distance edge labeling." Discrete Applied Mathematics (2017).
- J. Fiala, J Hubička, Y Long, J Nešetřil: Fractal property of the graph homomorphism order, European Journal of Combinatorics 66, 101-109
- A. Aranda, J. Hubicka, E. K. Hng, M. Karamanlis, M. Kompatscher, M. Konecny, M. Pawliuk, D. Bradley-Williams: Completing graphs to metric spaces (extended abstract), Eurocomb 2017, Electronic Notes in Discrete Mathematics 61(2017), 53--60.
- J. Hubicka, J. Nesetril: Ramsey theorem for designs (extended abstract), Eurocomb 2017, Electronic Notes in Discrete Mathematics 61(2017), 623-629.
- J. Fiala, J. Hubicka, Y. Long: Gaps in full homomorphism order (extended abstract), Eurocomb 2017, Electronic Notes in Discrete Mathematics 61(2017), 429-435.
- Pavel Klavík, Jan Kratochvíl, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, and Tomáš Vyskočil: Extending Partial Representations of Proper and Unit Interval Graphs. Algorithmica 77(4):1071-1104, 2017.
- Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh, and Tomáš Vyskočil: Extending Partial Representations of Interval Graphs. Algorithmica 78(3):945-967, 2017.
- James Abello, Pavel Klavík, Jan Kratochvíl, and Tomáš Vyskočil: MSOL Restricted Contractibility to Planar Graphs. Theoretical Computer Science 676:1-14, 2017.
- T. Klimosova, D. Piguet, V. Rozhoň: A skew version of the Loebl-Komlós-Sós conjecture (extended abstract), Electronic Notes in Discrete Mathematics, Volume 61 (2017) 743-749.
- T. Klimosová, S. Thomassé: Decomposing graphs into paths and trees (extended abstract), Electronic Notes in Discrete Mathematics, Volume 61 (2017) 751-757.
- R. Glebov, C. Hoppen, T. Klimošová, Y. Kohayakawa, D. Král, H. Liu: Densities in large permutations and parameter testing, European J. Combin., 60 (2017), 89-99.
- Karel Zimmermann, Martin Gavalec, Richard Cimler: An Optimization Problem on the Image Set of a (max,min)-linear Operator, Fuzzy Sets and Systems (accepted).
- X. Goaoc, P. Patak, Z. Patakova, M. Tancer, U. Wagner: Bounding Helly numbers via Betti numbers. Chapter in A Journey Through Discrete Mathematics, A Tribute to Jiří Matoušek (2017, online), 407-447.
- E. Colin de Verdiere, V. Kaluza, P. Patak, Z. Patakova, M. Tancer: A Direct Proof of the Strong Hanani-Tutte Theorem on the Projective Plane. Journal of Graph Algorithms and Applications 21(5) (2017), 939-981.
- A. Hubard, V. Kaluza, A. de Mesmay, M. Tancer: Shortest Path Embeddings of Graphs on Surfaces. Discrete and Computational Geometry 58(4) (2017), 921-945.
- X. Goaoc, I. Mabillard, P. Patak, Z. Patakova, M. Tancer, U. Wagner: On Generalized Heawood Inequalities for Manifolds: A Van Kampen-Flores-type Nonembeddability Result. Israel Journal of Mathematics 222(2) (2017), 841-866.
- O. Aichholzer, M. Balko, T. Hackl, J. Kynčl, I. Parada, M. Scheucher, P. Valtr, and B. Vogtenhuber. A superlinear lower bound on the number of 5-holes, Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), Leibniz International Proceedings in Informatics (LIPIcs) 77, pages 8:1-8:16, 2017.
- M. Balko, J. Kynčl, S. Langerman, and A. Pilz. Induced Ramsey-type results and binary predicates for point sets, Electronic Notes in Discrete Mathematics 61, pages 77-83, 2017.
- M. Balko, J. Cibulka, and P. Valtr. Covering lattice points by subspaces and counting point-hyperplane incidences, Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), Leibniz International Proceedings in Informatics (LIPIcs) 77, pages 12:1-12:16, 2017.
- M. Balko, J. Kynčl, S. Langerman, and A. Pilz. Induced Ramsey-type results and binary predicates for point sets, The Electronic Journal of Combinatorics 24, Issue 4, P4.24, 22 pages, 2017.
- M. Balko and P. Valtr. A SAT attack on the Erdos--Szekeres conjecture, European Journal of Combinatorics 66, pages 13-23, 2017.
- M. Balko, V. Jelínek, P. Valtr, and B. Walczak. On the Beer index of convexity and its variants, Discrete and Computational Geometry 57(1), pages 179-214, 2017.
- Patrizio Angelini, Steven Chaplick, Sabine Cornelsen, Giordano Da Lozzo, Giuseppe Di Battista, Peter Eades, Philipp Kindermann, Jan Kratochvíl, Fabian Lipp, Ignaz Rutter: Simultaneous Orthogonal Planarity. Graph Drawing 2016: 532-545, Lecture Notes in Computer Science 9801, Springer 2016, ISBN 978-3-319-50105-5
- James Abello, Pavel Klavík, Jan Kratochvíl, Tomás Vyskocil: MSOL restricted contractibility to planar graphs. Theor. Comput. Sci. 676: 1-14 (2017)
- Carla Binucci, Markus Chimani, Walter Didimo, Martin Gronemann, Karsten Klein, Jan Kratochvíl, Fabrizio Montecchiani, Ioannis G. Tollis: Algorithms and Characterizations for 2-Layer Fan-planarity: From Caterpillar to Stegosaurus. J. Graph Algorithms Appl. 21(1): 81-102 (2017)
- Jason Crampton, Gregory Gutin, Martin Koutecký, Rémi Watrigant: Parameterized Resiliency Problems via Integer Linear Programming. CIAC 2017: 164-176
- Jakub Gajarský, Petr Hlinený, Martin Koutecký, Shmuel Onn: Parameterized Shifted Combinatorial Optimization. COCOON 2017: 224-236
- Dusan Knop, Martin Koutecký, Matthias Mnich: Combinatorial n-fold Integer Programming and Applications. ESA 2017: 54:1-54:14
- Dusan Knop, Martin Koutecký, Matthias Mnich: Voting and Bribing in Single-Exponential Time. STACS 2017: 46:1-46:14
- Dusan Knop, Martin Koutecký, Tomás Masarík, Tomás Toufar: Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity.WG 2017: 344-357 (Best Student Paper award)
- Dušan Knop, Martin Koutecký: Scheduling meets n-fold integer programming. Journal of Scheduling (to appear)
- Andreas Emil Feldmann: "Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs." Algorithmica.
- Andreas Emil Feldmann, Wai Shing Fung, Jochen Konemann, Ian Post: "A (1 + eps)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs." SIAM Journal on Computing.
- Hans Raj Tiwary, Stefan Weltge, Rico Zenklusen: Extension complexities of Cartesian products involving a pyramid. Inf. Process. Lett. 128: 11-13 (2017)
- David Avis, Hans Raj Tiwary: On the H-free extension complexity of the TSP. Optimization Letters 11(3): 445-455 (2017)
- David Avis, Hans Raj Tiwary: Compact linear programs for 2SAT. Accepted for publication in European Journal of Combinatorics.
- J. Picado and A. Pultr, Localic maps constructed from open and closed parts, Categories and General Algebraic Structures with Applications 6 (2017), 21-35
- D. Baboolal, P. Pillay, and A. Pultr, C-connected frame congruences, Categories and General Algebraic Structures with Applications 6(2017), 51-66
- M.A. Moshier, J. Picado, and A. Pultr, Generating sublocales by sub-sets and relations: a tangle of adjunctions, Algebra Univers.78 (2017),105-118
- R.N. Ball, M.A. Moshier, J.L. Walters-Wayland, and A. Pultr, Lin-deof tightness and the Dedekind-MacNeille completion of a regular sigma-frame, Quaestiones Math. 40,3(2017), 347-369
- J. Picado, A. Pultr and A. Tozzi, Joins of closed sublocales, Houston J. Math. (accepted)
- R. Chen, I. Kriz and A. Pultr, Kans combinatorial spectra and their sheaves revisited, Theory and Appl. of Categories
- J. Picado and A. Pultr, A Boolean extension of a frame and a repre- sentation of discontinuity, Quaestiones Math. (accepted),
- R.N. Ball and A. Pultr, Maximal essential extensions in the context of frames , Algebra Univ. (accepted)
- M. Loebl, J. Nesetril, R. Thomas (eds), A Journey Through Discrete Mathematics: A Tribute to Jiri Matousek, Springer Verlag (2017) ISBN 978-3-319-44479-6.
- R. Aharoni, N. Alon, E. Berger, M. Chudnovsky, D. Kotlar, M. Loebl, R. Ziv Fair representation by independent sets. A chapter in: A Journey Through Discrete Mathematics: A Tribute to Jiri Matousek, Springer (2017)
- M. Loebl, Binary linear codes via 4D discrete Ihara-Selberg function. Annales de lInstitute Henri Poincare D- European Mathematical Society (2017)
- Steven Chaplick, Peter Zeman, Combinatorial Problems on H-graphs, In Electronic Notes in Discrete Mathematics, Volume 61, 2017, Pages 223-229, ISSN 1571-0653
- Chaplick S., Topfer M., Voborník J., Zeman P. (2017) On H-Topological Intersection Graphs. In: Bodlaender H., Woeginger G. (eds) Graph-Theoretic Concepts in Computer Science. WG 2017. Lecture Notes in Computer Science, vol 10520. Springer, Cham
- Snehashish Chakraverty, Milan Hladík, and Nisha Rani Mahato. A sign function approach to solve algebraically interval system of linear equations for nonnegative solutions. Fund. Inform., 152(1):13-31, 2017.
- Snehashish Chakraverty, Milan Hladík, and Diptiranjan Behera. Formal solution of an interval system of linear equations with an application in static responses of structures with interval forces. Appl. Math. Model., 50:105-117, 2017.
- Elif Garajová, Milan Hladík, and Miroslav Rada. The effects of transformations on the optimal set in interval linear programming. In Proceedings of the 14th International Symposium on Operational Research SOR17, Bled, Slovenia, September 27-29, 2017, pp. 487-492, Slovenian Society Informatika, Ljubljana, Slovenia, 2017.
- Elif Garajová, Milan Hladík, and Miroslav Rada. On the properties of interval linear programs with a fixed coefficient matrix. In Antonio Sforza and Claudio Sterle, editors, Optimization and Decision Science: Methodologies and Applications, Springer Proceedings in Mathematics & Statistics, pp. 393-401, Springer, Cham, 2017.
- Milan Hladík. Transformations of interval linear systems of equations and inequalities. Linear Multilinear Algebra, 65(2):211-223, 2017.
- Milan Hladík. On relation between P-matrices and regularity of interval matrices. In Natália Bebiano, editor, Applied and Computational Matrix Analysis, Springer Proceedings in Mathematics & Statistics, pp. 27-35, Springer, 2017.
- Milan Hladík. Interval convex quadratic programming problems in a general form. Cent. Eur. J. Oper. Res., 25(3):725-737, 2017.
- Milan Hladík. On strong optimality of interval linear programming. Optim. Lett., 11(7):1459-1468, 2017.
- Milan Hladík. On relation of possibly efficiency and robust counterparts in interval multiobjective linear programming. In Antonio Sforza and Claudio Sterle, editors, Optimization and Decision Science: Methodologies and Applications, Springer Proceedings in Mathematics & Statistics, pp. 335-343, Springer, Cham, 2017.
- Milan Hladík and Michal Černý. Two optimization problems in linear regression with interval data. Optim., 66(3):331-349, 2017.
- Jaroslav Horáček, Milan Hladík, and Michal Černý. Interval linear algebra and computational complexity. In Natália Bebiano, editor, Applied and Computational Matrix Analysis, Springer Proceedings in Mathematics & Statistics, pp. 37-66, Springer, 2017.
- Jana Novotná, Milan Hladík, and Tomáš Masařík. Duality gap in interval linear programming. In Proceedings of the 14th International Symposium on Operational Research SOR17, Bled, Slovenia, September 27-29, 2017, pp. 501-506, Slovenian Society Informatika, Ljubljana, Slovenia, 2017.
- Julien Alexandre dit Sandretto and Milan Hladík. Solving over-constrained systems of non-linear interval equations - And its robotic application. Appl. Math. Comput., 313:180-195, 2017.
- Jiří Fiala, Jan Hubička, Yangjing Long, Jaroslav Nešetřil: Fractal property of the graph homomorphism order. Eur. J. Comb. 66: 101-109 (2017)
- Jiří Fiala, Jan Hubička, Yangjing Long: Gaps in full homomorphism order. Electronic Notes in Discrete Mathematics 61: 429-435 (2017)
- Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů. Edice CZ-NIC, 2017.
- O. Aichholzer, T. Hackl, P. Valtr, B. Vogtenhuber A Note on the Number of General 4-holes in (Perturbed) Grids Discrete and Computational Geometry and Graphs. Volume 9943 of the series Lecture Notes in Computer Science pp 1-12, 2016
- Sergio Cabello, Josef Cibulka, Jan Kynčl, Maria Saumell, Pavel Valtr. Peeling potatoes near-optimally in near-linear time. SIAM Journal on Computing 46(5) (2017), 1574-1602.
- Josef Cibulka, Miroslav Korbelář, Jan Kynčl, Viola Mészáros, Rudolf Stolař, Pavel Valtr. On three measures of non-convexity. Israel Journal of Mathematics 218 (2017), Issue 1, 331-369
- Patrizio Angelini, Steven Chaplick, Felice De Luca, Jirí Fiala, Jan Hancl Jr., Niklas Heinsohn, Michael Kaufmann, Stephen G. Kobourov, Jan Kratochvíl, Pavel Valtr: On Vertex- and Empty-Ply Proximity Drawings. Proc. of Graph Drawing 2017.
- Patrice Ossona de Mendez, Pavel Valtr and John Gimbel. Obstacle Numbers of Planar Graphs. Proc. of Graph Drawing 2017.
- Martin Balko, Josef Cibulka, Pavel Valtr: Drawing Graphs Using a Small Number of Obstacles online in Discrete and Computational Geometry, August 2017
- Markus Chimani, Stefan Felsner, Stephen G. Kobourov, Torsten Ueckerdt, Pavel Valtr, Alexander Wolff: On the Maximum Crossing Number. Proceedings of IWOCA 2017
- Oswin Aichholzer, Martin Balko, Thomas Hackl, Alexander Pilz, Pedro Ramos, Pavel Valtr and Birgit Vogtenhuber. Holes in 2-convex point sets. Proceedings of IWOCA 2017
- Jakub Gajarsky, Petr Hlinený, Hans Raj Tiwary: Parameterized extension complexity of independent set and related problems. Accepted for publication in Discrete Applied Mathematics.
- Tomás Gavenčiak, Barbara Geissmann, Johannes Lengler: Sorting by swaps with noisy comparisons. GECCO 2017: 1375-1382
- Jiří Fiala, Tomáš Gavenčiak, Dušan Knop, Martin Koutecký, Jan Kratochvíl, Parameterized complexity of distance labeling and uniform channel assignment problems, Discrete Applied Mathematics. In print, available online 23 Mar 2017
- A. Dudek, A. Frieze, A. Rucinski, M Šileikis. Embedding the Erdos-Renyi Hypergraph into the Random Regular Hypergraph and Hamiltonicity, J. Comb. Theory B, 122 (2017), pp. 719-740
- T. Luczak, K. Mieczkowska. M. Šileikis. On maximal tail probability of sums of nonnegative, independent and identically distributed random variables, Statistics & Probability Letters, 129 (2017), pp. 12-16
- C. Holmgren, S. Janson, M. Šileikis. Multivariate normal limit laws for the numbers of fringe subtrees in m-ary search trees and preferential attachment trees, Electron. J. Combin. 24-2 (2017).
- J. Cibulka and J. Kyncl, Better upper bounds on the Füredi-Hajnal limits of permutations, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), 2280-2293.
- V. Jelinek and J. Kyncl, Hardness of permutation pattern matching, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), 378-396.
- A. F. Holmsen, J. Kyncl and C. Valculescu, Near equipartitions of colored point sets, Computational Geometry: Theory and Applications 65 (2017), 35-42.
- J. Kyncl and Z. Patakova, On the nonexistence of k-reptile simplices in R^3 and R^4, The Electronic Journal of Combinatorics 24 (2017), Issue 3, P3.1, 44 pp.
- R. Fulek, J. Kyncl and D. Palvolgyi, Unified Hanani-Tutte theorem, The Electronic Journal of Combinatorics 24 (2017), Issue 3, P3.18, 8 pp.
- J. Kyncl, B. Lidicky and T. Vyskocil, Irreversible 2-conversion set in graphs of bounded degree, Discrete Mathematics & Theoretical Computer Science 19 (2017), no. 3, Paper No. 5, 18pp.
- M. Kano and J. Kyncl, The hamburger theorem, Computational Geometry: Theory and Applications 68 (2018), 167-173.
Webmaster: kamweb@kam.mff.cuni.cz Modified: 15. 11. 2017