66 citations · 323 across the 55 of their papers we have counts for
7 papers · 1 filter
Tree decompositions meet induced matchings: beyond Max Weight Independent Set
Paloma T. Lima, Martin Milanič, Peter Muršič +3
For a tree decomposition of a graph , by we denote the size of a largest induced matching in all of whose edges intersect one bag of $\mathcal…
Tree decompositions with bounded independence number: beyond independent sets
Martin Milanič, Paweł Rzążewski
We continue the study of graph classes in which the treewidth can only be large due to the presence of a large clique, and, more specifically, of graph classes with bounded tree-in…
New Algorithms for Weighted -Domination and Total -Domination Problems in Proper Interval Graphs
Nina Chiarelli, Tatiana Romina Hartinger, Valeria Alejandra Leoni +2
Given a positive integer , a -dominating set in a graph is a set of vertices such that every vertex not in the set has at least neighbors in the set. A total -domi…
Minimum Connected Transversals in Graphs: New Hardness Results and Tractable Cases Using the Price of Connectivity
Nina Chiarelli, Tatiana R. Hartinger, Matthew Johnson +2
We perform a systematic study in the computational complexity of the connected variant of three related transversal problems: Vertex Cover, Feedback Vertex Set, and Odd Cycle Trans…
Recognizing k-equistable graphs in FPT time
Eun Jung Kim, Martin Milanic, Oliver Schaudt
A graph is called equistable if there exist a positive integer and a weight function such that is a maximal stable set of …
Latency-Bounded Target Set Selection in Social Networks
Ferdinando Cicalese, Gennaro Cordasco, Luisa Gargano +2
Motivated by applications in sociology, economy and medicine, we study variants of the Target Set Selection problem, first proposed by Kempe, Kleinberg and Tardos. In our scenario…
Competitive Boolean Function Evaluation: Beyond Monotonicity, and the Symmetric Case
Ferdinando Cicalese, Travis Gagie, Eduardo Laber +1
We study the extremal competitive ratio of Boolean function evaluation. We provide the first non-trivial lower and upper bounds for classes of Boolean functions which are not inclu…