LIPIcs, Volume 170
MFCS 2020, August 24-28, 2020, Prague, Czech Republic
Editors: Javier Esparza and Daniel Král'
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Marcin Briański, Martin Koutecký, Daniel Král', Kristýna Pekárková, and Felix Schröder. Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 29:1-29:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{brianski_et_al:LIPIcs.ICALP.2022.29, author = {Bria\'{n}ski, Marcin and Kouteck\'{y}, Martin and Kr\'{a}l', Daniel and Pek\'{a}rkov\'{a}, Krist\'{y}na and Schr\"{o}der, Felix}, title = {{Characterization of Matrices with Bounded Graver Bases and Depth Parameters and Applications to Integer Programming}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {29:1--29:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.29}, URN = {urn:nbn:de:0030-drops-163702}, doi = {10.4230/LIPIcs.ICALP.2022.29}, annote = {Keywords: Integer programming, width parameters, matroids, Graver basis, tree-depth, fixed parameter tractability} }
Published in: Dagstuhl Reports, Volume 11, Issue 8 (2022)
Daniel Král’, Michał Pilipczuk, Sebastian Siebertz, and Blair D. Sullivan. Sparsity in Algorithms, Combinatorics and Logic (Dagstuhl Seminar 21391). In Dagstuhl Reports, Volume 11, Issue 8, pp. 115-128, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@Article{kral'_et_al:DagRep.11.8.115, author = {Kr\'{a}l’, Daniel and Pilipczuk, Micha{\l} and Siebertz, Sebastian and Sullivan, Blair D.}, title = {{Sparsity in Algorithms, Combinatorics and Logic (Dagstuhl Seminar 21391)}}, pages = {115--128}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {11}, number = {8}, editor = {Kr\'{a}l’, Daniel and Pilipczuk, Micha{\l} and Siebertz, Sebastian and Sullivan, Blair D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.8.115}, URN = {urn:nbn:de:0030-drops-157718}, doi = {10.4230/DagRep.11.8.115}, annote = {Keywords: Algorithm design, Parameterised complexity, Sparse graphs, Graph decompositions, Model theory} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Javier Esparza and Daniel Král'. LIPIcs, Volume 170, MFCS 2020, Complete Volume. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 1-1216, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@Proceedings{esparza_et_al:LIPIcs.MFCS.2020, title = {{LIPIcs, Volume 170, MFCS 2020, Complete Volume}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {1--1216}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020}, URN = {urn:nbn:de:0030-drops-126703}, doi = {10.4230/LIPIcs.MFCS.2020}, annote = {Keywords: LIPIcs, Volume 170, MFCS 2020, Complete Volume} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Javier Esparza and Daniel Král'. Front Matter, Table of Contents, Preface, Conference Organization. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 0:i-0:xviii, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{esparza_et_al:LIPIcs.MFCS.2020.0, author = {Esparza, Javier and Kr\'{a}l', Daniel}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {0:i--0:xviii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-159-7}, ISSN = {1868-8969}, year = {2020}, volume = {170}, editor = {Esparza, Javier and Kr\'{a}l', Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.0}, URN = {urn:nbn:de:0030-drops-126714}, doi = {10.4230/LIPIcs.MFCS.2020.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Timothy F. N. Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král', and Kristýna Pekárková. Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 26:1-26:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chan_et_al:LIPIcs.ICALP.2020.26, author = {Chan, Timothy F. N. and Cooper, Jacob W. and Kouteck\'{y}, Martin and Kr\'{a}l', Daniel and Pek\'{a}rkov\'{a}, Krist\'{y}na}, title = {{Matrices of Optimal Tree-Depth and Row-Invariant Parameterized Algorithm for Integer Programming}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {26:1--26:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-138-2}, ISSN = {1868-8969}, year = {2020}, volume = {168}, editor = {Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.26}, URN = {urn:nbn:de:0030-drops-124339}, doi = {10.4230/LIPIcs.ICALP.2020.26}, annote = {Keywords: Matroid algorithms, width parameters, integer programming, fixed parameter tractability, branch-width, branch-depth} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Carl Einarson and Felix Reidl. Domination Above r-Independence: Does Sparseness Help?. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 40:1-40:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{einarson_et_al:LIPIcs.MFCS.2019.40, author = {Einarson, Carl and Reidl, Felix}, title = {{Domination Above r-Independence: Does Sparseness Help?}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {40:1--40:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.40}, URN = {urn:nbn:de:0030-drops-109840}, doi = {10.4230/LIPIcs.MFCS.2019.40}, annote = {Keywords: Dominating Set, Above Guarantee, Kernel, Bounded Expansion, Nowhere Dense} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Andrei A. Bulatov and Stanislav Živný. Approximate Counting CSP Seen from the Other Side. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 60:1-60:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bulatov_et_al:LIPIcs.MFCS.2019.60, author = {Bulatov, Andrei A. and \v{Z}ivn\'{y}, Stanislav}, title = {{Approximate Counting CSP Seen from the Other Side}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {60:1--60:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.60}, URN = {urn:nbn:de:0030-drops-110041}, doi = {10.4230/LIPIcs.MFCS.2019.60}, annote = {Keywords: constraint satisfaction, approximate counting, homomorphisms} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Barnaby Martin, Daniël Paulusma, and Siani Smith. Colouring H-Free Graphs of Bounded Diameter. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{martin_et_al:LIPIcs.MFCS.2019.14, author = {Martin, Barnaby and Paulusma, Dani\"{e}l and Smith, Siani}, title = {{Colouring H-Free Graphs of Bounded Diameter}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {14:1--14:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.14}, URN = {urn:nbn:de:0030-drops-109584}, doi = {10.4230/LIPIcs.MFCS.2019.14}, annote = {Keywords: vertex colouring, H-free graph, diameter} }
Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Jakub Gajarský and Daniel Král'. Recovering Sparse Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 29:1-29:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{gajarsky_et_al:LIPIcs.MFCS.2018.29, author = {Gajarsk\'{y}, Jakub and Kr\'{a}l', Daniel}, title = {{Recovering Sparse Graphs}}, booktitle = {43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)}, pages = {29:1--29:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-086-6}, ISSN = {1868-8969}, year = {2018}, volume = {117}, editor = {Potapov, Igor and Spirakis, Paul and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.29}, URN = {urn:nbn:de:0030-drops-96111}, doi = {10.4230/LIPIcs.MFCS.2018.29}, annote = {Keywords: model checking, degenerate graphs, interpretations, bounded expansion} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Zdenek Dvorák, Daniel Král, and Bojan Mohar. Graphic TSP in Cubic Graphs. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 27:1-27:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{dvorak_et_al:LIPIcs.STACS.2017.27, author = {Dvor\'{a}k, Zdenek and Kr\'{a}l, Daniel and Mohar, Bojan}, title = {{Graphic TSP in Cubic Graphs}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {27:1--27:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.27}, URN = {urn:nbn:de:0030-drops-70068}, doi = {10.4230/LIPIcs.STACS.2017.27}, annote = {Keywords: Graphic TSP, approximation algorithms, cubic graphs} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Pascal Schweitzer. Towards an Isomorphism Dichotomy for Hereditary Graph Classes. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 689-702, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{schweitzer:LIPIcs.STACS.2015.689, author = {Schweitzer, Pascal}, title = {{Towards an Isomorphism Dichotomy for Hereditary Graph Classes}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {689--702}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.689}, URN = {urn:nbn:de:0030-drops-49513}, doi = {10.4230/LIPIcs.STACS.2015.689}, annote = {Keywords: graph isomorphism, modular decomposition, bounded color valence, reductions, forbidden induced subgraphs} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Hu Fu and Robert Kleinberg. Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 669-676, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{fu_et_al:LIPIcs.APPROX-RANDOM.2014.669, author = {Fu, Hu and Kleinberg, Robert}, title = {{Improved Lower Bounds for Testing Triangle-freeness in Boolean Functions via Fast Matrix Multiplication}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {669--676}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.669}, URN = {urn:nbn:de:0030-drops-47304}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.669}, annote = {Keywords: Property testing, linear invariance, fast matrix multiplication, uniquely solvable puzzles} }
Feedback for Dagstuhl Publishing