Publications 2020

R.N. Ball, M.A. Moshier and A. Pultr: Exact filters and joins of closed sublocales, Applied Categ.Str. 28(2020), 655-667
M.A. Moshier, A. Pultr and A.L. Suarez: Exact and strongly exact filters, Applied Categ.Str. 28(2020), 877-905
D. Baboolal, P. Pillay, J. Picado and Aleš Pultr: Hewitt’s irresolvability and induced sublocales in spatial frames, Quaestiones Math. on-line August 2019
Andreas Emil Feldmann, David Saulpic:
Polynomial Time Approximation Schemes for Clustering in Low Highway Dimension Graphs. In Proceedings of the 28th Annual European Symposium on Algorithms (ESA): 46:1-46:22
Bartlomiej Bosek, Yann Disser, Andreas Emil Feldmann, Jakub Pawlewicz, Anna Zych-Pawlewicz:
Recoloring Interval Graphs with Limited Recourse Budget. In Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT): 17:1-17:23
Pavel Dvorák, Andreas Emil Feldmann, Ashutosh Rai, Pawel Rzazewski:
Parameterized Inapproximability of Independent Set in H-Free Graphs. In Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG): 40-53
Davis Issac, Andreas Emil Feldmann, Ashutosh Rai: Fixed-Parameter Tractability of the Weighted Edge Clique Partition Problem. In Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC): accepted for publication
Andreas Emil Feldmann, Karthik C. S., Euiwoong Lee, Pasin Manurangsi:
A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms. Algorithms 13(6): 146
Elif Garajová, Milan Hladík, and Miroslav Rada. Interval transportation problem: The best and the worst (feasible) scenario. In 38th International Conference on Mathematical Methods in Economics 2020 (MME 2020). Conference Proceedings, pp. 122–127, Mendel University in Brno, 2020.
David Hartman and Milan Hladík. Complexity of computing interval matrix powers for special classes of matrices. Appl. Math., 65(5):645–663, 2020.
Milan Hladík. An overview of polynomially computable characteristics of special interval matrices. In Olga Kosheleva et al., editor, Beyond Traditional Probabilistic Data Processing Techniques: Interval, Fuzzy etc. Methods and Their Applications, Studies in Computational Intelligence, pp. 295–310, Springer, Cham, 2020.
Milan Hladík. P-completeness of testing solutions of parametric interval linear systems. In Martine Ceberio and Vladik Kreinovich, editors, Decision Making under Constraints, Studies in Systems, Decision and Control, pp. 117–123, Springer, Cham, 2020.
Milan Hladík. Two approaches to inner estimations of the optimal solution set in interval linear programming. In Proceedings of the 2020 4th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence, pp. 99–104, ISMSI 2020, Association for Computing Machinery, New York, USA, 2020.
Milan Hladík. Redundancy in interval linear systems. In 38th International Conference on Mathematical Methods in Economics 2020 (MME 2020). Conference Proceedings, pp. 160–165, Mendel University in Brno, 2020.
Milan Hladík, Michal Černý, and Jaromír Antoch. EIV regression with bounded errors in data: total 'least squares' with Chebyshev norm. Stat. Papers, 61(1):279–301, 2020.
Milan Hladík and David Hartman. Maximization of a convex quadratic form on a polytope: Factorization and the Chebyshev norm bounds. In Optimization of Complex Systems: Theory, Models, Algorithms and Applications, pp. 119–127, AISC 991, Springer, Cham, 2020.
Hossein Moosaei and Milan Hladík. Least squares K-SVCR multi-class classification. In Ilias S. Kotsireas and Panos M. Pardalos, editors, Learning and Intelligent Optimization, LNCS, pp. 117–127, Springer, Cham, 2020.
Hossein Moosaei and Milan Hladík. Minimum norm solution of the Markowitz mean-variance portfolio optimization model. In 38th International Conference on Mathematical Methods in Economics 2020 (MME 2020). Conference Proceedings, pp. 383–388, Mendel University in Brno, 2020.
Amin Mostafaee and Milan Hladík. Optimal value bounds in interval fractional linear programming and revenue efficiency measuring. Cent. Eur. J. Oper. Res., 28(3):963–981, 2020.
Jana Novotná, Milan Hladík, and Tomáš Masařík. Duality gap in interval linear programming. J. Optim. Theory Appl., 184(2):565–580, 2020.
Iwona Skalna, Marcin Pietroń, and Milan Hladík. Improvements of monotonicity approach to solve interval parametric linear systems. In R. Wyrzykowski et al., editor, Parallel Processing and Applied Mathematics, LNCS, pp. 374–383, Springer, Cham, 2020.
Milan Hladík and Martin Černý. Weak and strong consistency of an interval comparison matrix. In V.-N. Huynh et al., editor, Integrated Uncertainty in Knowledge Modelling and Decision Making, LNAI, pp. 15–25, Springer, Cham, 2020.
Balko, M., Bhore, S., Martínez-Sandoval, L., Valtr, P.: On Erdős–Szekeres-type problems for k-convex point sets, European Journal of Combinatorics, 2020, 89, 103157.
Aichholzer, O., Balko, M., Hackl, T., Kynčl, J., Parada, I., Scheucher, M., Valtr, P., Vogtenhuber, B.: A superlinear lower bound on the number of 5-holes, Journal of Combinatorial Theory. Series A, 2020, 173, 105236.
Balko, M., Vizer, M. Edge-ordered Ramsey numbers, European Journal of Combinatorics, 2020, 87, 103100.
Balko, M., Scheucher, M., Valtr, P.: Holes and islands in random point sets, Leibniz International Proceedings in Informatics, LIPIcs, 2020, 164, LIPIcs-SoCG-2020-14. 5)
Balko, M., Pór, A., Scheucher, M., Swanepoel, K. , Valtr, P.: Almost-Equidistant Sets, Graphs and Combinatorics, 2020, 36(3), pp. 729-754.
Balko, M., Cibulka, J., Král, K., Kynčl, J.: Ramsey numbers of ordered graphs, Electronic Journal of Combinatorics, 2020, 27(1), P1.16.
Carl Feghali, Jiří Fiala: Reconfiguration graph for vertex colourings of weakly chordal graphs. Discret. Math. 343(3): 111733 (2020)
Václav Blažej, Jiří Fiala and Giuseppe Liotta. On the edge-length ratio of 2-trees.
Kateřina Altmanová, Petr Kolman and Jan Voborník: On Polynomial-Time Combinatorial Algorithms for Maximum L-Bounded Flow , Journal of Graph Algorithms and Applications, Volume 24, Number 3, pp. 303-322, 2020
Eden Chlamtáč, Petr Kolman: How to Cut a Ball without Separating: Improved Approximations for Length Bounded Cut Proc. of 23rd Int. Conf. on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2020), pp. 41:1-41:17, 2020
Petr Kolman, Martin Koutecký, Hans Raj Tiwary: Extension Complexity, MSO Logic, and Treewidth. Discret. Math. Theor. Comput. Sci. 22(4) (2020)
Hans Raj Tiwary: Extension Complexity of Formal Languages. Theory Comput. Syst. 64(5): 735-753 (2020)
Hans Raj Tiwary, Victor Verdugo, Andreas Wiese: On the extension complexity of scheduling polytopes. Oper. Res. Lett. 48(4): 472-479 (2020)
Lars Jaffke, Mateus de Oliveira Oliveira, Hans Raj Tiwary: Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach. MFCS 2020: 50:1-50:15
Pawan Aurora, Hans Raj Tiwary: On the Complexity of Some Facet-Defining Inequalities of the QAP-polytope. Accepted COCOA 2020
R. Fulek and J. Kynčl, Counterexample to an extension of the Hanani-Tutte theorem on the surface of genus 4, Combinatorica 39 (2019), Issue 6, 1267--1279. https://doi.org/10.1007/s00493-019-3905-7
O. Aichholzer, M. Balko, M. Hoffmann, J. Kynčl, W. Mulzer, I. Parada, A. Pilz, M. Scheucher, P. Valtr, B. Vogtenhuber and E. Welzl, Minimal representations of order types by geometric graphs, Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019), Lecture Notes in Computer Science 11904}, 101-113, Springer, 2019. https://doi.org/10.1007/978-3-030-35802-0_8
V. Jelínek, I. Kantor, J. Kynčl and M. Tancer, On the growth of the Möbius function of permutations, Journal of Combinatorial Theory, Series A 169 (2020), 105121. https://doi.org/10.1016/j.jcta.2019.105121
J. Kynčl, Simple realizability of complete abstract topological graphs simplified, Discrete and Computational Geometry 64 (2020), Issue 1, 1-27. https://doi.org/10.1007/s00454-020-00204-0
Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell, and Nikola Jedličková.
List Homomorphism Problems for Signed Graphs. In Javier Esparza and
Daniel Kráľ, editors, 45th International Symposium on Mathematical Founda-
tions of Computer Science (MFCS 2020), volume 170 of Leibniz International
Proceedings in Informatics (LIPIcs), pages 20:1–20:14, Dagstuhl, Germany,
2020a. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISBN 978-3-95977-
159-7. doi: 10.4230/LIPIcs.MFCS.2020.20. URL https://drops.dagstuhl.
de/opus/volltexte/2020/12688.
Jan Bok, Nikola Jedličková, Barnaby Martin, Daniël Paulusma, and Siani Smith.
Acyclic, Star and Injective Colouring: A Complexity Picture for H-Free
Graphs. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, edi-
tors, 28th Annual European Symposium on Algorithms (ESA 2020), volume
173 of Leibniz International Proceedings in Informatics (LIPIcs), pages 22:1–
22:22, Dagstuhl, Germany, 2020b. Schloss Dagstuhl–Leibniz-Zentrum für In-
formatik. ISBN 978-3-95977-162-7. doi: 10.4230/LIPIcs.ESA.2020.22. URL
https://drops.dagstuhl.de/opus/volltexte/2020/12888.
K. Adiprasito, E. Nevo, M. Tancer: On Betti numbers of flag complexes with forbidden induced subgraphs. Mathematical Proceedings of the Cambridge Philosophical Society 168(3) (2020), 567-600.
A. de Mesmay, Y. Rieck, E. Sedgwick, M. Tancer: Embeddability in R^3 is NP-hard. Journal of the ACM 67(4) (2020), art. no. 20.
V. Kaluža, M. Tancer: Even maps, the Colin de Verdière number and representations of graphs. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA20).
Z. Patáková, M. Tancer, U. Wagner: Barycentric cuts through a convex body. In Proceedings of 36th International Symposium on Computational Geometry (SoCG 2020) 164 (2020), 62:1--62:16.
Karel Zimmermann: Optimization Problem under Two-sided (max,+)/(min,+) Inequality Constraints, Aplikace matematiky, Special Issue contributions of MATTRIAD 2019.
Michael Kaufmann, Jan Kratochvíl, Fabian Lipp, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Pavel Valtr:
The Stub Resolution of 1-Planar Graphs. WALCOM 2020, Lecture Notes in Computer Science 12049, Springer 2020, ISBN 978-3-030-39880-4: 170-182
Jan Kratochvíl, Tomáš Masařík, Jana Novotná:
U-Bubble Model for Mixed Unit Interval Graphs and Its Applications: The MaxCut Problem Revisited. MFCS 2020, LIPIcs 170, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2020, ISBN 978-3-95977-159-7: 57:1-57:14
Černý, Martin. "Interval matrices with Monge property." Applications of Mathematics 65.5 (2020): 619-643.
Klavík P., Knop D., Zeman P. (2020) Graph Isomorphism Restricted by Lists. In: Adler I., Müller H. (eds) Graph-Theoretic Concepts in Computer Science. WG 2020. Lecture Notes in Computer Science, vol 12301. Springer, Cham. https://doi.org/10.1007/978-3-030-60440-0_9
Evans, D., Hubička, J., Konečný, M., & Nešetřil, J. (2020). EPPA for two-graphs and antipodal metric spaces. Proceedings of the American Mathematical Society, 148(5), 1901-1915.
Hubicka, J. (2020). BIG RAMSEY DEGREES OF THE UNIVERSAL HOMOGENEOUS PARTIAL ORDER ARE FINITE. Algebras, Graphs and Ordered Sets (ALGOS 2020), 183.
T. Klimošová, J. Malík, T. Masařík, J. Novotná, D. Paulusma, V. Slívová: Colouring (P_r+P_s)-Free Graphs, Algorithmica (2020): 1-26.
T. Klimošová, D. Piguet, V. Rozhoň: A version of the Loebl-Komlós-Sós conjecture for skewed trees, European Journal of Combinatorics (2020): 103106.
Clique-Width: Harnessing the Power of Atoms (Konrad K. Dabrowski, Tomáš Masařík, Jana Novotná, Daniël Paulusma, Pawel Rzazewski), 46th International Workshop on Graph-Theoretic Concepts in Computer Science, 119-133 (WG 2020)
Vertex deletion into bipartite permutation graphs (Łukasz Bożyk, Jan Derbisz, Tomasz Krawczyk, Jana Novotná, Karolina Okrasa): International Symposium on Parameterized and Exact Computation (IPEC 2020)
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs (Jana Novotná, Karolina Okrasa, Michał Pilipczuk, Paweł Rzążewski, Erik Jan van Leeuwen, Bartosz Walczak ): Algorithmica, Available online on 31 July 2020.
Elif Garajová, Miroslav Rada, and Milan Hladík. Outcome Range Problem in Interval Linear Programming: An Exact Approach. In Integrated Uncertainty in Knowledge Modelling and Decision Making, International Symposium IUKM 2020. Conference Proceedings, Lecture Notes in Artificial Intelligence.
Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher, Patrick Schnider, Raphael Steiner, Pavel Valtr: On the Average Complexity of the k-Level. Journal of Computational Geometry 11(1), pages 493-506, 2020
Wolfgang Mulzer, Pavel Valtr: Long Alternating Paths Exist, Proceedings of the 36th International Symposium on Computational Geometry (SoCG 2020), pages 57:1-57:16, LIPIcs 164, Dagstuhl, 2020.
Jaroslav Hančl Jr.: Complementary Schur asymptotics for partitions, Discrete Mathematics, 343(12), 2020
Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, Thomas Zeume: Dynamic Complexity of Reachability: How Many Changes Can We Handle? ICALP 2020
Julien Baste, Michael R. Fellows, Lars Jaffke, Tomáš Masařík,
Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond:
Diversity of Solutions: An Exploration Through the Lens of
Fixed-Parameter Tractability Theory. IJCAI 2020: 1119-1125
Zdeněk Dvořák, Tomáš Masařík, Jan Musílek, Ondřej Pangrác:
Flexibility of planar graphs of girth at least six. J. Graph Theory
95(3): 457-466 (2020)
Zdeněk Dvořák, Tomáš Masařík, Jan Musílek, Ondřej Pangrác:
Flexibility of triangle-free planar graphs. J. Graph Theory (2020)
Jinha Kim, Ryan R. Martin, Tomáš Masařík, Warren Shull, Heather C.
Smith, Andrew J. Uzzell, Zhiyu Wang:
On difference graphs and the local dimension of posets. Eur. J. Comb.