Lampis Michael - CV

Articles

Harutyunyan A., Lampis M., Melissinos N. (2024), Digraph Coloring and Distance to Acyclicity, Theory of Computing Systems, vol. 68, n°4, p. 986-1013

Gourvès L., Harutyunyan A., Lampis M., Melissinos N. (2024), Filling crosswords is very hard, Theoretical Computer Science, vol. 982, p. 114275

Katsikarelis I., Lampis M., Paschos V. (2023), Improved (In-)Approximability Bounds for d-Scattered Set, Journal of Graph Algorithms and Applications, vol. 27, n°3, p. 219-238

Belmonte R., Hanaka T., Katsikarelis I., Kim E., Lampis M. (2023), New Results on Directed Edge Dominating Set, Discrete Mathematics and Theoretical Computer Science, vol. vol. 25:1

Belmonte R., Hanaka T., Kanzaki M., Kiyomi M., Kobayashi Y., Kobayashi Y., Lampis M., Ono H., Otachi Y. (2022), Parameterized Complexity of (A,ℓ)-Path Packing, Algorithmica, vol. 84, n°4, p. 871–895

Katsikarelis I., Lampis M., Paschos V. (2022), Structurally parameterized d -scattered set, Discrete Applied Mathematics, vol. 308, p. 168-186

Belmonte R., Kim E., Lampis M., Mitsou V., Otachi Y. (2022), Grundy Distinguishes Treewidth from Pathwidth, SIAM Journal on Discrete Mathematics, vol. 36, n°3, p. 1761-1787

Dublois L., Hanaka T., Khosravian Ghadikolaei M., Lampis M., Melissinos N. (2022), (In)approximability of maximum minimal FVS, Journal of Computer and System Sciences, vol. 124, p. 26-40

Belmonte R., Lampis M., Mitsou V. (2022), Defective Coloring on Classes of Perfect Graphs, Discrete Mathematics and Theoretical Computer Science, vol. 24, n°1

Sikora F., Belmonte R., Kim E., Lampis M., Mitsou V., Otachi Y. (2021), Token Sliding on Split Graphs, Theory of Computing Systems, vol. 65, n°4, p. 662–686

Dublois L., Lampis M., Paschos V. (2021), New Algorithms for Mixed Dominating Set, Discrete Mathematics and Theoretical Computer Science, vol. 23, n°1

Lampis M. (2020), Finer Tight Bounds for Coloring on Clique-Width, SIAM Journal on Discrete Mathematics, vol. 34, n°3, p. 1538–1558

Chiba K., Belmonte R., Ito H., Lampis M., Nagao A., Otachi Y. (2020), K3 Edge Cover Problem in a Wide Sense, Journal of Information Processing, vol. 28, p. 849–858

Belmonte R., Lampis M., Mitsou V. (2020), Parameterized (Approximate) Defective Coloring, SIAM Journal on Discrete Mathematics, vol. 34, n°2, p. 1084–1106

Harutyunyan A., Lampis M., Lozin V., Monnot J. (2020), Maximum independent sets in subcubic graphs: New results, Theoretical Computer Science, vol. 846, p. 14-26

Belmonte R., Hanaka T., Katsikarelis I., Lampis M., Ono H., Otachi Y. (2020), Parameterized Complexity of Safe Set, Journal of Graph Algorithms and Applications, vol. 24, n°3, p. 215-245

Belmonte R., Hanaka T., Lampis M., Ono H., Otachi Y. (2020), Independent Set Reconfiguration Parameterized by Modular-Width, Algorithmica, vol. 82, n°9, p. 2586–2605

Hanaka T., Katsikarelis I., Lampis M., Otachi Y., Sikora F. (2020), Parameterized Orientable Deletion, Algorithmica, vol. 82, n°7, p. 1909–1938

Belmonte R., Khosravian Ghadikolaei M., Kiyomi M., Lampis M., Otachi Y. (2019), How Bad is the Freedom to Flood-It?, Journal of Graph Algorithms and Applications, vol. 23, n°2, p. 111-134

Katsikarelis I., Lampis M., Paschos V. (2019), Structural parameters, tight bounds, and approximation for (k,r)-center, Discrete Applied Mathematics, vol. 264, p. 90-117

