Curriculum vitae

Lampis Michael

Maître de conférences
LAMSADE

michail.lampisping@lamsade.dauphinepong.fr
Tel : 01 44 05 40 50
Bureau : P622
Site web personnel

Biographie

Michael Lampis  is generally interested in the field of theoretical computer science and more specifically in algorithm design and analysis. Favorite topics include approximation algorithms and fixed-parameter tractability.

Dernières publications

Articles

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

Dublois L., Lampis M., Paschos V. (2021), New Algorithms for Mixed Dominating Set, Discrete Mathematics and Theoretical Computer Science, vol. 23, 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

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

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

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., 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

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

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

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

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

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

Communications avec actes

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.

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.

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.

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., 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.

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.

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.

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.

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.

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. (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. (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., 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.

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.

Retour à la liste