Vikash Tripathi

dblp:239/4070 · DBLP profile ↗
← Back
11ranked-venue papers
2as first author
9since 2021 · last 2025
0000-0002-5703-0417ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 9 · 2 first-author · 7 since 2021Artificial intelligence and machine learning · 2 · 2 since 2021
YearPublicationVenuePosition
2025 On the Parameterized Complexity of Cosecure Domination
D. Karthika, R. Muthucumaraswamy, V. P. Abidha, Pradeesha Ashok, Sriram Bhyravarapu, Sayani Das, Saket Saurabh 0001, Ayush Sawlani, Vikash Tripathi
FCT9
2025 Budget-feasible egalitarian allocation of conflicting jobs
abstract
Allocating conflicting jobs among individuals while respecting a budget constraint for each individual is an optimization problem that arises in various real-world scenarios. In this paper, we consider the situation where each individual derives some satisfaction from each job. We focus on finding a feasible allocation of conflicting jobs that maximize egalitarian cost, i.e., the satisfaction of the individual who is worst-off. To the best of our knowledge, this is the first paper to combine egalitarianism, budget-feasibility, and conflict-freeness in allocations. We provide a systematic study of the computational complexity of finding budget-feasible conflict-free egalitarian allocation and show that our problem generalizes a large number of classical optimization problems. Therefore, unsurprisingly, our problem is NP-hard even for two individuals and when there is no conflict between any jobs. We show that the problem admits algorithms when studied in the realm of approximation algorithms and parameterized algorithms with a host of natural parameters that match and in some cases improve upon the running time of known algorithms.
Sushmita Gupta, Pallavi Jain 0001, A. Mohanapriya, Vikash Tripathi
Auton. Agents Multi Agent Syst.4
2025 More on the complexity of defensive domination in graphs
Michael A. Henning, Arti Pandey, Vikash Tripathi
Discret. Appl. Math.3
2024 Parameterized Complexity of Paired Domination
Nikita Andreev, Ivan Bliznets, Madhumita Kundu, Saket Saurabh 0001, Vikash Tripathi, Shaily Verma
IWOCA5
2024 Algorithms and hardness results for edge total domination problem in graphs
Michael A. Henning, Arti Pandey, Gopika Sharma, Vikash Tripathi
Theor. Comput. Sci.4
2023 A linear-time algorithm for semitotal domination in strongly chordal graphs
Vikash Tripathi, Arti Pandey, Anil Maheshwari
Discret. Appl. Math.1
2023 Algorithmic aspects of paired disjunctive domination in graphs
Michael A. Henning, Arti Pandey, Vikash Tripathi
Theor. Comput. Sci.3
2022 Complexity of paired domination in AT-free and planar graphs
Vikash Tripathi, Ton Kloks, Arti Pandey, Kaustav Paul, Hung-Lung Wang
Theor. Comput. Sci.1
2021 Approximation Algorithm and Hardness Results for Defensive Domination in Graphs
Michael A. Henning, Arti Pandey, Vikash Tripathi
COCOA3
2020 Complexity and Algorithms for Semipaired Domination in Graphs
Michael A. Henning, Arti Pandey, Vikash Tripathi
Theory Comput. Syst.3
2019 Complexity and Algorithms for Semipaired Domination in Graphs
Michael A. Henning, Arti Pandey, Vikash Tripathi
IWOCA3