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…
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…
Sparse graphs with local covering conditions on edges
Debsoumya Chakraborti, Amirali Madani, Anil Maheshwari +1
In 1988, Erdős suggested the question of minimizing the number of edges in a connected -vertex graph where every edge is contained in a triangle. Shortly after, Catlin, Grossman…
Distance-Preserving Graph Compression Techniques
Amirali Madani, Anil Maheshwari
We study the problem of distance-preserving graph compression for weighted paths and trees. The problem entails a weighted graph with non-negative weights, and a subse…