Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Júlio Araújo, Marin Bougeret, Victor Campos, and Ignasi Sau. A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{araujo_et_al:LIPIcs.IPEC.2021.4, author = {Ara\'{u}jo, J\'{u}lio and Bougeret, Marin and Campos, Victor and Sau, Ignasi}, title = {{A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.4}, URN = {urn:nbn:de:0030-drops-153879}, doi = {10.4230/LIPIcs.IPEC.2021.4}, annote = {Keywords: Maximum minimal vertex cover, parameterized complexity, polynomial kernel, kernelization lower bound, Erd\H{o}s-Hajnal property, induced subgraphs} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos. Lean Tree-Cut Decompositions: Obstructions and Algorithms. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{giannopoulou_et_al:LIPIcs.STACS.2019.32, author = {Giannopoulou, Archontia C. and Kwon, O-joung and Raymond, Jean-Florent and Thilikos, Dimitrios M.}, title = {{Lean Tree-Cut Decompositions: Obstructions and Algorithms}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {32:1--32:14}, 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.32}, URN = {urn:nbn:de:0030-drops-102716}, doi = {10.4230/LIPIcs.STACS.2019.32}, annote = {Keywords: tree-cut width, lean decompositions, immersions, obstructions, parameterized algorithms} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{giannopoulou_et_al:LIPIcs.ICALP.2017.57, author = {Giannopoulou, Archontia C. and Pilipczuk, Michal and Raymond, Jean-Florent and Thilikos, Dimitrios M. and Wrochna, Marcin}, title = {{Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {57:1--57: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.57}, URN = {urn:nbn:de:0030-drops-73891}, doi = {10.4230/LIPIcs.ICALP.2017.57}, annote = {Keywords: Kernelization, Approximation, Immersion, Protrusion, Tree-cut width} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 63:1-63:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{eickmeyer_et_al:LIPIcs.ICALP.2017.63, author = {Eickmeyer, Kord and Giannopoulou, Archontia C. and Kreutzer, Stephan and Kwon, O-joung and Pilipczuk, Michal and Rabinovich, Roman and Siebertz, Sebastian}, title = {{Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {63:1--63: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.63}, URN = {urn:nbn:de:0030-drops-74288}, doi = {10.4230/LIPIcs.ICALP.2017.63}, annote = {Keywords: Graph Structure Theory, Nowhere Dense Graphs, Parameterized Complexity, Kernelization, Dominating Set} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Archontia C. Giannopoulou, Michal Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna. Cutwidth: Obstructions and Algorithmic Aspects. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{giannopoulou_et_al:LIPIcs.IPEC.2016.15, author = {Giannopoulou, Archontia C. and Pilipczuk, Michal and Raymond, Jean-Florent and Thilikos, Dimitrios M. and Wrochna, Marcin}, title = {{Cutwidth: Obstructions and Algorithmic Aspects}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {15:1--15:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.15}, URN = {urn:nbn:de:0030-drops-69306}, doi = {10.4230/LIPIcs.IPEC.2016.15}, annote = {Keywords: cutwidth, obstructions, immersions, fixed-parameter tractability} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Dimitris Chatzidimitriou, Archontia C. Giannopoulou, Spyridon Maniatis, Clément Requilé, Dimitrios M. Thilikos, and Dimitris Zoros. FPT Algorithms for Plane Completion Problems. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{chatzidimitriou_et_al:LIPIcs.MFCS.2016.26, author = {Chatzidimitriou, Dimitris and Giannopoulou, Archontia C. and Maniatis, Spyridon and Requil\'{e}, Cl\'{e}ment and Thilikos, Dimitrios M. and Zoros, Dimitris}, title = {{FPT Algorithms for Plane Completion Problems}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {26:1--26:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.26}, URN = {urn:nbn:de:0030-drops-64418}, doi = {10.4230/LIPIcs.MFCS.2016.26}, annote = {Keywords: completion problems, FPT, plane graphs, topological isomorphism} }
Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Archontia C. Giannopoulou, George B. Mertzios, and Rolf Niedermeier. Polynomial Fixed-parameter Algorithms: A Case Study for Longest Path on Interval Graphs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 102-113, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{giannopoulou_et_al:LIPIcs.IPEC.2015.102, author = {Giannopoulou, Archontia C. and Mertzios, George B. and Niedermeier, Rolf}, title = {{Polynomial Fixed-parameter Algorithms: A Case Study for Longest Path on Interval Graphs}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {102--113}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.102}, URN = {urn:nbn:de:0030-drops-55750}, doi = {10.4230/LIPIcs.IPEC.2015.102}, annote = {Keywords: fixed-parameter algorithm, preprocessing, data reduction, polynomial-time algorithm, longest path problem, interval graphs, proper interval vertex del} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Archontia C. Giannopoulou and George B. Mertzios. New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 354-366, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{giannopoulou_et_al:LIPIcs.STACS.2015.354, author = {Giannopoulou, Archontia C. and Mertzios, George B.}, title = {{New Geometric Representations and Domination Problems on Tolerance and Multitolerance Graphs}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {354--366}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.354}, URN = {urn:nbn:de:0030-drops-49268}, doi = {10.4230/LIPIcs.STACS.2015.354}, annote = {Keywords: tolerance graphs, multitolerance graphs, geometric representation, dominating set problem, polynomial time algorithm, APX-hard} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh, and Ondrej Suchy. Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation). In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 85-96, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{giannopoulou_et_al:LIPIcs.FSTTCS.2014.85, author = {Giannopoulou, Archontia C. and Lokshtanov, Daniel and Saurabh, Saket and Suchy, Ondrej}, title = {{Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {85--96}, 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.85}, URN = {urn:nbn:de:0030-drops-48261}, doi = {10.4230/LIPIcs.FSTTCS.2014.85}, annote = {Keywords: Tree Deletion Set, Feedback Vertex Set, Kernelization, Linear Equations} }
Feedback for Dagstuhl Publishing