13 citations · 46 across the 31 of their papers we have counts for
57 papers
Pure Nash Equilibria in Graphical Games of Bounded Width Revisited
Michael Lampis, Yiren Lu
We revisit the complexity of deciding whether a graphical game admits a pure Nash equilibrium (PNE) parameterized by standard measures of the input graph, such as treewidth. The na…
Parameterized Capacitated Vertex Cover Revisited
Michael Lampis, Manolis Vasilakis
Capacitated Vertex Cover is a generalization of Vertex Cover where we seek a set of vertices covering all edges, but with the added constraint that for each vertex we are given…
Forcing a unique minimum spanning tree and a unique shortest path
Tatsuya Gima, Andreas Grigorjew, Yasuaki Kobayashi +7
A forcing set in a combinatorial problem is a set of elements such that there is a unique solution that contains all the elements in . An anti-forcing set is the symmetric c…
Broadcasting under Structural Restrictions
Yudai Egami, Tatsuya Gima, Tesshu Hanaka +7
In the Telephone Broadcast problem we are given a graph with a designated source vertex . Our goal is to transmit a message, which is initially known only to ,…
Structural Parameterizations for Induced and Acyclic Matching
Michael Lampis, Manolis Vasilakis
We revisit the (structurally) parameterized complexity of Induced Matching and Acyclic Matching, two problems where we seek to find a maximum independent set of edges whose endpoin…
Parameterized Spanning Tree Congestion
Michael Lampis, Valia Mitsou, Edouard Nemery +3
In this paper we study the Spanning Tree Congestion problem, where we are given a graph and are asked to find a spanning tree of minimum maximum congestion. Here, the…