Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Approximating Long Cycle Above Dirac’s Guarantee. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 60:1-60:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{fomin_et_al:LIPIcs.ICALP.2023.60, author = {Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill}, title = {{Approximating Long Cycle Above Dirac’s Guarantee}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {60:1--60:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.60}, URN = {urn:nbn:de:0030-drops-181128}, doi = {10.4230/LIPIcs.ICALP.2023.60}, annote = {Keywords: Longest path, longest cycle, approximation algorithms, above guarantee parameterization, minimum degree, Dirac theorem} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Longest Cycle Above Erdős-Gallai Bound. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 55:1-55:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{fomin_et_al:LIPIcs.ESA.2022.55, author = {Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill}, title = {{Longest Cycle Above Erd\H{o}s-Gallai Bound}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {55:1--55:15}, 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.55}, URN = {urn:nbn:de:0030-drops-169935}, doi = {10.4230/LIPIcs.ESA.2022.55}, annote = {Keywords: Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization, average degree, Erd\H{o}s and Gallai theorem} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Fedor V. Fomin, Petr A. Golovach, Danil Sagunov, and Kirill Simonov. Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms (Invited Talk). In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 1:1-1:4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{fomin_et_al:LIPIcs.MFCS.2022.1, author = {Fomin, Fedor V. and Golovach, Petr A. and Sagunov, Danil and Simonov, Kirill}, title = {{Long Cycles in Graphs: Extremal Combinatorics Meets Parameterized Algorithms}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {1:1--1:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.1}, URN = {urn:nbn:de:0030-drops-167999}, doi = {10.4230/LIPIcs.MFCS.2022.1}, annote = {Keywords: Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization, average degree, dense graph, Dirac theorem, Erd\H{o}s-Gallai theorem} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Fedor V. Fomin, Petr A. Golovach, William Lochet, Danil Sagunov, Kirill Simonov, and Saket Saurabh. Detours in Directed Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 29:1-29:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{fomin_et_al:LIPIcs.STACS.2022.29, author = {Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Sagunov, Danil and Simonov, Kirill and Saurabh, Saket}, title = {{Detours in Directed Graphs}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {29:1--29:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.29}, URN = {urn:nbn:de:0030-drops-158390}, doi = {10.4230/LIPIcs.STACS.2022.29}, annote = {Keywords: longest path, longest detour, diameter, directed graphs, parameterized complexity} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Dmitry Itsykson and Artur Riazanov. Proof Complexity of Natural Formulas via Communication Arguments. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 3:1-3:34, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{itsykson_et_al:LIPIcs.CCC.2021.3, author = {Itsykson, Dmitry and Riazanov, Artur}, title = {{Proof Complexity of Natural Formulas via Communication Arguments}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {3:1--3:34}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.3}, URN = {urn:nbn:de:0030-drops-142773}, doi = {10.4230/LIPIcs.CCC.2021.3}, annote = {Keywords: bit pigeonhole principle, disjointness, multiparty communication complexity, perfect matching, proof complexity, randomized communication complexity, Resolution over linear equations, tree-like proofs} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Fedor V. Fomin, Petr A. Golovach, Lars Jaffke, Geevarghese Philip, and Danil Sagunov. Diverse Pairs of Matchings. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 26:1-26:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.ISAAC.2020.26, author = {Fomin, Fedor V. and Golovach, Petr A. and Jaffke, Lars and Philip, Geevarghese and Sagunov, Danil}, title = {{Diverse Pairs of Matchings}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {26:1--26:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.26}, URN = {urn:nbn:de:0030-drops-133706}, doi = {10.4230/LIPIcs.ISAAC.2020.26}, annote = {Keywords: Matching, Solution Diversity, Fixed-Parameter Tractability} }
Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Fedor V. Fomin, Danil Sagunov, and Kirill Simonov. Building Large k-Cores from Sparse Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 35:1-35:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.MFCS.2020.35, author = {Fomin, Fedor V. and Sagunov, Danil and Simonov, Kirill}, title = {{Building Large k-Cores from Sparse Graphs}}, booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)}, pages = {35:1--35:14}, 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.35}, URN = {urn:nbn:de:0030-drops-127026}, doi = {10.4230/LIPIcs.MFCS.2020.35}, annote = {Keywords: parameterized complexity, k-core, vertex cover, treewidth} }
Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Ivan Bliznets and Danil Sagunov. Solving Target Set Selection with Bounded Thresholds Faster than 2^n. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 22:1-22:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{bliznets_et_al:LIPIcs.IPEC.2018.22, author = {Bliznets, Ivan and Sagunov, Danil}, title = {{Solving Target Set Selection with Bounded Thresholds Faster than 2^n}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {22:1--22:14}, 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.22}, URN = {urn:nbn:de:0030-drops-102235}, doi = {10.4230/LIPIcs.IPEC.2018.22}, annote = {Keywords: exact exponential algorithms, target set, vertex thresholds, social influence, irreversible conversions of graphs, bootstrap percolation} }
Feedback for Dagstuhl Publishing