BibTeX
@ARTICLE{
         Lulfesmann2014Seg,
       title = "Sub-exponential graph coloring algorithm for stencil-based {J}acobian computations",
       journal = "Journal of Computational Science",
       volume = "5",
       number = "1",
       pages = "1--11",
       year = "2014",
       issn = "1877-7503",
       doi = "http://dx.doi.org/10.1016/j.jocs.2013.06.002",
       url = "http://www.sciencedirect.com/science/article/pii/S1877750313000781",
       author = "M. L{\"u}lfesmann and K. Kawarabayashi",
       abstract = "Abstract Partial differential equations can be discretized using a regular
         Cartesian grid and a stencil-based method to approximate the partial derivatives. The computational
         effort for determining the associated Jacobian matrix can be reduced. This reduction can be modeled
         as a (grid) coloring problem. Currently, this problem is solved by using a heuristic approach for
         general graphs or by developing a formula for every single stencil. We introduce a sub-exponential
         algorithm using the Lipton–Tarjan separator in a divide-and-conquer approach to compute an
         optimal coloring. The practical relevance of the algorithm is evaluated when compared with an
         exponential algorithm and a greedy heuristic.",
       keywords = "Sparsity exploitation",
       ad_theotech = "graph coloring, Sparsity"
}