73 citations · 73 across the 1 of their papers we have counts for
2 papers
cs.DM2005★ 6 cited
Bidimensionality, Map Graphs, and Grid Minors
Erik D. Demaine, MohammadTaghi Hajiaghayi
In this paper we extend the theory of bidimensionality to two families of graphs that do not exclude fixed minors: map graphs and power graphs. In both cases we prove a polynomial…
math.CO2003★ 73 cited
The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
MohammadTaghi Hajiaghayi, Gregory B. Sorkin
We prove that a random 3-SAT instance with clause-to-variable density less than 3.52 is satisfiable with high probability. The proof comes through an algorithm which selects (and s…