Coloring Jacobians revisited: a new algorithm for star and~acyclic bicoloring

References

• Ausiello , G. , Crescenzi , P. , Gambosi , G. , Kann , V. , Marchetti-Spaccamela , A. and Protasi , M. 1999 . Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties , Berlin : Springer-Verlag .
   Google Scholar
• Balcázar , J. , Díaz , J. and Gabarró , J. 1988 . Structural Complexity I , Berlin : Springer-Verlag .
   Google Scholar
• Bellare , M. , Goldreich , O. and Sudan , M. 1998 . Free bits, PCPs and non-approximability – towards tight results . SIAM J. Comput. , 27 : 804 – 915 .
   Web of Science ®Google Scholar
• Cai , L. and Juedes , D. 1999 . The approximability of bipartite path coloring and related problems unpublished manuscript
   Google Scholar
• Coleman , T. F. and Cai , J.-Y. 1986 . The cyclic coloring problem and estimation of sparse Hessian matrices . SIAM J. Algebr. Discrete Methods , 7 ( 2 ) : 221 – 235 .
   Google Scholar
• Coleman , T. F. and More , J. J. 1984 . Estimation of sparse Hessian matrices and graph coloring problems . Math. Program. , 28 ( 3 ) : 243 – 270 .
   Web of Science ®Google Scholar
• Coleman , T. F. and Verma , A. 1998 . The efficient computation of sparse Jacobian matrices using automatic differentiation . SIAM J. Sci. Comput. , 18 ( 4 ) : 1210 – 1233 .
   Web of Science ®Google Scholar
• Feige , U. and Kilian , J. 1998 . Zero knowledge and the chromatic number . J. Comput. System Sci. , 57 ( 2 ) : 187 – 199 .
   Web of Science ®Google Scholar
• Garey , M. R. and Johnson , D. S. 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness , New York : W. H. Freeman and Company .
   Google Scholar
• Gebremedhin , A. H. , Manne , F. and Pothen , A. 2005 . What color is your Jacobian? Graph coloring for computing derivatives . SIAM Rev. , 47 ( 4 ) : 629 – 705 .
   Web of Science ®Google Scholar
• Gebremedhin , A. H. , Tarafdar , A. , Manne , F. and Pothen , A. 2007 . New acyclic and star coloring algorithms with application to computing Hessians . SIAM J. Sci. Comput. , 29 ( 3 ) : 1042 – 1072 .
   Web of Science ®Google Scholar
• Giering , R. and Kaminski , T. 1998 . Recipes for adjoint code construction . ACM Trans. Math. Software , 24 ( 4 ) : 437 – 474 .
   Web of Science ®Google Scholar
• Griewank , A. 2000 . Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation , Philadelphia : SIAM .
   Google Scholar
• Griewank , A. , Juedes , D. and Utke , J. 1996 . ADOL-C: A package for the automatic differentation of algorithms written in C/C++ . ACM Trans. Math. Software , 22 : 131 – 167 .
   Web of Science ®Google Scholar
• Halld\'orsson , M. M. 1993 . A still better performance guarantee for approximate graph coloring . Inform. Process. Lett. , 45 ( 1 ) : 19 – 23 .
   Web of Science ®Google Scholar
• Heimbach , P. , Hill , C. and Giering , R. 2005 . An efficient exact adjoint of the parallel MIT general circulation model, generated via automatic differentiation . Future Gener. Comput. Syst. , 21 ( 8 ) : 1356 – 1371 .
   Web of Science ®Google Scholar
• Hendrickson , B. and Pothen , A. Combinatorial Scientific Computing: The Enabling Power of Discrete Algorithms in Computational Science . Proceedings of the Seventh International Meeting on High Performance Computing for Computational Science VECPAR06 . Berlin : Springer-Verlag . Lecture Notes in Computer Science Vol. 4395
   Google Scholar
• Hossain , S. and Steihaug , T. 1998 . Computing a sparse Jacobian matrix by rows and columns . Optim. Methods Softw. , 10 : 33 – 48 .
   Web of Science ®Google Scholar
• Hossain , S. and Steihaug , T. 2008 . Graph coloring in the estimation of sparse derivative matrices: Instances and applications . Discrete Appl. Math. , 156 ( 2 ) : 280 – 288 .
   Web of Science ®Google Scholar
• Johnson , D. S. Worst case behaviour of graph coloring algorithms . Proceedings of the 5th South-Eastern Conference on Combinatorics, Graph Theory, and Computing . pp. 513 – 528 . Winnipeg , , Canada : Utilitas Mathematica Publishing .
   Google Scholar
• Juedes , D. 1991 . “ A taxonomy of automatic differentiation tools ” . In Automatic Differentiation of Algorithms: Theory, Implementation, and Application , Edited by: Griewank , A. and Corliss , G.F. 315 – 329 . Philadelphia , PA : SIAM .
   Google Scholar
• Lund , C. and Yannakakis , M. 1994 . On the hardness of approximating minimization problems . J. ACM , 41 ( 5 ) : 960 – 981 .
   Web of Science ®Google Scholar
• McCormick , S. T. 1983 . Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem . Math. Program. , 26 : 153 – 171 .
   Web of Science ®Google Scholar
• Utke , J. , Naumann , U. , Fagan , M. , Tallent , N. , Strout , M. , Heimbach , P. , Hill , C. and Wunsch , C. 2008 . OpenAD/F: A modular open-source tool for automatic differentiation of Fortran codes . ACM Trans. Math. Software , 34 ( 4 ) : 1 – 36 .
   Web of Science ®Google Scholar
• Zuckerman , D. 2007 . Linear degree extractors and the inapproximability of max clique and chromatic number . Theory Comput. , 3 : 103 – 128 .
   PubMedGoogle Scholar