BibTeX
@ARTICLE{
         Juedes2012CJr,
       author = "Juedes, David and Jones, Jeffrey",
       title = "Coloring {J}acobians revisited: a new algorithm for star and acyclic bicoloring",
       journal = "Optimization Methods and Software",
       volume = "27",
       number = "2",
       pages = "295--309",
       year = "2012",
       doi = "10.1080/10556788.2011.606575",
       url = "http://www.tandfonline.com/doi/abs/10.1080/10556788.2011.606575",
       eprint = "http://www.tandfonline.com/doi/pdf/10.1080/10556788.2011.606575",
       abstract = "This paper presents a new polynomial-time algorithm, approximate star bicoloring
         (ASBC), for star bicoloring and acyclic bicoloring. These NP-complete combinatorial problems arise
         from problems associated with computing large sparse Jacobian matrices. The main results of this
         paper lie in approximation analysis related to these problems. In particular, it is shown that (i)
         both star and acyclic bicoloring can be approximated in polynomial time to the ratio O(n 2/3) and
         (ii) both star and acyclic bicoloring cannot be approximated to the ratio O(n 1/3-e) in polynomial
         time under reasonable complexity theoretic hypotheses. The ASBC algorithm is also analysed
         experimentally on a collection of realistic test cases from the Harwell–Boeing sparse
         matrix collection. The experimental results indicate that ASBC performs quite well in practice; the
         performance of the new algorithm always fell within the range of 1.53 and 6 times optimal on the
         given test sets.",
       ad_theotech = "Combinatorics, Sparsity"
}