Published in: LIPIcs, Volume 233, 20th International Symposium on Experimental Algorithms (SEA 2022)
Vasily Alferov and Mateus de Oliveira Oliveira. On the Satisfiability of Smooth Grid CSPs. In 20th International Symposium on Experimental Algorithms (SEA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 233, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{alferov_et_al:LIPIcs.SEA.2022.18, author = {Alferov, Vasily and de Oliveira Oliveira, Mateus}, title = {{On the Satisfiability of Smooth Grid CSPs}}, booktitle = {20th International Symposium on Experimental Algorithms (SEA 2022)}, pages = {18:1--18:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-251-8}, ISSN = {1868-8969}, year = {2022}, volume = {233}, editor = {Schulz, Christian and U\c{c}ar, Bora}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2022.18}, URN = {urn:nbn:de:0030-drops-165526}, doi = {10.4230/LIPIcs.SEA.2022.18}, annote = {Keywords: Grid CSPs, Smoothness, SAT Solving, Linear Programming} }
Published in: LIPIcs, Volume 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismaël Jecker, Mateus de Oliveira Oliveira, and Petra Wolf. On the Complexity of Intersection Non-emptiness for Star-Free Language Classes. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arrighi_et_al:LIPIcs.FSTTCS.2021.34, author = {Arrighi, Emmanuel and Fernau, Henning and Hoffmann, Stefan and Holzer, Markus and Jecker, Isma\"{e}l and de Oliveira Oliveira, Mateus and Wolf, Petra}, title = {{On the Complexity of Intersection Non-emptiness for Star-Free Language Classes}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {34:1--34:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-215-0}, ISSN = {1868-8969}, year = {2021}, volume = {213}, editor = {Boja\'{n}czyk, Miko{\l}aj and Chekuri, Chandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2021.34}, URN = {urn:nbn:de:0030-drops-155456}, doi = {10.4230/LIPIcs.FSTTCS.2021.34}, annote = {Keywords: Intersection Non-emptiness Problem, Star-Free Languages, Straubing-Th\'{e}rien Hierarchy, dot-depth Hierarchy, Commutative Languages, Complexity} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, and Petra Wolf. Order Reconfiguration Under Width Constraints. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arrighi_et_al:LIPIcs.MFCS.2021.8, author = {Arrighi, Emmanuel and Fernau, Henning and de Oliveira Oliveira, Mateus and Wolf, Petra}, title = {{Order Reconfiguration Under Width Constraints}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {8:1--8:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.8}, URN = {urn:nbn:de:0030-drops-144486}, doi = {10.4230/LIPIcs.MFCS.2021.8}, annote = {Keywords: Parameterized Complexity, Order Reconfiguration, String Rewriting Systems} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Gabriel L. Duarte, Mateus de Oliveira Oliveira, and Uéverton S. Souza. Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 42:1-42:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{duarte_et_al:LIPIcs.MFCS.2021.42, author = {Duarte, Gabriel L. and de Oliveira Oliveira, Mateus and Souza, U\'{e}verton S.}, title = {{Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {42:1--42:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.42}, URN = {urn:nbn:de:0030-drops-144828}, doi = {10.4230/LIPIcs.MFCS.2021.42}, annote = {Keywords: FPT, treewidth, degeneracy, complement graph, Bondy-Chv\'{a}tal closure} }
Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)
Emmanuel Arrighi and Mateus de Oliveira Oliveira. Three Is Enough for Steiner Trees. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 5:1-5:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{arrighi_et_al:LIPIcs.SEA.2021.5, author = {Arrighi, Emmanuel and de Oliveira Oliveira, Mateus}, title = {{Three Is Enough for Steiner Trees}}, booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)}, pages = {5:1--5:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-185-6}, ISSN = {1868-8969}, year = {2021}, volume = {190}, editor = {Coudert, David and Natale, Emanuele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.5}, URN = {urn:nbn:de:0030-drops-137775}, doi = {10.4230/LIPIcs.SEA.2021.5}, annote = {Keywords: Steiner Tree, Heuristics, 3TST} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, and Petra Wolf. Width Notions for Ordering-Related Problems. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 9:1-9:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{arrighi_et_al:LIPIcs.FSTTCS.2020.9, author = {Arrighi, Emmanuel and Fernau, Henning and de Oliveira Oliveira, Mateus and Wolf, Petra}, title = {{Width Notions for Ordering-Related Problems}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {9:1--9:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.9}, URN = {urn:nbn:de:0030-drops-132505}, doi = {10.4230/LIPIcs.FSTTCS.2020.9}, annote = {Keywords: Parameterized algorithms, interval width, linear extension, one-sided crossing minimization, Kemeny rank aggregation, grouping by swapping} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Lars Jaffke, Mateus de Oliveira Oliveira, and Hans Raj Tiwary. Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{jaffke_et_al:LIPIcs.MFCS.2020.50, author = {Jaffke, Lars and de Oliveira Oliveira, Mateus and Tiwary, Hans Raj}, title = {{Compressing Permutation Groups into Grammars and Polytopes. A Graph Embedding Approach}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {50:1--50:15}, 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.50}, URN = {urn:nbn:de:0030-drops-127161}, doi = {10.4230/LIPIcs.MFCS.2020.50}, annote = {Keywords: Permutation Groups, Context Free Grammars, Extension Complexity, Graph Embedding Complexity} }
Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Daniel Lokshtanov, Mateus de Oliveira Oliveira, and Saket Saurabh. A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 25:1-25:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lokshtanov_et_al:LIPIcs.IPEC.2018.25, author = {Lokshtanov, Daniel and de Oliveira Oliveira, Mateus and Saurabh, Saket}, title = {{A Strongly-Uniform Slicewise Polynomial-Time Algorithm for the Embedded Planar Diameter Improvement Problem}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {25:1--25:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-084-2}, ISSN = {1868-8969}, year = {2019}, volume = {115}, editor = {Paul, Christophe and Pilipczuk, Michal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.25}, URN = {urn:nbn:de:0030-drops-102265}, doi = {10.4230/LIPIcs.IPEC.2018.25}, annote = {Keywords: Embedded Planar Diameter Improvement, Constructive Algorithms, Nooses} }
Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)
Mateus de Oliveira Oliveira. On Supergraphs Satisfying CMSO Properties. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{deoliveiraoliveira:LIPIcs.CSL.2017.33, author = {de Oliveira Oliveira, Mateus}, title = {{On Supergraphs Satisfying CMSO Properties}}, booktitle = {26th EACSL Annual Conference on Computer Science Logic (CSL 2017)}, pages = {33:1--33:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-045-3}, ISSN = {1868-8969}, year = {2017}, volume = {82}, editor = {Goranko, Valentin and Dam, Mads}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.33}, URN = {urn:nbn:de:0030-drops-77058}, doi = {10.4230/LIPIcs.CSL.2017.33}, annote = {Keywords: On Supergraphs Satisfying CMSO Properties} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Mateus de Oliveira Oliveira and Pavel Pudlák. Representations of Monotone Boolean Functions by Linear Programs. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{deoliveiraoliveira_et_al:LIPIcs.CCC.2017.3, author = {de Oliveira Oliveira, Mateus and Pudl\'{a}k, Pavel}, title = {{Representations of Monotone Boolean Functions by Linear Programs}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {3:1--3:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.3}, URN = {urn:nbn:de:0030-drops-75200}, doi = {10.4230/LIPIcs.CCC.2017.3}, annote = {Keywords: Monotone Linear Programming Circuits, Lov\'{a}sz-Schrijver Proof System, Cutting-Planes Proof System, Feasible Interpolation, Lower Bounds} }
Published in: LIPIcs, Volume 78, 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
Christian Komusiewicz, Mateus de Oliveira Oliveira, and Meirav Zehavi. Revisiting the Parameterized Complexity of Maximum-Duo Preservation String Mapping. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 78, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{komusiewicz_et_al:LIPIcs.CPM.2017.11, author = {Komusiewicz, Christian and de Oliveira Oliveira, Mateus and Zehavi, Meirav}, title = {{Revisiting the Parameterized Complexity of Maximum-Duo Preservation String Mapping}}, booktitle = {28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)}, pages = {11:1--11:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-039-2}, ISSN = {1868-8969}, year = {2017}, volume = {78}, editor = {K\"{a}rkk\"{a}inen, Juha and Radoszewski, Jakub and Rytter, Wojciech}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2017.11}, URN = {urn:nbn:de:0030-drops-73436}, doi = {10.4230/LIPIcs.CPM.2017.11}, annote = {Keywords: comparative genomics, parameterized complexity, kernelization} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Mateus de Oliveira Oliveira. Ground Reachability and Joinability in Linear Term Rewriting Systems are Fixed Parameter Tractable with Respect to Depth. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 25:1-25:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{deoliveiraoliveira:LIPIcs.IPEC.2016.25, author = {de Oliveira Oliveira, Mateus}, title = {{Ground Reachability and Joinability in Linear Term Rewriting Systems are Fixed Parameter Tractable with Respect to Depth}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {25:1--25:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.25}, URN = {urn:nbn:de:0030-drops-69256}, doi = {10.4230/LIPIcs.IPEC.2016.25}, annote = {Keywords: Linear Term Rewriting Systems, Ground Reachability, Ground Joinability, Fixed Parameter Tractability} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Mateus de Oliveira Oliveira. Size-Treewidth Tradeoffs for Circuits Computing the Element Distinctness Function. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{deoliveiraoliveira:LIPIcs.STACS.2016.56, author = {de Oliveira Oliveira, Mateus}, title = {{Size-Treewidth Tradeoffs for Circuits Computing the Element Distinctness Function}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {56:1--56:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-001-9}, ISSN = {1868-8969}, year = {2016}, volume = {47}, editor = {Ollinger, Nicolas and Vollmer, Heribert}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.56}, URN = {urn:nbn:de:0030-drops-57571}, doi = {10.4230/LIPIcs.STACS.2016.56}, annote = {Keywords: non-linear lower bounds, treewidth, element distinctness} }
Feedback for Dagstuhl Publishing