SIAM Journal on Discrete Mathematics · 2011 · 108 citations · 3 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsComputational GeometryEnumerative CombinatoricsGraph TheoryShortest Path AlgorithmsAll-pairs Shortest PathsComputational Complexity Of Graph AlgorithmsEnumerative Graph TheoryGeometric Graph TheoryGraph Theory ConnectivityGridsShortest Paths
In this paper, we conclude the calculation of the domination number of all $n\times m$ grid graphs. Indeed, we prove Chang's conjecture saying that for every $16\le n\le m$, $\gamma(G_{n,m})=\lfloor\frac{(n+2)(m+2)}{5}\rfloor -4$.
3
All-Pairs Shortest Paths with Real Weights in O(n 3/log n) Time
Timothy M. Chan · Algorithmica · 2007 · 76 citations