Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)
Jonas Lill, Kalina Petrova, and Simon Weber. Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turzík Bound. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lill_et_al:LIPIcs.IPEC.2024.2, author = {Lill, Jonas and Petrova, Kalina and Weber, Simon}, title = {{Linear-Time MaxCut in Multigraphs Parameterized Above the Poljak-Turz{\'\i}k Bound}}, booktitle = {19th International Symposium on Parameterized and Exact Computation (IPEC 2024)}, pages = {2:1--2:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-353-9}, ISSN = {1868-8969}, year = {2024}, volume = {321}, editor = {Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.2}, URN = {urn:nbn:de:0030-drops-222282}, doi = {10.4230/LIPIcs.IPEC.2024.2}, annote = {Keywords: Fixed-parameter tractability, maximum cut, Edwards-Erd\H{o}s bound, Poljak-Turz{\'\i}k bound, multigraphs, integer-weighted graphs} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Michaela Borzechowski, John Fearnley, Spencer Gordon, Rahul Savani, Patrick Schnider, and Simon Weber. Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{borzechowski_et_al:LIPIcs.ICALP.2024.32, author = {Borzechowski, Michaela and Fearnley, John and Gordon, Spencer and Savani, Rahul and Schnider, Patrick and Weber, Simon}, title = {{Two Choices Are Enough for P-LCPs, USOs, and Colorful Tangents}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {32:1--32:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.32}, URN = {urn:nbn:de:0030-drops-201751}, doi = {10.4230/LIPIcs.ICALP.2024.32}, annote = {Keywords: P-LCP, Unique Sink Orientation, \alpha-Ham Sandwich, search complexity, TFNP, UEOPL} }
Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)
Patrick Schnider and Simon Weber. A Topological Version of Schaefer’s Dichotomy Theorem. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 77:1-77:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{schnider_et_al:LIPIcs.SoCG.2024.77, author = {Schnider, Patrick and Weber, Simon}, title = {{A Topological Version of Schaefer’s Dichotomy Theorem}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {77:1--77:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-316-4}, ISSN = {1868-8969}, year = {2024}, volume = {293}, editor = {Mulzer, Wolfgang and Phillips, Jeff M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.77}, URN = {urn:nbn:de:0030-drops-200220}, doi = {10.4230/LIPIcs.SoCG.2024.77}, annote = {Keywords: Computational topology, Boolean CSP, satisfiability, computational complexity, solution space, homotopy universality, homological connectivity} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Michaela Borzechowski, Patrick Schnider, and Simon Weber. An FPT Algorithm for Splitting a Necklace Among Two Thieves. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{borzechowski_et_al:LIPIcs.ISAAC.2023.15, author = {Borzechowski, Michaela and Schnider, Patrick and Weber, Simon}, title = {{An FPT Algorithm for Splitting a Necklace Among Two Thieves}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {15:1--15:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.15}, URN = {urn:nbn:de:0030-drops-193178}, doi = {10.4230/LIPIcs.ISAAC.2023.15}, annote = {Keywords: Necklace splitting, n-separability, well-separation, ham sandwich, FPT} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, and Emo Welzl. On Connectivity in Random Graph Models with Limited Dependencies. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 30:1-30:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{lengler_et_al:LIPIcs.APPROX/RANDOM.2023.30, author = {Lengler, Johannes and Martinsson, Anders and Petrova, Kalina and Schnider, Patrick and Steiner, Raphael and Weber, Simon and Welzl, Emo}, title = {{On Connectivity in Random Graph Models with Limited Dependencies}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {30:1--30:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.30}, URN = {urn:nbn:de:0030-drops-188556}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.30}, annote = {Keywords: Random Graphs, Independence, Dependency, Connectivity, Threshold, Probabilistic Method} }
Feedback for Dagstuhl Publishing