4 papers
Triangle-Covered Graphs: Algorithms, Complexity, and Structure
Amirali Madani, Anil Maheshwari, Babak Miraftab +1
The widely studied edge modification problems ask how to minimally alter a graph to satisfy certain structural properties. In this paper, we introduce and study a new edge modifica…
Partial Domination in Some Geometric Intersection Graphs and Some Complexity Results
Madhura Dutta, Anil Maheshwari, Subhas C. Nandy +1
{\em Partial domination problem} is a generalization of the {\em minimum dominating set problem} on graphs. Here, instead of dominating all the nodes, one asks to dominate at least…
Deciding if a DAG is Interesting is Hard
Jean-Lou De Carufel, Anil Maheshwari, Saeed Odak +3
The \emph{interestingness score} of a directed path in an edge-weighted directed graph is defined as $\texttt{score}(Î ) := \sum_{i=1}^\ell w…
Algorithms and Hardness Results for the -Cover Problem
Amirali Madani, Anil Maheshwari, Babak Miraftab +1
A connected graph has a -cover if each of its edges is contained in at least cliques of order . Motivated by recent advances in extremal combinatorics and the l…