Bonnet E., Giannopoulos P., Lampis M. (2019), On the parameterized complexity of red-blue points separation, Journal of Computational Geometry (JoCG), vol. 10, n°1, p. 181–206

Lampis M., Makino K., Mitsou V., Uno Y. (2018), Parameterized Edge Hamiltonicity, Discrete Applied Mathematics, vol. 248, p. 68-78

Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2018), The many facets of upper domination, Theoretical Computer Science, vol. 717, p. 2-25

Bonnet É., Lampis M., Paschos V. (2018), Time-approximation trade-offs for inapproximable problems, Journal of Computer and System Sciences, vol. 92, p. 171-180

Dell H., Kim E., Lampis M., Mitsou V., Mömke T. (2017), Complexity and Approximability of Parameterized MAX-CSPs, Algorithmica, vol. 79, n°1, p. 230-250

Karpinski M., Lampis M., Schmied R. (2015), New inapproximability bounds for TSP, Journal of Computer and System Sciences, vol. 81, n°8, p. 1665-1677

Lampis M., Mitsou V., Sołtys K. (2015), Scrabble is PSPACE-Complete, Journal of Information Processing, vol. 23, n°3, p. 284-292

Lampis M. (2014), Model Checking Lower Bounds for Simple Graphs, Logical Methods in Computer Science, vol. 10, n°1: 18, p. 1-21

Lampis M. (2014), Improved Inapproximability for TSP, Theory of Computing, vol. 10, n°9, p. 217-236

Lampis M. (2013), Parameterized maximum path coloring, Theoretical Computer Science, vol. 511, p. 42-53

Bar-Noy A., Lampis M. (2012), Online maximum directed cut, Journal of Combinatorial Optimization, vol. 24, n°1, p. 52-64

Lampis M. (2012), Algorithmic Meta-theorems for Restrictions of Treewidth, Algorithmica, vol. 64, n°1, p. 19-37

Bar-Noy A., Cheilaris P., Lampis M., Mitsou V., Zachos S. (2012), Ordered coloring of grids and related graphs, Theoretical Computer Science, vol. 444, p. 40-51

Achilleos A., Lampis M., Mitsou V. (2012), Parameterized Modal Satisfiability, Algorithmica, vol. 64, n°1, p. 38-55

Communications avec actes

Lampis M. (2023), First Order Logic on Pathwidth Revisited Again, in Kousha Etessami ; Uriel Feige ; Gabriele Puppis, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 132:1-132:17 p.

Lampis M., Vasilakis M. (2023), Structural Parameterizations for Two Bounded Degree Problems Revisited, in Inge Li Gørtz ; Martin Farach-Colto ; Simon J. Puglisi ; Grzegorz Herman, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 77:1-77:16 p.

Hanaka T., Lampis M. (2022), Hedonic Games and Treewidth Revisited, in , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 64:1–64:16 p.

Lampis M. (2022), Determining a Slater Winner Is Complete for Parallel Access to NP, in , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 45:1–45:14 p.

Gourvès L., Harutyunyan A., Lampis M., Melissinos N. (2021), Filling Crosswords is Very Hard, in , Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Dublois L., Lampis M., Paschos V. (2021), Upper Dominating Set: Tight Algorithms for Pathwidth and Sub-exponential Approximation, in Tiziana Calamoneri ; Federico Corò, Berlin Heidelberg, Springer International Publishing, 202-215 p.

Lampis M. (2021), Minimum Stable Cut and Treewidth, in Nikhil Bansal ; Emanuela Merelli ; James Worrell, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 92:1--92:16 p.

Harutyunyan A., Lampis M., Melissinos N. (2021), Digraph Coloring and Distance to Acyclicity, in Markus Bläser, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 41:1-41:15 p.

Lampis M., Mitsou V. (2021), Fine-Grained Meta-Theorems for Vertex Integrity, in Hee-Kap Ahn ; Kunihiko Sadakane, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 34:1--34:15 p.

Belmonte R., Hanaka T., Kanzaki M., Kiyomi M., Kobayashi Y., Kobayashi Y., Lampis M., Ono H., Otachi Y. (2020), Parameterized Complexity of (A,ℓ)-Path Packing, in Leszek Gąsieniec ; Ralf Klasing ; Tomasz Radzik, Berlin Heidelberg, Springer International Publishing, 43-55 p.

