7 Result(s)
-
Chapter and Conference Paper
Sparsity in Covering Solutions
In the classical covering problems, the goal is to find a subset of vertices/edges that “covers” a specific structure of the graph. In this work, we initiate the study of the covering problems where given a gr...
-
Chapter and Conference Paper
Max-SAT with Cardinality Constraint Parameterized by the Number of Clauses
Max-SAT with cardinality constraint (CC-Max-SAT) is one of the classical NP-complete problems. In this problem, given a CNF-formula $$\varPhi ...
-
Article
Even More Effort Towards Improved Bounds and Fixed-Parameter Tractability for Multiwinner Rules
Multiwinner elections have proven to be a fruitful research topic with many real-world applications. We contribute to this line of research by improving the state of the art regarding the computational complex...
-
Chapter and Conference Paper
More Effort Towards Multiagent Knapsack
In this paper, we study two multiagent variants of the knapsack problem. Fluschnik et al. [AAAI 2019] studied the model in which each agent expresses its preference by assigning a utility to every item. They s...
-
Chapter and Conference Paper
Parameterized Complexity of d-Hitting Set with Quotas
In this paper we study a variant of the classic d -Hitting Set problem with lower and upper capacity constraints, say A and B, respectively. The input to the problem consists of a universe U, a set family, ...
-
Article
Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized
Let π be a family of graphs. In the classical π-Vertex Deletion problem, given a graph G and a positive integer k, the objective is to check whether there exists a subset S of at most k vertices such that G − S i...
-
Article
Parameterized Complexity of Conflict-Free Matchings and Paths
An input to a conflict-free variant of a classical problem \(\Gamma \)Γ, called Conflict-Free\(\Gamma \)Γ, consists of an instance I of \(\Gamma \)Γ coupled with a graph H, called the conflict graph. A solution t...
