Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Jan Dreier, Sebastian Ordyniak, and Stefan Szeider. SAT Backdoors: Depth Beats Size. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 46:1-46:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{dreier_et_al:LIPIcs.ESA.2022.46, author = {Dreier, Jan and Ordyniak, Sebastian and Szeider, Stefan}, title = {{SAT Backdoors: Depth Beats Size}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {46:1--46:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.46}, URN = {urn:nbn:de:0030-drops-169840}, doi = {10.4230/LIPIcs.ESA.2022.46}, annote = {Keywords: satisfiability, backdoor (depth)} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Eduard Eiben, Robert Ganian, Iyad Kanj, Sebastian Ordyniak, and Stefan Szeider. Finding a Cluster in Incomplete Data. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 47:1-47:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{eiben_et_al:LIPIcs.ESA.2022.47, author = {Eiben, Eduard and Ganian, Robert and Kanj, Iyad and Ordyniak, Sebastian and Szeider, Stefan}, title = {{Finding a Cluster in Incomplete Data}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {47:1--47:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.47}, URN = {urn:nbn:de:0030-drops-169858}, doi = {10.4230/LIPIcs.ESA.2022.47}, annote = {Keywords: Parameterized complexity, incomplete data, clustering} }
Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)
Jan Dreier, Sebastian Ordyniak, and Stefan Szeider. CSP Beyond Tractable Constraint Languages. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 20:1-20:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{dreier_et_al:LIPIcs.CP.2022.20, author = {Dreier, Jan and Ordyniak, Sebastian and Szeider, Stefan}, title = {{CSP Beyond Tractable Constraint Languages}}, booktitle = {28th International Conference on Principles and Practice of Constraint Programming (CP 2022)}, pages = {20:1--20:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-240-2}, ISSN = {1868-8969}, year = {2022}, volume = {235}, editor = {Solnon, Christine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.20}, URN = {urn:nbn:de:0030-drops-166490}, doi = {10.4230/LIPIcs.CP.2022.20}, annote = {Keywords: CSP, backdoor depth, constraint language, tractable class, recursive backdoor} }
Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)
Peter Jonsson, Victor Lagerkvist, and Sebastian Ordyniak. Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 32:1-32:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{jonsson_et_al:LIPIcs.CP.2021.32, author = {Jonsson, Peter and Lagerkvist, Victor and Ordyniak, Sebastian}, title = {{Reasoning Short Cuts in Infinite Domain Constraint Satisfaction: Algorithms and Lower Bounds for Backdoors}}, booktitle = {27th International Conference on Principles and Practice of Constraint Programming (CP 2021)}, pages = {32:1--32:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-211-2}, ISSN = {1868-8969}, year = {2021}, volume = {210}, editor = {Michel, Laurent D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.32}, URN = {urn:nbn:de:0030-drops-153238}, doi = {10.4230/LIPIcs.CP.2021.32}, annote = {Keywords: Constraint Satisfaction Problems, Parameterised Complexity, Backdoors} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Gregory Gutin, Diptapriyo Majumdar, Sebastian Ordyniak, and Magnus Wahlström. Parameterized Pre-Coloring Extension and List Coloring Problems. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 19:1-19:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{gutin_et_al:LIPIcs.STACS.2020.19, author = {Gutin, Gregory and Majumdar, Diptapriyo and Ordyniak, Sebastian and Wahlstr\"{o}m, Magnus}, title = {{Parameterized Pre-Coloring Extension and List Coloring Problems}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {19:1--19:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.19}, URN = {urn:nbn:de:0030-drops-118801}, doi = {10.4230/LIPIcs.STACS.2020.19}, annote = {Keywords: Parameterized Algorithms, W-hardness, Kernelization, Graph Coloring, List Coloring} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Robert Ganian, Sebastian Ordyniak, and C. S. Rahul. Group Activity Selection with Few Agent Types. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 48:1-48:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{ganian_et_al:LIPIcs.ESA.2019.48, author = {Ganian, Robert and Ordyniak, Sebastian and Rahul, C. S.}, title = {{Group Activity Selection with Few Agent Types}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {48:1--48:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.48}, URN = {urn:nbn:de:0030-drops-111693}, doi = {10.4230/LIPIcs.ESA.2019.48}, annote = {Keywords: group activity selection problem, parameterized complexity analysis, multi-agent systems} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Eduard Eiben, Robert Ganian, and Sebastian Ordyniak. Small Resolution Proofs for QBF using Dependency Treewidth. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 28:1-28:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{eiben_et_al:LIPIcs.STACS.2018.28, author = {Eiben, Eduard and Ganian, Robert and Ordyniak, Sebastian}, title = {{Small Resolution Proofs for QBF using Dependency Treewidth}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {28:1--28:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf 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.2018.28}, URN = {urn:nbn:de:0030-drops-85135}, doi = {10.4230/LIPIcs.STACS.2018.28}, annote = {Keywords: QBF, treewidth, fixed parameter tractability, dependency schemes} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 33:1-33:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{ganian_et_al:LIPIcs.STACS.2018.33, author = {Ganian, Robert and Klute, Fabian and Ordyniak, Sebastian}, title = {{On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {33:1--33:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf 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.2018.33}, URN = {urn:nbn:de:0030-drops-85140}, doi = {10.4230/LIPIcs.STACS.2018.33}, annote = {Keywords: bounded-degree vertex deletion, feedback vertex set, parameterized algorithms, treecut width} }
Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Robert Ganian, Sebastian Ordyniak, and Ramanujan Sridharan. On Structural Parameterizations of the Edge Disjoint Paths Problem. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 36:1-36:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{ganian_et_al:LIPIcs.ISAAC.2017.36, author = {Ganian, Robert and Ordyniak, Sebastian and Sridharan, Ramanujan}, title = {{On Structural Parameterizations of the Edge Disjoint Paths Problem}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {36:1--36:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.36}, URN = {urn:nbn:de:0030-drops-82555}, doi = {10.4230/LIPIcs.ISAAC.2017.36}, annote = {Keywords: edge disjoint path problem, feedback vertex set, treewidth, fracture number, parameterized complexity} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. Towards a Polynomial Kernel for Directed Feedback Vertex Set. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 36:1-36:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{bergougnoux_et_al:LIPIcs.MFCS.2017.36, author = {Bergougnoux, Benjamin and Eiben, Eduard and Ganian, Robert and Ordyniak, Sebastian and Ramanujan, M. S.}, title = {{Towards a Polynomial Kernel for Directed Feedback Vertex Set}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {36:1--36:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-046-0}, ISSN = {1868-8969}, year = {2017}, volume = {83}, editor = {Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.36}, URN = {urn:nbn:de:0030-drops-81126}, doi = {10.4230/LIPIcs.MFCS.2017.36}, annote = {Keywords: parameterized algorithms, kernelization, (directed) feedback vertex set} }
Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)
Serge Gaspers, Sebastian Ordyniak, and Stefan Szeider. Backdoor Sets for CSP. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 137-157, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InCollection{gaspers_et_al:DFU.Vol7.15301.137, author = {Gaspers, Serge and Ordyniak, Sebastian and Szeider, Stefan}, title = {{Backdoor Sets for CSP}}, booktitle = {The Constraint Satisfaction Problem: Complexity and Approximability}, pages = {137--157}, series = {Dagstuhl Follow-Ups}, ISBN = {978-3-95977-003-3}, ISSN = {1868-8977}, year = {2017}, volume = {7}, editor = {Krokhin, Andrei and Zivny, Stanislav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.137}, URN = {urn:nbn:de:0030-drops-69626}, doi = {10.4230/DFU.Vol7.15301.137}, annote = {Keywords: Backdoor sets, Constraint satisfaction problems, Parameterized complexity, Polymorphisms} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Arne Meier, Sebastian Ordyniak, Ramanujan Sridharan, and Irena Schindler. Backdoors for Linear Temporal Logic. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 23:1-23:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{meier_et_al:LIPIcs.IPEC.2016.23, author = {Meier, Arne and Ordyniak, Sebastian and Sridharan, Ramanujan and Schindler, Irena}, title = {{Backdoors for Linear Temporal Logic}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {23:1--23:17}, 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.23}, URN = {urn:nbn:de:0030-drops-69462}, doi = {10.4230/LIPIcs.IPEC.2016.23}, annote = {Keywords: Linear Temporal Logic, Parameterized Complexity, Backdoor Sets} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Robert Ganian, N. S. Narayanaswamy, Sebastian Ordyniak, C. S. Rahul, and M. S. Ramanujan. On the Complexity Landscape of Connected f-Factor Problems. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 41:1-41:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{ganian_et_al:LIPIcs.MFCS.2016.41, author = {Ganian, Robert and Narayanaswamy, N. S. and Ordyniak, Sebastian and Rahul, C. S. and Ramanujan, M. S.}, title = {{On the Complexity Landscape of Connected f-Factor Problems}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {41:1--41:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.41}, URN = {urn:nbn:de:0030-drops-65013}, doi = {10.4230/LIPIcs.MFCS.2016.41}, annote = {Keywords: f-factors, connected f-factors, quasi-polynomial time algorithms, randomized algorithms} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Eduard Eiben, Robert Ganian, Kustaa Kangas, and Sebastian Ordyniak. Counting Linear Extensions: Parameterizations by Treewidth. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 39:1-39:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{eiben_et_al:LIPIcs.ESA.2016.39, author = {Eiben, Eduard and Ganian, Robert and Kangas, Kustaa and Ordyniak, Sebastian}, title = {{Counting Linear Extensions: Parameterizations by Treewidth}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {39:1--39:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.39}, URN = {urn:nbn:de:0030-drops-63903}, doi = {10.4230/LIPIcs.ESA.2016.39}, annote = {Keywords: Partially ordered sets, Linear extensions, Parameterized Complexity, Structural parameters, Treewidth} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Serge Gaspers, Sebastian Ordyniak, M. S. Ramanujan, Saket Saurabh, and Stefan Szeider. Backdoors to q-Horn. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 67-79, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2013)
@InProceedings{gaspers_et_al:LIPIcs.STACS.2013.67, author = {Gaspers, Serge and Ordyniak, Sebastian and Ramanujan, M. S. and Saurabh, Saket and Szeider, Stefan}, title = {{Backdoors to q-Horn}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {67--79}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.67}, URN = {urn:nbn:de:0030-drops-39236}, doi = {10.4230/LIPIcs.STACS.2013.67}, annote = {Keywords: Algorithms and data structures, Backdoor sets, Satisfiability, Fixed Parameter Tractability} }
Feedback for Dagstuhl Publishing