Belmonte R., Kim E., Lampis M., Mitsou V., Otachi Y. (2020), Grundy Distinguishes Treewidth from Pathwidth, in Public, John Q.; Access, Joan R., Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 23:1–23:27 p.

Katsikarelis I., Lampis M., Paschos V. (2020), Improved (In-)Approximability Bounds for d-Scattered Set, in Evripidis Bampis ; Nicole Megow, Berlin Heidelberg, Springer International Publishing, 202-216 p.

DUBLOIS L., Lampis M., Paschos V. (2020), New Algorithms for Mixed Dominating Set, in Yixin Cao ; Marcin Pilipczuk, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 9:1--9:17 p.

Dublois L., Hanaka T., Khosravian Ghadikolaei M., Lampis M., Melissinos N. (2020), (In)approximability of Maximum Minimal FVS, in Yixin Cao ; Siu-Wing Cheng ; Minming Li, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 3:1-3:14 p.

Belmonte R., Hanaka T., Lampis M., Ono H., Otachi Y. (2019), Independent Set Reconfiguration Parameterized by Modular-Width, in Ignasi Sau, Dimitrios M. Thilikos, Graph-Theoretic Concepts in Computer Science (WG 2019), Springer International Publishing, 285-297 p.

Belmonte R., Kim E., Lampis M., Mitsou V., Otachi Y., Sikora F. (2019), Token Sliding on Split Graphs, in Rolf Niedermeier, Christophe Paul, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 13:1--13:17 p.

Harutyunyan A., Lampis M., Lozin V., Monnot J. (2019), Maximum Independent Sets in Subcubic Graphs: New Results, in Ignasi Sau, Dimitrios M. Thilikos, Graph-Theoretic Concepts in Computer Science (WG 2019), Springer International Publishing, 40-52 p.

Belmonte R., Hanaka T., Katsikarelis I., Lampis M., Ono H., Otachi Y. (2019), Parameterized Complexity of Safe Set, in Pinar Heggernes, Algorithms and Complexity (CIAC 2019), Springer International Publishing, 38-49 p.

Lampis M., Mengel S., Mitsou V. (2018), QBF as an Alternative to Courcelle’s Theorem, in Olaf Beyersdorff; Christoph M. Wintersteiger, Theory and Applications of Satisfiability Testing – SAT 2018, 21st International Conference, SAT 2018, Held as Part of the Federated Logic Conference, FloC 2018, Oxford, UK, July 9–12, 2018, Proceedings, Springer International Publishing, 235-252 p.

Katsikarelis I., Lampis M., Paschos V. (2018), Structurally Parameterized d-Scattered Set, in Andreas Brandstädt; Ekkehard Köhler; Klaus Meer, Graph-Theoretic Concepts in Computer Science, 44th International Workshop, WG 2018, Cottbus, Germany, June 27–29, 2018, Proceedings, Springer International Publishing, 292-305 p.

Lampis M. (2018), Finer Tight Bounds for Coloring on Clique-Width, in Ioannis Chatzigiannakis ; Christos Kaklamanis ; Dániel Marx ; Donald Sannella, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 86:1--86:14 p.

Belmonte R., Lampis M., Mitsou V. (2018), Parameterized (Approximate) Defective Coloring, in Rolf Niedermeier ; Brigitte Vallée, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 10:1--10:15 p.

Belmonte R., Khosravian Ghadikolaei M., Kiyomi M., Lampis M., Otachi Y. (2018), How Bad is the Freedom to Flood-It?, in Hiro Ito ; Stefano Leonardi ; Linda Pagli ; Giuseppe Prencipe, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 5:1--5:13 p.

Hanaka T., Katsikarelis I., Lampis M., Otachi Y., Sikora F. (2018), Parameterized Orientable Deletion, in David Eppstein, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 24:1-24:13 p.

Belmonte R., Hanaka T., Katsikarelis I., Kim E., Lampis M. (2018), New Results on Directed Edge Dominating Set, in Igor Potapov ; Paul Spirakis ; James Worrell, elsevier, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 67:1-67:16 p.

Belmonte R., Lampis M., Mitsou V. (2017), Defective Coloring on Classes of Perfect Graphs, in Hans L. Bodlaender; Gerhard J. Woeginger, Graph-Theoretic Concepts in Computer Science, 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers, Springer International Publishing, 113-126 p.

