Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)
Matthias Bentert, Fedor V. Fomin, Fanny Hauser, and Saket Saurabh. The Parameterized Complexity Landscape of Two-Sets Cut-Uncut. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 14:1-14:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bentert_et_al:LIPIcs.IPEC.2024.14, author = {Bentert, Matthias and Fomin, Fedor V. and Hauser, Fanny and Saurabh, Saket}, title = {{The Parameterized Complexity Landscape of Two-Sets Cut-Uncut}}, booktitle = {19th International Symposium on Parameterized and Exact Computation (IPEC 2024)}, pages = {14:1--14:23}, 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.14}, URN = {urn:nbn:de:0030-drops-222400}, doi = {10.4230/LIPIcs.IPEC.2024.14}, annote = {Keywords: Fixed-parameter tractability, Polynomial Kernels, W\lbrack1\rbrack-hardness, XP, para-NP-Hardness} }
Published in: LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024)
Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. Distributed Model Checking on Graphs of Bounded Treedepth. In 38th International Symposium on Distributed Computing (DISC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 319, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fomin_et_al:LIPIcs.DISC.2024.25, author = {Fomin, Fedor V. and Fraigniaud, Pierre and Montealegre, Pedro and Rapaport, Ivan and Todinca, Ioan}, title = {{Distributed Model Checking on Graphs of Bounded Treedepth}}, booktitle = {38th International Symposium on Distributed Computing (DISC 2024)}, pages = {25:1--25:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-352-2}, ISSN = {1868-8969}, year = {2024}, volume = {319}, editor = {Alistarh, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.25}, URN = {urn:nbn:de:0030-drops-212513}, doi = {10.4230/LIPIcs.DISC.2024.25}, annote = {Keywords: proof-labeling schemes, local computing, CONGEST model} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Aritra Banik, Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Satyabrata Jana, and Saket Saurabh. Cuts in Graphs with Matroid Constraints. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{banik_et_al:LIPIcs.ESA.2024.17, author = {Banik, Aritra and Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Jana, Satyabrata and Saurabh, Saket}, title = {{Cuts in Graphs with Matroid Constraints}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {17:1--17:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.17}, URN = {urn:nbn:de:0030-drops-210887}, doi = {10.4230/LIPIcs.ESA.2024.17}, annote = {Keywords: s-t-cut, multiway Cut, matroid, odd cycle transversal, feedback vertex set, fixed-parameter tractability} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Hybrid k-Clustering: Blending k-Median and k-Center. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fomin_et_al:LIPIcs.APPROX/RANDOM.2024.4, author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav}, title = {{Hybrid k-Clustering: Blending k-Median and k-Center}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.4}, URN = {urn:nbn:de:0030-drops-209975}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.4}, annote = {Keywords: clustering, k-center, k-median, Euclidean space, fpt approximation} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin, Petr A. Golovach, and Tuukka Korhonen. Two-Sets Cut-Uncut on Planar Graphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bentert_et_al:LIPIcs.ICALP.2024.22, author = {Bentert, Matthias and Drange, P\r{a}l Gr{\o}n\r{a}s and Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka}, title = {{Two-Sets Cut-Uncut on Planar Graphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {22:1--22: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.22}, URN = {urn:nbn:de:0030-drops-201654}, doi = {10.4230/LIPIcs.ICALP.2024.22}, annote = {Keywords: planar graphs, cut-uncut, group-constrained paths} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Clément Dallard, Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Martin Milanič. Computing Tree Decompositions with Small Independence Number. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dallard_et_al:LIPIcs.ICALP.2024.51, author = {Dallard, Cl\'{e}ment and Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Milani\v{c}, Martin}, title = {{Computing Tree Decompositions with Small Independence Number}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {51:1--51: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.51}, URN = {urn:nbn:de:0030-drops-201945}, doi = {10.4230/LIPIcs.ICALP.2024.51}, annote = {Keywords: tree-independence number, approximation, parameterized algorithms} }
Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Saket Saurabh. Stability in Graphs with Matroid Constraints. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fomin_et_al:LIPIcs.SWAT.2024.22, author = {Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Saurabh, Saket}, title = {{Stability in Graphs with Matroid Constraints}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {22:1--22:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.22}, URN = {urn:nbn:de:0030-drops-200629}, doi = {10.4230/LIPIcs.SWAT.2024.22}, annote = {Keywords: frameworks, independent stable sets, parameterized complexity, kernelization} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Emmanuel Arrighi, Fedor V. Fomin, Petr A. Golovach, and Petra Wolf. Kernelizing Temporal Exploration Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{arrighi_et_al:LIPIcs.IPEC.2023.1, author = {Arrighi, Emmanuel and Fomin, Fedor V. and Golovach, Petr A. and Wolf, Petra}, title = {{Kernelizing Temporal Exploration Problems}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {1:1--1:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.1}, URN = {urn:nbn:de:0030-drops-194201}, doi = {10.4230/LIPIcs.IPEC.2023.1}, annote = {Keywords: Temporal graph, temporal exploration, computational complexity, kernel} }
Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen, and Giannos Stamoulis. Computing Paths of Large Rank in Planar Frameworks Deterministically. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fomin_et_al:LIPIcs.ISAAC.2023.32, author = {Fomin, Fedor V. and Golovach, Petr A. and Korhonen, Tuukka and Stamoulis, Giannos}, title = {{Computing Paths of Large Rank in Planar Frameworks Deterministically}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {32:1--32:15}, 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.32}, URN = {urn:nbn:de:0030-drops-193341}, doi = {10.4230/LIPIcs.ISAAC.2023.32}, annote = {Keywords: Planar graph, longest path, linear matroid, irrelevant vertex} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Saket Saurabh, and Meirav Zehavi. Kernelization for Spreading Points. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fomin_et_al:LIPIcs.ESA.2023.48, author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket and Zehavi, Meirav}, title = {{Kernelization for Spreading Points}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {48:1--48:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.48}, URN = {urn:nbn:de:0030-drops-187017}, doi = {10.4230/LIPIcs.ESA.2023.48}, annote = {Keywords: parameterized algorithms, kernelization, spreading points, distant representatives, unit disk packing} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Fedor V. Fomin, Tien-Nam Le, Daniel Lokshtanov, Saket Saurabh, Stéphan Thomassé, and Meirav Zehavi. Lossy Kernelization for (Implicit) Hitting Set Problems. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 49:1-49:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fomin_et_al:LIPIcs.ESA.2023.49, author = {Fomin, Fedor V. and Le, Tien-Nam and Lokshtanov, Daniel and Saurabh, Saket and Thomass\'{e}, St\'{e}phan and Zehavi, Meirav}, title = {{Lossy Kernelization for (Implicit) Hitting Set Problems}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {49:1--49:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.49}, URN = {urn:nbn:de:0030-drops-187020}, doi = {10.4230/LIPIcs.ESA.2023.49}, annote = {Keywords: Hitting Set, Lossy Kernelization} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Tomohiro Koana. FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 46:1-46:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fomin_et_al:LIPIcs.MFCS.2023.46, author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Koana, Tomohiro}, title = {{FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {46:1--46:8}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.46}, URN = {urn:nbn:de:0030-drops-185806}, doi = {10.4230/LIPIcs.MFCS.2023.46}, annote = {Keywords: Partial Vertex Cover, Approximation Algorithms, Max Cut} }
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 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Fedor V. Fomin, Petr A. Golovach, Ignasi Sau, Giannos Stamoulis, and Dimitrios M. Thilikos. Compound Logics for Modification Problems. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 61:1-61:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{fomin_et_al:LIPIcs.ICALP.2023.61, author = {Fomin, Fedor V. and Golovach, Petr A. and Sau, Ignasi and Stamoulis, Giannos and Thilikos, Dimitrios M.}, title = {{Compound Logics for Modification Problems}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {61:1--61:21}, 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.61}, URN = {urn:nbn:de:0030-drops-181137}, doi = {10.4230/LIPIcs.ICALP.2023.61}, annote = {Keywords: Algorithmic meta-theorems, Graph modification problems, Model-checking, Graph minors, First-order logic, Monadic second-order logic, Flat Wall theorem, Irrelevant vertex technique} }
Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)
Sayan Bandyapadhyay, Fedor V. Fomin, and Tanmay Inamdar. Coresets for Clustering in Geometric Intersection Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bandyapadhyay_et_al:LIPIcs.SoCG.2023.10, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Inamdar, Tanmay}, title = {{Coresets for Clustering in Geometric Intersection Graphs}}, booktitle = {39th International Symposium on Computational Geometry (SoCG 2023)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-273-0}, ISSN = {1868-8969}, year = {2023}, volume = {258}, editor = {Chambers, Erin W. and Gudmundsson, Joachim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.10}, URN = {urn:nbn:de:0030-drops-178605}, doi = {10.4230/LIPIcs.SoCG.2023.10}, annote = {Keywords: k-median, k-means, clustering, coresets, geometric graphs} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit, and Kirill Simonov. FPT Approximation for Fair Minimum-Load Clustering. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bandyapadhyay_et_al:LIPIcs.IPEC.2022.4, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Golovach, Petr A. and Purohit, Nidhi and Simonov, Kirill}, title = {{FPT Approximation for Fair Minimum-Load Clustering}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.4}, URN = {urn:nbn:de:0030-drops-173600}, doi = {10.4230/LIPIcs.IPEC.2022.4}, annote = {Keywords: fair clustering, load balancing, parameterized approximation} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, Nidhi Purohit, and Saket Saurabh. Exact Exponential Algorithms for Clustering Problems. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fomin_et_al:LIPIcs.IPEC.2022.13, author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Purohit, Nidhi and Saurabh, Saket}, title = {{Exact Exponential Algorithms for Clustering Problems}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {13:1--13:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.13}, URN = {urn:nbn:de:0030-drops-173691}, doi = {10.4230/LIPIcs.IPEC.2022.13}, annote = {Keywords: clustering, k-median, k-means, exact algorithms} }
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 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Meirav Zehavi. (Re)packing Equal Disks into Rectangle. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fomin_et_al:LIPIcs.ICALP.2022.60, author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Zehavi, Meirav}, title = {{(Re)packing Equal Disks into Rectangle}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {60:1--60:17}, 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.60}, URN = {urn:nbn:de:0030-drops-164011}, doi = {10.4230/LIPIcs.ICALP.2022.60}, annote = {Keywords: circle packing, unit disks, parameterized complexity, fixed-parameter tractability} }
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 213, 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Fedor V. Fomin, Petr A. Golovach, Tanmay Inamdar, and Saket Saurabh. ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space. 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. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{fomin_et_al:LIPIcs.FSTTCS.2021.21, author = {Fomin, Fedor V. and Golovach, Petr A. and Inamdar, Tanmay and Saurabh, Saket}, title = {{ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space}}, booktitle = {41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)}, pages = {21:1--21:16}, 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.21}, URN = {urn:nbn:de:0030-drops-155323}, doi = {10.4230/LIPIcs.FSTTCS.2021.21}, annote = {Keywords: Subexponential Algorithms, Geometric Intersection Graphs, Treedepth, Treewidth} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, and Kirill Simonov. Parameterized Complexity of Feature Selection for Categorical Data Clustering. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bandyapadhyay_et_al:LIPIcs.MFCS.2021.14, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Golovach, Petr A. and Simonov, Kirill}, title = {{Parameterized Complexity of Feature Selection for Categorical Data Clustering}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {14:1--14:14}, 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.14}, URN = {urn:nbn:de:0030-drops-144544}, doi = {10.4230/LIPIcs.MFCS.2021.14}, annote = {Keywords: Robust clustering, PCA, Low rank approximation, Hypergraph enumeration} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Sayan Bandyapadhyay, Fedor V. Fomin, and Kirill Simonov. On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 23:1-23:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bandyapadhyay_et_al:LIPIcs.ICALP.2021.23, author = {Bandyapadhyay, Sayan and Fomin, Fedor V. and Simonov, Kirill}, title = {{On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applications}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {23:1--23:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela 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.ICALP.2021.23}, URN = {urn:nbn:de:0030-drops-140923}, doi = {10.4230/LIPIcs.ICALP.2021.23}, annote = {Keywords: fair clustering, coresets, approximation algorithms} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, Geevarghese Philip, and Saket Saurabh. Diverse Collections in Matroids and Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{fomin_et_al:LIPIcs.STACS.2021.31, author = {Fomin, Fedor V. and Golovach, Petr A. and Panolan, Fahad and Philip, Geevarghese and Saurabh, Saket}, title = {{Diverse Collections in Matroids and Graphs}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {31:1--31:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus 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.2021.31}, URN = {urn:nbn:de:0030-drops-136769}, doi = {10.4230/LIPIcs.STACS.2021.31}, annote = {Keywords: Matroids, Diverse solutions, Fixed-parameter tractable algorithms} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Fedor V. Fomin, Petr A. Golovach, William Lochet, Pranabendu Misra, Saket Saurabh, and Roohani Sharma. Parameterized Complexity of Directed Spanner Problems. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 12:1-12:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.IPEC.2020.12, author = {Fomin, Fedor V. and Golovach, Petr A. and Lochet, William and Misra, Pranabendu and Saurabh, Saket and Sharma, Roohani}, title = {{Parameterized Complexity of Directed Spanner Problems}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {12:1--12:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.12}, URN = {urn:nbn:de:0030-drops-133156}, doi = {10.4230/LIPIcs.IPEC.2020.12}, annote = {Keywords: Graph spanners, directed graphs, parameterized complexity, kernelization} }
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 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Fedor V. Fomin and Petr A. Golovach. Kernelization of Whitney Switches. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 48:1-48:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.ESA.2020.48, author = {Fomin, Fedor V. and Golovach, Petr A.}, title = {{Kernelization of Whitney Switches}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {48:1--48:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.48}, URN = {urn:nbn:de:0030-drops-129144}, doi = {10.4230/LIPIcs.ESA.2020.48}, annote = {Keywords: Whitney switch, 2-isomorphism, Parameterized Complexity, kernelization} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Fedor V. Fomin and Petr A. Golovach. Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 49:1-49:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.ESA.2020.49, author = {Fomin, Fedor V. and Golovach, Petr A.}, title = {{Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {49:1--49:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.49}, URN = {urn:nbn:de:0030-drops-129157}, doi = {10.4230/LIPIcs.ESA.2020.49}, annote = {Keywords: Parameterized complexity, structural parameterization, subexponential algorithms, kernelization, chordal graphs, fill-in, independent set, clique, coloring} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Fedor V. Fomin, Petr Golovach, Pranabendu Misra, and M. S. Ramanujan. On the Complexity of Recovering Incidence Matrices. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 50:1-50:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.ESA.2020.50, author = {Fomin, Fedor V. and Golovach, Petr and Misra, Pranabendu and Ramanujan, M. S.}, title = {{On the Complexity of Recovering Incidence Matrices}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {50:1--50:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.50}, URN = {urn:nbn:de:0030-drops-129164}, doi = {10.4230/LIPIcs.ESA.2020.50}, annote = {Keywords: Graph Incidence Matrix, Matrix Recovery, Enumeration Algorithm} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Fedor V. Fomin, Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 51:1-51:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.ESA.2020.51, author = {Fomin, Fedor V. and Golovach, Petr A. and Stamoulis, Giannos and Thilikos, Dimitrios M.}, title = {{An Algorithmic Meta-Theorem for Graph Modification to Planarity and FOL}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {51:1--51:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.51}, URN = {urn:nbn:de:0030-drops-129172}, doi = {10.4230/LIPIcs.ESA.2020.51}, annote = {Keywords: Graph modification Problems, Algorithmic meta-theorems, First Order Logic, Irrelevant vertex technique, Planar graphs, Surface embeddable graphs} }
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 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Fedor V. Fomin, Petr A. Golovach, Fahad Panolan, and Kirill Simonov. Low-Rank Binary Matrix Approximation in Column-Sum Norm. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.APPROX/RANDOM.2020.32, author = {Fomin, Fedor V. and Golovach, Petr A. and Panolan, Fahad and Simonov, Kirill}, title = {{Low-Rank Binary Matrix Approximation in Column-Sum Norm}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {32:1--32:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.32}, URN = {urn:nbn:de:0030-drops-126355}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.32}, annote = {Keywords: Binary Matrix Factorization, PTAS, Column-sum norm} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Fedor V. Fomin, Daniel Lokshtanov, Ivan Mihajlin, Saket Saurabh, and Meirav Zehavi. Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.ICALP.2020.49, author = {Fomin, Fedor V. and Lokshtanov, Daniel and Mihajlin, Ivan and Saurabh, Saket and Zehavi, Meirav}, title = {{Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds}}, booktitle = {47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, pages = {49:1--49:18}, 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.49}, URN = {urn:nbn:de:0030-drops-124568}, doi = {10.4230/LIPIcs.ICALP.2020.49}, annote = {Keywords: Hadwiger Number, Exponential-Time Hypothesis, Exact Algorithms, Edge Contraction Problems} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
Fedor V. Fomin, Petr A. Golovach, and Kirill Simonov. Parameterized Complexity of PCA (Invited Talk). In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 1:1-1:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.SWAT.2020.1, author = {Fomin, Fedor V. and Golovach, Petr A. and Simonov, Kirill}, title = {{Parameterized Complexity of PCA}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {1:1--1:5}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.1}, URN = {urn:nbn:de:0030-drops-122487}, doi = {10.4230/LIPIcs.SWAT.2020.1}, annote = {Keywords: parameterized complexity, Robust PCA, outlier detection} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.SoCG.2020.44, author = {Fomin, Fedor V. and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Zehavi, Meirav}, title = {{ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {44:1--44:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.44}, URN = {urn:nbn:de:0030-drops-122024}, doi = {10.4230/LIPIcs.SoCG.2020.44}, annote = {Keywords: Optimality Program, ETH, Unit Disk Graphs, Parameterized Complexity, Long Path, Long Cycle} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Parameterization Above a Multiplicative Guarantee. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 39:1-39:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fomin_et_al:LIPIcs.ITCS.2020.39, author = {Fomin, Fedor V. and Golovach, Petr A. and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Zehavi, Meirav}, title = {{Parameterization Above a Multiplicative Guarantee}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {39:1--39:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.39}, URN = {urn:nbn:de:0030-drops-117248}, doi = {10.4230/LIPIcs.ITCS.2020.39}, annote = {Keywords: Parameterized Complexity, Above-Guarantee Parameterization, Girth} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Fedor V. Fomin, Petr A. Golovach, and Kirill Simonov. Parameterized k-Clustering: Tractability Island. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fomin_et_al:LIPIcs.FSTTCS.2019.14, author = {Fomin, Fedor V. and Golovach, Petr A. and Simonov, Kirill}, title = {{Parameterized k-Clustering: Tractability Island}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {14:1--14:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.14}, URN = {urn:nbn:de:0030-drops-115761}, doi = {10.4230/LIPIcs.FSTTCS.2019.14}, annote = {Keywords: clustering, parameterized complexity, k-means, k-median} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Going Far From Degeneracy. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fomin_et_al:LIPIcs.ESA.2019.47, author = {Fomin, Fedor V. and Golovach, Petr A. and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Zehavi, Meirav}, title = {{Going Far From Degeneracy}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {47:1--47:14}, 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.47}, URN = {urn:nbn:de:0030-drops-111688}, doi = {10.4230/LIPIcs.ESA.2019.47}, annote = {Keywords: Longest path, longest cycle, fixed-parameter tractability, above guarantee parameterization} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale. Path Contraction Faster Than 2^n. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agrawal_et_al:LIPIcs.ICALP.2019.11, author = {Agrawal, Akanksha and Fomin, Fedor V. and Lokshtanov, Daniel and Saurabh, Saket and Tale, Prafullkumar}, title = {{Path Contraction Faster Than 2^n}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {11:1--11:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.11}, URN = {urn:nbn:de:0030-drops-105874}, doi = {10.4230/LIPIcs.ICALP.2019.11}, annote = {Keywords: path contraction, exact exponential time algorithms, graph algorithms, enumerating connected sets, 3-disjoint connected subgraphs} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 59:1-59:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fomin_et_al:LIPIcs.ICALP.2019.59, author = {Fomin, Fedor V. and Golovach, Petr A. and Lokshtanov, Daniel and Saurabh, Saket and Zehavi, Meirav}, title = {{Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {59:1--59:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.59}, URN = {urn:nbn:de:0030-drops-106351}, doi = {10.4230/LIPIcs.ICALP.2019.59}, annote = {Keywords: Binary matroids, perturbed graphic matroids, spanning set, parameterized complexity} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Decomposition of Map Graphs with Applications. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 60:1-60:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fomin_et_al:LIPIcs.ICALP.2019.60, author = {Fomin, Fedor V. and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Zehavi, Meirav}, title = {{Decomposition of Map Graphs with Applications}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {60:1--60:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.60}, URN = {urn:nbn:de:0030-drops-106366}, doi = {10.4230/LIPIcs.ICALP.2019.60}, annote = {Keywords: Longest Cycle, Cycle Packing, Feedback Vertex Set, Map Graphs, FPT} }
Published in: Dagstuhl Reports, Volume 9, Issue 1 (2019)
Fedor V. Fomin, Dániel Marx, Saket Saurabh, and Meirav Zehavi. New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041). In Dagstuhl Reports, Volume 9, Issue 1, pp. 67-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@Article{fomin_et_al:DagRep.9.1.67, author = {Fomin, Fedor V. and Marx, D\'{a}niel and Saurabh, Saket and Zehavi, Meirav}, title = {{New Horizons in Parameterized Complexity (Dagstuhl Seminar 19041)}}, pages = {67--87}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2019}, volume = {9}, number = {1}, editor = {Fomin, Fedor V. and Marx, D\'{a}niel and Saurabh, Saket and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.1.67}, URN = {urn:nbn:de:0030-drops-105706}, doi = {10.4230/DagRep.9.1.67}, annote = {Keywords: Intractability, Parameterized Complexity} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. Modification to Planarity is Fixed Parameter Tractable. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fomin_et_al:LIPIcs.STACS.2019.28, author = {Fomin, Fedor V. and Golovach, Petr A. and Thilikos, Dimitrios M.}, title = {{Modification to Planarity is Fixed Parameter Tractable}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {28:1--28:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.28}, URN = {urn:nbn:de:0030-drops-102677}, doi = {10.4230/LIPIcs.STACS.2019.28}, annote = {Keywords: Modification problems, Planar graphs, Irrelevant vertex technique} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the Tractability of Optimization Problems on H-Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{fomin_et_al:LIPIcs.ESA.2018.30, author = {Fomin, Fedor V. and Golovach, Petr A. and Raymond, Jean-Florent}, title = {{On the Tractability of Optimization Problems on H-Graphs}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {30:1--30:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah 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.2018.30}, URN = {urn:nbn:de:0030-drops-94930}, doi = {10.4230/LIPIcs.ESA.2018.30}, annote = {Keywords: H-topological intersection graphs, parameterized complexity, minimal separators, boolean-width, mim-width} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Fedor V. Fomin, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. On the Optimality of Pseudo-polynomial Algorithms for Integer Programming. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 31:1-31:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{fomin_et_al:LIPIcs.ESA.2018.31, author = {Fomin, Fedor V. and Panolan, Fahad and Ramanujan, M. S. and Saurabh, Saket}, title = {{On the Optimality of Pseudo-polynomial Algorithms for Integer Programming}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {31:1--31:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah 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.2018.31}, URN = {urn:nbn:de:0030-drops-94949}, doi = {10.4230/LIPIcs.ESA.2018.31}, annote = {Keywords: Integer Programming, Strong Exponential Time Hypothesis, Branch-width of a matrix, Fine-grained Complexity} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Fedor V. Fomin, Petr A. Golovach, and Fahad Panolan. Parameterized Low-Rank Binary Matrix Approximation. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{fomin_et_al:LIPIcs.ICALP.2018.53, author = {Fomin, Fedor V. and Golovach, Petr A. and Panolan, Fahad}, title = {{Parameterized Low-Rank Binary Matrix Approximation}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {53:1--53:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.53}, URN = {urn:nbn:de:0030-drops-90571}, doi = {10.4230/LIPIcs.ICALP.2018.53}, annote = {Keywords: Binary matrices, clustering, low-rank approximation, fixed-parameter tractability} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Timothy Carpenter, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Anastasios Sidiropoulos. Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{carpenter_et_al:LIPIcs.SoCG.2018.21, author = {Carpenter, Timothy and Fomin, Fedor V. and Lokshtanov, Daniel and Saurabh, Saket and Sidiropoulos, Anastasios}, title = {{Algorithms for Low-Distortion Embeddings into Arbitrary 1-Dimensional Spaces}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {21:1--21:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.21}, URN = {urn:nbn:de:0030-drops-87344}, doi = {10.4230/LIPIcs.SoCG.2018.21}, annote = {Keywords: Metric embeddings, minimum-distortion embeddings, 1-dimensional simplicial complex, Fixed-parameter tractable algorithms, Approximation algorithms} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme, and Dimitrios M. Thilikos. Partial Complementation of Graphs. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 21:1-21:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{fomin_et_al:LIPIcs.SWAT.2018.21, author = {Fomin, Fedor V. and Golovach, Petr A. and Str{\o}mme, Torstein J. F. and Thilikos, Dimitrios M.}, title = {{Partial Complementation of Graphs}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {21:1--21:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.21}, URN = {urn:nbn:de:0030-drops-88476}, doi = {10.4230/LIPIcs.SWAT.2018.21}, annote = {Keywords: Partial complementation, graph editing, graph classes} }
Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Radu Curticapean, Holger Dell, Fedor V. Fomin, Leslie Ann Goldberg, and John Lapinskas. A Fixed-Parameter Perspective on #BIS. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 13:1-13:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{curticapean_et_al:LIPIcs.IPEC.2017.13, author = {Curticapean, Radu and Dell, Holger and Fomin, Fedor V. and Goldberg, Leslie Ann and Lapinskas, John}, title = {{A Fixed-Parameter Perspective on #BIS}}, booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)}, pages = {13:1--13:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-051-4}, ISSN = {1868-8969}, year = {2018}, volume = {89}, editor = {Lokshtanov, Daniel and Nishimura, Naomi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.13}, URN = {urn:nbn:de:0030-drops-85613}, doi = {10.4230/LIPIcs.IPEC.2017.13}, annote = {Keywords: Approximate counting, parameterised complexity, independent sets} }
Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. Structured Connectivity Augmentation. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{fomin_et_al:LIPIcs.MFCS.2017.29, author = {Fomin, Fedor V. and Golovach, Petr A. and Thilikos, Dimitrios M.}, title = {{Structured Connectivity Augmentation}}, booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)}, pages = {29:1--29:13}, 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.29}, URN = {urn:nbn:de:0030-drops-80603}, doi = {10.4230/LIPIcs.MFCS.2017.29}, annote = {Keywords: connectivity augmentation, graph superposition, complexity} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Ivona Bezáková, Radu Curticapean, Holger Dell, and Fedor V. Fomin. Finding Detours is Fixed-Parameter Tractable. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bezakova_et_al:LIPIcs.ICALP.2017.54, author = {Bez\'{a}kov\'{a}, Ivona and Curticapean, Radu and Dell, Holger and Fomin, Fedor V.}, title = {{Finding Detours is Fixed-Parameter Tractable}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {54:1--54:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.54}, URN = {urn:nbn:de:0030-drops-74790}, doi = {10.4230/LIPIcs.ICALP.2017.54}, annote = {Keywords: longest path, fixed-parameter tractable algorithms, above-guarantee parameterization, graph minors} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Covering Vectors by Spaces: Regular Matroids. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{fomin_et_al:LIPIcs.ICALP.2017.56, author = {Fomin, Fedor V. and Golovach, Petr A. and Lokshtanov, Daniel and Saurabh, Saket}, title = {{Covering Vectors by Spaces: Regular Matroids}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {56:1--56:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.56}, URN = {urn:nbn:de:0030-drops-73865}, doi = {10.4230/LIPIcs.ICALP.2017.56}, annote = {Keywords: regular matroids, spanning set, parameterized complexity} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi. Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 65:1-65:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{fomin_et_al:LIPIcs.ICALP.2017.65, author = {Fomin, Fedor V. and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket and Zehavi, Meirav}, title = {{Finding, Hitting and Packing Cycles in Subexponential Time on Unit Disk Graphs}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {65:1--65:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.65}, URN = {urn:nbn:de:0030-drops-73937}, doi = {10.4230/LIPIcs.ICALP.2017.65}, annote = {Keywords: Longest Cycle, Cycle Packing, Feedback Vertex Set, Unit Disk Graph, Parameterized Complexity} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Pradeesha Ashok, Fedor V. Fomin, Sudeshna Kolay, Saket Saurabh, and Meirav Zehavi. Exact Algorithms for Terrain Guarding. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{ashok_et_al:LIPIcs.SoCG.2017.11, author = {Ashok, Pradeesha and Fomin, Fedor V. and Kolay, Sudeshna and Saurabh, Saket and Zehavi, Meirav}, title = {{Exact Algorithms for Terrain Guarding}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {11:1--11:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.11}, URN = {urn:nbn:de:0030-drops-71975}, doi = {10.4230/LIPIcs.SoCG.2017.11}, annote = {Keywords: Terrain Guarding, Art Gallery, Exponential-Time Algorithms} }
Published in: Dagstuhl Reports, Volume 7, Issue 1 (2017)
Marek Cygan, Fedor V. Fomin, Danny Hermelin, and Magnus Wahlström. Randomization in Parameterized Complexity (Dagstuhl Seminar 17041). In Dagstuhl Reports, Volume 7, Issue 1, pp. 103-128, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@Article{cygan_et_al:DagRep.7.1.103, author = {Cygan, Marek and Fomin, Fedor V. and Hermelin, Danny and Wahlstr\"{o}m, Magnus}, title = {{Randomization in Parameterized Complexity (Dagstuhl Seminar 17041)}}, pages = {103--128}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2017}, volume = {7}, number = {1}, editor = {Cygan, Marek and Fomin, Fedor V. and Hermelin, Danny and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.1.103}, URN = {urn:nbn:de:0030-drops-72479}, doi = {10.4230/DagRep.7.1.103}, annote = {Keywords: fixed-parameter tractability, intractability, parameterized complexity, randomness} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, and Meirav Zehavi. Matrix Rigidity from the Viewpoint of Parameterized Complexity. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{fomin_et_al:LIPIcs.STACS.2017.32, author = {Fomin, Fedor V. and Lokshtanov, Daniel and Meesum, S. M. and Saurabh, Saket and Zehavi, Meirav}, title = {{Matrix Rigidity from the Viewpoint of Parameterized Complexity}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {32:1--32:14}, 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.32}, URN = {urn:nbn:de:0030-drops-70019}, doi = {10.4230/LIPIcs.STACS.2017.32}, annote = {Keywords: Matrix Rigidity, Parameterized Complexity, Linear Algebra} }
Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Fedor V. Fomin. Graph Decompositions and Algorithms (Invited Talk). In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{fomin:LIPIcs.FSTTCS.2016.5, author = {Fomin, Fedor V.}, title = {{Graph Decompositions and Algorithms}}, booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)}, pages = {5:1--5:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-027-9}, ISSN = {1868-8969}, year = {2016}, volume = {65}, editor = {Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.5}, URN = {urn:nbn:de:0030-drops-68903}, doi = {10.4230/LIPIcs.FSTTCS.2016.5}, annote = {Keywords: Algorithms, logic, graph minor} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Pål Grønås Drange, Markus Dregi, Fedor V. Fomin, Stephan Kreutzer, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Felix Reidl, Fernando Sánchez Villaamil, Saket Saurabh, Sebastian Siebertz, and Somnath Sikdar. Kernelization and Sparseness: the Case of Dominating Set. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{drange_et_al:LIPIcs.STACS.2016.31, author = {Drange, P\r{a}l Gr{\o}n\r{a}s and Dregi, Markus and Fomin, Fedor V. and Kreutzer, Stephan and Lokshtanov, Daniel and Pilipczuk, Marcin and Pilipczuk, Michal and Reidl, Felix and S\'{a}nchez Villaamil, Fernando and Saurabh, Saket and Siebertz, Sebastian and Sikdar, Somnath}, title = {{Kernelization and Sparseness: the Case of Dominating Set}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {31:1--31: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.31}, URN = {urn:nbn:de:0030-drops-57327}, doi = {10.4230/LIPIcs.STACS.2016.31}, annote = {Keywords: kernelization, dominating set, bounded expansion, nowhere dense} }
Published in: LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Fedor V. Fomin, Petr Golovach, Fahad Panolan, and Saket Saurabh. Editing to Connected f-Degree Graph. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{fomin_et_al:LIPIcs.STACS.2016.36, author = {Fomin, Fedor V. and Golovach, Petr and Panolan, Fahad and Saurabh, Saket}, title = {{Editing to Connected f-Degree Graph}}, booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)}, pages = {36:1--36: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.36}, URN = {urn:nbn:de:0030-drops-57370}, doi = {10.4230/LIPIcs.STACS.2016.36}, annote = {Keywords: Connected f-factor, FPT, Representative Family, Color Coding} }
Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)
Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, and Alexander S. Kulikov. Parameterized Complexity of Secluded Connectivity Problems. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 408-419, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{fomin_et_al:LIPIcs.FSTTCS.2015.408, author = {Fomin, Fedor V. and Golovach, Petr A. and Karpov, Nikolay and Kulikov, Alexander S.}, title = {{Parameterized Complexity of Secluded Connectivity Problems}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {408--419}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.408}, URN = {urn:nbn:de:0030-drops-56318}, doi = {10.4230/LIPIcs.FSTTCS.2015.408}, annote = {Keywords: Secluded path, Secluded Steiner tree, parameterized complexity} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Manu Basavaraju, Fedor V. Fomin, Petr A. Golovach, and Saket Saurabh. Connecting Vertices by Independent Trees. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 73-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{basavaraju_et_al:LIPIcs.FSTTCS.2014.73, author = {Basavaraju, Manu and Fomin, Fedor V. and Golovach, Petr A. and Saurabh, Saket}, title = {{Connecting Vertices by Independent Trees}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {73--84}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.73}, URN = {urn:nbn:de:0030-drops-48340}, doi = {10.4230/LIPIcs.FSTTCS.2014.73}, annote = {Keywords: Parameterized complexity, FPT-algorithms, completely independent spanning trees} }
Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Pal Gronas Drange, Fedor V. Fomin, Michal Pilipczuk, and Yngve Villanger. Exploring Subexponential Parameterized Complexity of Completion Problems. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 288-299, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{drange_et_al:LIPIcs.STACS.2014.288, author = {Drange, Pal Gronas and Fomin, Fedor V. and Pilipczuk, Michal and Villanger, Yngve}, title = {{Exploring Subexponential Parameterized Complexity of Completion Problems}}, booktitle = {31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)}, pages = {288--299}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-65-1}, ISSN = {1868-8969}, year = {2014}, volume = {25}, editor = {Mayr, Ernst W. and Portier, Natacha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.288}, URN = {urn:nbn:de:0030-drops-44659}, doi = {10.4230/LIPIcs.STACS.2014.288}, annote = {Keywords: edge completion, modification, subexponential parameterized complexity} }
Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Rajesh Chitnis, Fedor V. Fomin, and Petr A. Golovach. Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 79-90, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{chitnis_et_al:LIPIcs.FSTTCS.2013.79, author = {Chitnis, Rajesh and Fomin, Fedor V. and Golovach, Petr A.}, title = {{Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)}, pages = {79--90}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-64-4}, ISSN = {1868-8969}, year = {2013}, volume = {24}, editor = {Seth, Anil and Vishnoi, Nisheeth K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.79}, URN = {urn:nbn:de:0030-drops-43636}, doi = {10.4230/LIPIcs.FSTTCS.2013.79}, annote = {Keywords: Parameterized complexity, directed graphs, anchored \$k\$-core} }
Published in: Dagstuhl Reports, Volume 3, Issue 3 (2013)
Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. Bidimensional Structures: Algorithms, Combinatorics and Logic (Dagstuhl Seminar 13121). In Dagstuhl Reports, Volume 3, Issue 3, pp. 51-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@Article{demaine_et_al:DagRep.3.3.51, author = {Demaine, Erik D. and Fomin, Fedor V. and Hajiaghayi, MohammadTaghi and Thilikos, Dimitrios M.}, title = {{Bidimensional Structures: Algorithms, Combinatorics and Logic (Dagstuhl Seminar 13121)}}, pages = {51--74}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {3}, number = {3}, editor = {Demaine, Erik D. and Fomin, Fedor V. and Hajiaghayi, MohammadTaghi and Thilikos, Dimitrios M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.3.51}, URN = {urn:nbn:de:0030-drops-40131}, doi = {10.4230/DagRep.3.3.51}, annote = {Keywords: Graph Minors, Treewidth, Graph algorithms, Parameterized Algorithms} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Fedor V. Fomin and Yngve Villanger. Searching for better fill-in. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 8-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{fomin_et_al:LIPIcs.STACS.2013.8, author = {Fomin, Fedor V. and Villanger, Yngve}, title = {{Searching for better fill-in}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {8--19}, 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.8}, URN = {urn:nbn:de:0030-drops-39187}, doi = {10.4230/LIPIcs.STACS.2013.8}, annote = {Keywords: Local Search, Parameterized Complexity, Fill-in, Triangulation, Chordal graph} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Fedor V. Fomin, Stefan Kratsch, Marcin Pilipczuk, Michal Pilipczuk, and Yngve Villanger. Tight bounds for Parameterized Complexity of Cluster Editing. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 32-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{fomin_et_al:LIPIcs.STACS.2013.32, author = {Fomin, Fedor V. and Kratsch, Stefan and Pilipczuk, Marcin and Pilipczuk, Michal and Villanger, Yngve}, title = {{Tight bounds for Parameterized Complexity of Cluster Editing}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {32--43}, 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.32}, URN = {urn:nbn:de:0030-drops-39209}, doi = {10.4230/LIPIcs.STACS.2013.32}, annote = {Keywords: parameterized complexity, cluster editing, correlation clustering, subexponential algorithms, tight bounds} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Dimitrios M. Thilikos. Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 92-103, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{fomin_et_al:LIPIcs.STACS.2013.92, author = {Fomin, Fedor V. and Lokshtanov, Daniel and Saurabh, Saket and Thilikos, Dimitrios M.}, title = {{Linear kernels for (connected) dominating set on graphs with excluded topological subgraphs}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {92--103}, 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.92}, URN = {urn:nbn:de:0030-drops-39255}, doi = {10.4230/LIPIcs.STACS.2013.92}, annote = {Keywords: Parameterized complexity, kernelization, algorithmic graph minors, dominating set, connected dominating set} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Fedor V. Fomin and Petr A. Golovach. Parameterized Complexity of Connected Even/Odd Subgraph Problems. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 432-440, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{fomin_et_al:LIPIcs.STACS.2012.432, author = {Fomin, Fedor V. and Golovach, Petr A.}, title = {{Parameterized Complexity of Connected Even/Odd Subgraph Problems}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {432--440}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph 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.2012.432}, URN = {urn:nbn:de:0030-drops-33986}, doi = {10.4230/LIPIcs.STACS.2012.432}, annote = {Keywords: Parameterized complexity, Euler graph, even graph, odd graph, treewidth} }
Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Fedor V. Fomin, Geevarghese Philip, and Yngve Villanger. Minimum Fill-in of Sparse Graphs: Kernelization and Approximation. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 164-175, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{fomin_et_al:LIPIcs.FSTTCS.2011.164, author = {Fomin, Fedor V. and Philip, Geevarghese and Villanger, Yngve}, title = {{Minimum Fill-in of Sparse Graphs: Kernelization and Approximation}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)}, pages = {164--175}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-34-7}, ISSN = {1868-8969}, year = {2011}, volume = {13}, editor = {Chakraborty, Supratik and Kumar, Amit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.164}, URN = {urn:nbn:de:0030-drops-33451}, doi = {10.4230/LIPIcs.FSTTCS.2011.164}, annote = {Keywords: Minimum Fill-In, Approximation, Kernelization, Sparse graphs} }
Published in: Dagstuhl Reports, Volume 1, Issue 2 (2011)
Fedor V. Fomin, Pierre Fraigniaud, Stephan Kreutzer, and Dimitrios M. Thilikos. Theory and Applications of Graph Searching Problems (GRASTA 2011) (Dagstuhl Seminar 11071). In Dagstuhl Reports, Volume 1, Issue 2, pp. 30-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@Article{fomin_et_al:DagRep.1.2.30, author = {Fomin, Fedor V. and Fraigniaud, Pierre and Kreutzer, Stephan and Thilikos, Dimitrios M.}, title = {{Theory and Applications of Graph Searching Problems (GRASTA 2011) (Dagstuhl Seminar 11071)}}, pages = {30--46}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2011}, volume = {1}, number = {2}, editor = {Fomin, Fedor V. and Fraigniaud, Pierre and Kreutzer, Stephan and Thilikos, Dimitrios M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.1.2.30}, URN = {urn:nbn:de:0030-drops-31534}, doi = {10.4230/DagRep.1.2.30}, annote = {Keywords: Graph Searching, Pursuit Evasion Games, Cop and Robers Games, Fugitive Search Games} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Fedor V. Fomin, Daniel Lokshtanov, Neeldhara Misra, Geevarghese Philip, and Saket Saurabh. Hitting forbidden minors: Approximation and Kernelization. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 189-200, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{fomin_et_al:LIPIcs.STACS.2011.189, author = {Fomin, Fedor V. and Lokshtanov, Daniel and Misra, Neeldhara and Philip, Geevarghese and Saurabh, Saket}, title = {{Hitting forbidden minors: Approximation and Kernelization}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {189--200}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.189}, URN = {urn:nbn:de:0030-drops-30103}, doi = {10.4230/LIPIcs.STACS.2011.189}, annote = {Keywords: kernelization} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Frederic Dorn, Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 251-262, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{dorn_et_al:LIPIcs.STACS.2010.2459, author = {Dorn, Frederic and Fomin, Fedor V. and Lokshtanov, Daniel and Raman, Venkatesh and Saurabh, Saket}, title = {{Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {251--262}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2459}, URN = {urn:nbn:de:0030-drops-24599}, doi = {10.4230/LIPIcs.STACS.2010.2459}, annote = {Keywords: Parameterized Subexponential Algorithms, Directed Graphs, Out-Branching, Internal Out-Branching} }
Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)
Fedor V. Fomin and Yngve Villanger. Finding Induced Subgraphs via Minimal Triangulations. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 383-394, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{fomin_et_al:LIPIcs.STACS.2010.2470, author = {Fomin, Fedor V. and Villanger, Yngve}, title = {{Finding Induced Subgraphs via Minimal Triangulations}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {383--394}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2470}, URN = {urn:nbn:de:0030-drops-24708}, doi = {10.4230/LIPIcs.STACS.2010.2470}, annote = {Keywords: Bounded treewidth, minimal triangulation, moderately exponential time algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)
Fedor V. Fomin, Petr Golovach, and Dimitrios M. Thilikos. Contraction Bidimensionality: the Accurate Picture. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{fomin_et_al:DagSemProc.09511.5, author = {Fomin, Fedor V. and Golovach, Petr and Thilikos, Dimitrios M.}, title = {{Contraction Bidimensionality: the Accurate Picture}}, booktitle = {Parameterized complexity and approximation algorithms}, pages = {1--12}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9511}, editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.5}, URN = {urn:nbn:de:0030-drops-25009}, doi = {10.4230/DagSemProc.09511.5}, annote = {Keywords: Paramerterized Algorithms, Bidimensionality, Graph Minors} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Stéphane Bessy, Fedor V. Fomin, Serge Gaspers, Christophe Paul, Anthony Perez, Saket Saurabh, and Stéphan Thomassé. Kernels for Feedback Arc Set In Tournaments. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 37-47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{bessy_et_al:LIPIcs.FSTTCS.2009.2305, author = {Bessy, St\'{e}phane and Fomin, Fedor V. and Gaspers, Serge and Paul, Christophe and Perez, Anthony and Saurabh, Saket and Thomass\'{e}, St\'{e}phan}, title = {{Kernels for Feedback Arc Set In Tournaments}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {37--47}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2305}, URN = {urn:nbn:de:0030-drops-23055}, doi = {10.4230/LIPIcs.FSTTCS.2009.2305}, annote = {Keywords: Parameterized complexity, kernels, tournaments} }
Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)
Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, and Saket Saurabh. Subexponential Algorithms for Partial Cover Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 193-201, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{fomin_et_al:LIPIcs.FSTTCS.2009.2318, author = {Fomin, Fedor V. and Lokshtanov, Daniel and Raman, Venkatesh and Saurabh, Saket}, title = {{Subexponential Algorithms for Partial Cover Problems}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {193--201}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-13-2}, ISSN = {1868-8969}, year = {2009}, volume = {4}, editor = {Kannan, Ravi and Narayan Kumar, K.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2318}, URN = {urn:nbn:de:0030-drops-23186}, doi = {10.4230/LIPIcs.FSTTCS.2009.2318}, annote = {Keywords: Partial cover problems, parameterized complexity, subexponential time algorithms, irrelevant vertex technique} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, and Yngve Villanger. Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 421-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{fernau_et_al:LIPIcs.STACS.2009.1843, author = {Fernau, Henning and Fomin, Fedor V. and Lokshtanov, Daniel and Raible, Daniel and Saurabh, Saket and Villanger, Yngve}, title = {{Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {421--432}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1843}, URN = {urn:nbn:de:0030-drops-18437}, doi = {10.4230/LIPIcs.STACS.2009.1843}, annote = {Keywords: Parameterized algorithms, Kernelization, Out-branching, Max-leaf, Lower bounds} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos. Approximating Acyclicity Parameters of Sparse Hypergraphs. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 445-456, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{fomin_et_al:LIPIcs.STACS.2009.1803, author = {Fomin, Fedor V. and Golovach, Petr A. and Thilikos, Dimitrios M.}, title = {{Approximating Acyclicity Parameters of Sparse Hypergraphs}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {445--456}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1803}, URN = {urn:nbn:de:0030-drops-18034}, doi = {10.4230/LIPIcs.STACS.2009.1803}, annote = {Keywords: Graph, Hypergraph, Hypertree width, Treewidth} }
Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)
Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch. 08431 Abstracts Collection – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{fomin_et_al:DagSemProc.08431.1, author = {Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter}, title = {{08431 Abstracts Collection – Moderately Exponential Time Algorithms}}, booktitle = {Moderately Exponential Time Algorithms}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8431}, editor = {Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.1}, URN = {urn:nbn:de:0030-drops-18004}, doi = {10.4230/DagSemProc.08431.1}, annote = {Keywords: Algorithms, Exponential time algorithms, Graphs, SAT} }
Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)
Fedor V. Fomin, Kazuo Iwama, and Dieter Kratsch. 08431 Executive Summary – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{fomin_et_al:DagSemProc.08431.2, author = {Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter}, title = {{08431 Executive Summary – Moderately Exponential Time Algorithms}}, booktitle = {Moderately Exponential Time Algorithms}, pages = {1--2}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8431}, editor = {Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.2}, URN = {urn:nbn:de:0030-drops-17976}, doi = {10.4230/DagSemProc.08431.2}, annote = {Keywords: Algorithms, NP-hard problems, Exact algorithms, Moderately Exponential Time Algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)
Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan van Rooij, and Ryan Williams. 08431 Open Problems – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{fomin_et_al:DagSemProc.08431.3, author = {Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter and Kaski, Petteri and Koivisto, Mikko and Kowalik, Lukasz and Okamoto, Yoshio and van Rooij, Johan and Williams, Ryan}, title = {{08431 Open Problems – Moderately Exponential Time Algorithms}}, booktitle = {Moderately Exponential Time Algorithms}, pages = {1--8}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8431}, editor = {Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.3}, URN = {urn:nbn:de:0030-drops-17986}, doi = {10.4230/DagSemProc.08431.3}, annote = {Keywords: Algorithms, NP-hard problems, Moderately Exponential Time Algorithms} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Parinya Chalermsook, Fedor Fomin, Thekla Hamm, Tuukka Korhonen, Jesper Nederlof, and Ly Orgo. Polynomial-Time Approximation of Independent Set Parameterized by Treewidth. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chalermsook_et_al:LIPIcs.ESA.2023.33, author = {Chalermsook, Parinya and Fomin, Fedor and Hamm, Thekla and Korhonen, Tuukka and Nederlof, Jesper and Orgo, Ly}, title = {{Polynomial-Time Approximation of Independent Set Parameterized by Treewidth}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {33:1--33:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.33}, URN = {urn:nbn:de:0030-drops-186865}, doi = {10.4230/LIPIcs.ESA.2023.33}, annote = {Keywords: Maximum Independent Set, Treewidth, Approximation Algorithms, Parameterized Approximation} }
Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Mohsen Alambardar Meybodi, Fedor Fomin, Amer E. Mouawad, and Fahad Panolan. On the Parameterized Complexity of [1,j]-Domination Problems. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{alambardarmeybodi_et_al:LIPIcs.FSTTCS.2018.34, author = {Alambardar Meybodi, Mohsen and Fomin, Fedor and Mouawad, Amer E. and Panolan, Fahad}, title = {{On the Parameterized Complexity of \lbrack1,j\rbrack-Domination Problems}}, booktitle = {38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)}, pages = {34:1--34:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-093-4}, ISSN = {1868-8969}, year = {2018}, volume = {122}, editor = {Ganguly, Sumit and Pandya, Paritosh}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.34}, URN = {urn:nbn:de:0030-drops-99330}, doi = {10.4230/LIPIcs.FSTTCS.2018.34}, annote = {Keywords: \lbrack1, j\rbrack-dominating set, parameterized complexity, sparse graphs} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Fedor Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{fomin_et_al:LIPIcs.SoCG.2016.39, author = {Fomin, Fedor and Kolay, Sudeshna and Lokshtanov, Daniel and Panolan, Fahad and Saurabh, Saket}, title = {{Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.39}, URN = {urn:nbn:de:0030-drops-59310}, doi = {10.4230/LIPIcs.SoCG.2016.39}, annote = {Keywords: Rectilinear graphs, Steiner arborescence, parameterized algorithms} }
Published in: LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008)
Omid Amini, Fedor Fomin, and Saket Saurabh. Implicit Branching and Parameterized Partial Cover Problems (Extended Abstract). In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{amini_et_al:LIPIcs.FSTTCS.2008.1736, author = {Amini, Omid and Fomin, Fedor and Saurabh, Saket}, title = {{Implicit Branching and Parameterized Partial Cover Problems}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, pages = {1--12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-08-8}, ISSN = {1868-8969}, year = {2008}, volume = {2}, editor = {Hariharan, Ramesh and Mukund, Madhavan and Vinay, V}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1736}, URN = {urn:nbn:de:0030-drops-17363}, doi = {10.4230/LIPIcs.FSTTCS.2008.1736}, annote = {Keywords: Implicit Branching, Parameterized Algorithms, Partial Dominating Set, Partial Vertex Cover, Local Treewidth} }
Feedback for Dagstuhl Publishing