CsegGraph: a graph colouring instance generator

References

• Boisvert , R. F. , Pozo , R. , Remington , K. , Barrett , R. and Dongarra , J. J. 1997 . The matrix market: A web resource for test matrix collections , Edited by: Boisvert , R. F. 125 – 137 . London : Chapman and Hall . Quality of Numerical Software, Assessment and Enhancement
   Google Scholar
• Brélaz , D. 1979 . New methods to color the vertices of a graph . Commun. ACM , 22 : 251 – 256 .
   Web of Science ®Google Scholar
• Bui , T. N. , Nguyen , T. H. , Patel , C. M. and Phan , K. A.T. 2008 . An ant-based algorithm for coloring graphs . Discrete Appl. Math. , 156 : 190 – 200 .
   Web of Science ®Google Scholar
• Caramia , M. and Dell'Olmo , P. 2008 . Coloring graphs by iterated local search traversing feasible and infeasible solutions . Discrete Appl. Math. , 156 : 201 – 217 .
   Web of Science ®Google Scholar
• Coleman , T. F. and Moré , J. J. 1983 . Estimation of sparse Jacobian matrices and graph colouring problems . SIAM J. Numer. Anal. , 20 : 187 – 209 .
   Web of Science ®Google Scholar
• Coleman , T. F. , Garbow , B. S. and Moré , J. J. 1984 . Software for estimating sparse Jacobian matrices . ACM Trans. Math. Softw. , 10 : 329 – 345 .
   Web of Science ®Google Scholar
• Culberson , J. and Gent , I. 2001 . Frozen development in graph coloring . Theor. Comput. Sci. , 265 : 227 – 264 .
   Google Scholar
• Dongarra , J. , Lumsdaine , A. , Pozo , R. and Remington , K. 1994 . Proceedings of the Second Object Oriented Numerics Conference . 1994 . A sparse matrix library in C++ for high performance architectures , pp. 214 – 218 .
   Google Scholar
• Duff , I. S. , Grimes , R. G. and Lewis , J. G. 1989 . Sparse matrix test problems . ACM Trans. Math. Softw. , 15 : 1 – 14 .
   Web of Science ®Google Scholar
• Galinier , P. , Hertz , A. and Zufferey , N. 2008 . An adaptive memory algorithm for the k-coloring problem . Discrete Appl. Math. , 156 : 267 – 279 .
   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 & Co .
   Google Scholar
• Gebremedhin , A. H. , Manne , F. and Pothen ,  A. 2005 . What color is your Jacobian? Graph coloring for computing derivatives . SIAM Rev. , 47 : 629 – 705 .
   Web of Science ®Google Scholar
• Griewank , A. 2000 . Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation , Philadelphia, PA : Number 19 in Frontiers in Applied Mathematics SIAM .
   Google Scholar
• Hossain , S. and Steihaug , T. 2002 . Sparsity issues in the computation of Jacobian matrices , Edited by: Mora , T. 123 – 130 . New York : ACM . Proceedings of the International Symposium on Symbolic and Algebraic Computing (ISSAC)
   Google Scholar
• Hossain , S. and Steihaug , T. 2008 . Graph coloring in the estimation of sparse derivative matrices: Instances and applications . Discrete Appl. Math. , 156 : 280 – 288 .
   Web of Science ®Google Scholar
• Hossain , S. and Steihaug , T. 2003 . “ Optimal direct determination of sparse Jacobian matrices ” . In Tech. Rep , Vol. 254 , Norway : Department of Informatics, University of Bergen . October, Optim. Methods Softw., to appear
   Google Scholar
• Johnson , D. S. , Aragon , C. R. , McGeoch , L. A. and Schevon , C. 1991 . Optimization by simulated annealing: an experimental evaluation; part II, graph coloring and number partitioning . Oper. Res. , 39 : 378 – 406 .
   Web of Science ®Google Scholar
• Johnson , D. S. , Mehrotra , A. and Trick , M. A. 2008 . Preface: Special issue on computational methods for graph coloring and its generalizations . Discrete Appl. Math. , 156 : 145 – 146 .
   Google Scholar
• Kugele , S. October 2006 . Efficient solving of combinatorial problems using sat-solvers . Technische Universität München, Available at www7.in.tum.de/um/bibdb/kugele/kugele_diploma06.pdf (accessed May 2009)
   Google Scholar
• Mehrotra , A. and Trick , M. A. 1996 . A column generation approach for graph coloring . INFORMS J. Comput. , 8 : 344 – 354 .
   Google Scholar
• Méndez-Díaz , I. and Zabala , P. 2006 . A branch-and-cut algorithm for graph coloring . Discrete Appl. Math. , 154 : 826 – 847 .
   Web of Science ®Google Scholar
• Méndez-Díaz , I. and Zabala , P. 2008 . A cutting plane algorithm for graph coloring . Discrete Appl. Math. , 156 : 159 – 179 .
   Web of Science ®Google Scholar
• Newsam , G. N. and Ramsdell , J. D. 1983 . Estimation of sparse Jacobian matrices . SIAM J. Alg. Disc. Methods , 4 : 404 – 417 .
   Google Scholar
• Van Gelder , A. 2008 . Another look at graph colouring via propositional satisfiability . Discrete Appl. Math. , 156 : 230 – 243 .
   Web of Science ®Google Scholar