Katsikarelis I., Lampis M., Paschos V. (2017), Structural Parameters, Tight Bounds, and Approximation for (k, r)-Center, in Yoshio Okamoto ; Takeshi Tokuyama, elsevier, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 50:1-50:13 p.

Bonnet E., Lampis M., Paschos E. (2016), Time-Approximation Trade-offs for Inapproximable Problems, in Nicolas Ollinger, Heribert Vollmer, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Orléans, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 22:1-22:14 p.

Fotakis D., Lampis M., Paschos E. (2016), Sub-exponential Approximation Schemes for CSPs: From Dense to Almost Sparse, in Nicolas Ollinger, Heribert Vollmer, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Orléans, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 37:1--37:14 p.

Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2016), Upper Domination : Complexity and Approximation, in Veli Mäkinen, Simon J. Puglisi, Leena Salmela, Combinatorial Algorithms. 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings, Berlin Heidelberg, Springer, 241-252 p.

Bazgan C., Brankovic L., Casel K., Fernau H., Jansen K., Klein K-M., Lampis M., Liedloff M., Monnot J., Paschos V. (2016), Algorithmic Aspects of Upper Domination: A Parameterized Perspective, in Riccardo Dondi, Guillaume Fertin, Giancarlo Mauri, Algorithmic Aspects in Information and Management. 11th International Conference, AAIM 2016, Bergamo, Italy, July 18-20, 2016, Proceedings, Berlin Heidelberg, Springer, 113-124 p.

Angel E., Bampis E., Escoffier B., Lampis M. (2016), Parameterized Power Vertex Cover, in Pinar Heggernes, Graph-Theoretic Concepts in Computer Science 42nd International Workshop, WG 2016, Istanbul, Turkey, June 22-24, 2016, Revised Selected Papers, Springer, 97-108 p.

Dell H., Kim E., Lampis M., Mitsou V., Mömke T. (2015), Complexity and Approximability of Parameterized MAX-CSPs, in Thore Husfeldt, Iyad Kanj, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), Patras, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 294-306 p.

Gajarsky J., Lampis M., Makino K., Mitsou V., Ordyniak S. (2015), Parameterized Algorithms for Parity Games, in Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella, Mathematical Foundations of Computer Science 2015 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II, Springer, 336-347 p.

Lampis M. (2014), Parameterized Approximation Schemes Using Graph Widths, in Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias, Automata, Languages, and Programming 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, Springer, 775-786 p.

Lampis M., Mitsou V. (2014), The Computational Complexity of the Game of Set and Its Theoretical Applications, in Alberto Pardo, Alfredo Viola, LATIN 2014: Theoretical Informatics 11th Latin American Symposium, Montevideo, Uruguay, March 31–April 4, 2014. Proceedings, Springer, 24-34 p.

Lampis M., Makino K., Mitsou V., Uno Y. (2014), Parameterized Edge Hamiltonicity, in Dieter Kratsch, Ioan Todinca, Graph-Theoretic Concepts in Computer Science 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers, Springer, 348-359 p.

Lampis M. (2013), Model Checking Lower Bounds for Simple Graphs, in Fedor V. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, David Peleg, Automata, Languages, and Programming 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Springer, 673-683 p.

Gajarský J., Lampis M., Ordyniak S. (2013), Parameterized Algorithms for Modular-Width, in Gregory Gutin, Stefan Szeider, Parameterized and Exact Computation 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers, Springer, 163-176 p.

Karpinski M., Lampis M., Schmied R. (2013), New Inapproximability Bounds for TSP, in Leizhen Cai, Siu-Wing Cheng, Tak-Wah Lam, Algorithms and Computation 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings, Springer, 568-578 p.

Lampis M. (2012), Improved Inapproximability for TSP, in Anupam Gupta, Klaus Jansen, José Rolim, Rocco Servedio, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings, Springer, 243-253 p.

Lampis M., Mitsou V., Sołtys K. (2012), Scrabble Is PSPACE-Complete, in Evangelos Kranakis, Danny Krizanc, Flaminia Luccio, Fun with Algorithms 6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012. Proceedings, Springer, 258-269 p.