13 citations · 46 across the 31 of their papers we have counts for
6 papers · 1 filter
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…
Parameterized Maximum Node-Disjoint Paths
Michael Lampis, Manolis Vasilakis
We revisit the Maximum Node-Disjoint Paths problem, the natural optimization version of Node-Disjoint Paths, where we are given a graph , pairs of vertices and…
The Primal Pathwidth SETH
Michael Lampis
Motivated by the importance of dynamic programming (DP) in parameterized complexity, we consider several fine-grained questions, such as the following examples: (i) can Dominating…
Core Stability in Additively Separable Hedonic Games of Low Treewidth
Tesshu Hanaka, Noleen Köhler, Michael Lampis
Additively Separable Hedonic Game (ASHG) are coalition-formation games where we are given a graph whose vertices represent selfish agents and the weight of each edge denot…
Parameterized Vertex Integrity Revisited
Tesshu Hanaka, Michael Lampis, Manolis Vasilakis +1
Vertex integrity is a graph parameter that measures the connectivity of a graph. Informally, its meaning is that a graph has small vertex integrity if it has a small separator whos…
Parameterized Algorithms for Steiner Forest in Bounded Width Graphs
Andreas Emil Feldmann, Michael Lampis
In this paper we reassess the parameterized complexity and approximability of the well-studied Steiner Forest problem in several graph classes of bounded width. The problem takes a…