Skip to main content

15 Result(s)

within Conference Paper Remove this filter Pallavi Jain Remove this filter

and

  1. No Access

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

    Pallavi Jain, Manveer Singh Rathore in LATIN 2024: Theoretical Informatics (2024)

  2. No Access

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

    Pallavi Jain, Lawqueen Kanesh, Fahad Panolan… in LATIN 2024: Theoretical Informatics (2024)

  3. No Access

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

    Sushmita Gupta, Pallavi Jain… in SOFSEM 2023: Theory and Practice of Comput… (2023)

  4. No Access

    Chapter and Conference Paper

    Preserving Consistency for Liquid Knapsack Voting

    Liquid Democracy (LD) uses transitive delegations to facilitate joint decision making. In its simplest form, it is used for binary decisions, however its promise holds also for more advanced voting settings. H...

    Pallavi Jain, Krzysztof Sornat, Nimrod Talmon in Multi-Agent Systems (2022)

  5. No Access

    Chapter and Conference Paper

    Gehrlein Stable Committee with Multi-modal Preferences

    Inspired by Gehrlein stability in multiwinner election, in this paper, we define several notions of stability that are applicable in multiwinner elections with multimodal preferences, a model recently proposed...

    Sushmita Gupta, Pallavi Jain, Daniel Lokshtanov, Sanjukta Roy… in Algorithmic Game Theory (2022)

  6. No Access

    Chapter and Conference Paper

    Gerrymandering on Graphs: Computational Complexity and Parameterized Algorithms

    This paper studies gerrymandering on graphs from a computational viewpoint (introduced by Cohen-Zemach et al. [AAMAS 2018] and continued by Ito et al. [AAMAS 2019]). Our contributions are two-fold: conceptual and...

    Sushmita Gupta, Pallavi Jain, Fahad Panolan, Sanjukta Roy… in Algorithmic Game Theory (2021)

  7. No Access

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

    Sushmita Gupta, Pallavi Jain, Aditya Petety… in SOFSEM 2021: Theory and Practice of Comput… (2021)

  8. No Access

    Chapter and Conference Paper

    Circumventing Connectivity for Kernelization

    Classical vertex subset problems demanding connectivity are of the following form: given an input graph G on n vertices and an integer k, find a set S of at most k vertices that satisfies a property and G[S] is c...

    Pallavi Jain, Lawqueen Kanesh, Shivesh Kumar Roy… in Algorithms and Complexity (2021)

  9. No Access

    Chapter and Conference Paper

    Vertex Deletion on Split Graphs: Beyond 4-Hitting Set

    In vertex deletion problems on graphs, the task is to find a set of minimum number of vertices whose deletion results in a graph with some specific property. The class of vertex deletion problems contains seve...

    Pratibha Choudhary, Pallavi Jain, R. Krithika, Vibha Sahlot in Algorithms and Complexity (2019)

  10. No Access

    Chapter and Conference Paper

    Quadratic Vertex Kernel for Split Vertex Deletion

    A graph is called a split graph if its vertex set can be partitioned into a clique and an independent set. Split graphs have rich mathematical structure and interesting algorithmic properties making it one of ...

    Akanksha Agrawal, Sushmita Gupta, Pallavi Jain, R. Krithika in Algorithms and Complexity (2019)

  11. No Access

    Chapter and Conference Paper

    List Colouring of Graphs Using a Genetic Algorithm

    The List Colouring Problem (LCP) is an NP-Hard optimization problem in which the goal is to find a proper list colouring of a graph G = (V, E) such that the number of colours used is minimized. This paper deals w...

    Aditi Khandelwal, Pallavi Jain, Gur Saran in Smart Computing and Informatics (2018)

  12. No Access

    Chapter and Conference Paper

    Hitting and Covering Partially

    d-Hitting Set and d-Set Cover are among the classical NP-hard problems. In this paper, we study variants of d-Hitting Set and d-Set Cover, which are called Partial d -Hitting Set (Partial

    Akanksha Agrawal, Pratibha Choudhary, Pallavi Jain… in Computing and Combinatorics (2018)

  13. No Access

    Chapter and Conference Paper

    Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized

    Let \(\mathrm{\Pi }\) be a family of graphs. In the classical

    Pallavi Jain, Lawqueen Kanesh… in Computer Science – Theory and Applications (2018)

  14. No Access

    Chapter and Conference Paper

    Mixed Dominating Set: A Parameterized Perspective

    In the mixed dominating set (mds) problem, we are given an n-vertex graph G and a positive integer k, and the objective is to decide whether there exists a set

    Pallavi Jain, M. Jayakrishnan, Fahad Panolan… in Graph-Theoretic Concepts in Computer Scien… (2017)

  15. No Access

    Chapter and Conference Paper

    Branch and Bound Algorithm for Vertex Bisection Minimization Problem

    Vertex Bisection Minimization problem (VBMP) consists of partitioning the vertex set V of a graph G = (V, E) into two sets B and B′ where ...

    Pallavi Jain, Gur Saran, Kamal Srivastava in Advanced Computing and Communication Techn… (2016)