{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T04:17:21Z","timestamp":1725769041222},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319041254"},{"type":"electronic","value":"9783319041261"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-04126-1_15","type":"book-chapter","created":{"date-parts":[[2014,1,7]],"date-time":"2014-01-07T22:16:13Z","timestamp":1389132973000},"page":"174-186","source":"Crossref","is-referenced-by-count":1,"title":["An Experimental Analysis of Vertex Coloring Algorithms on Sparse Random Graphs"],"prefix":"10.1007","author":[{"given":"Patrick","family":"Healy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Ju","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"15_CR1","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1145\/359094.359101","volume":"22","author":"D. Br\u00e9laz","year":"1979","unstructured":"Br\u00e9laz, D.: New methods to color the vertices of a graph. Communications of the ACM\u00a022(4), 251\u2013256 (1979)","journal-title":"Communications of the ACM"},{"issue":"4","key":"15_CR2","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1287\/mnsc.19.4.456","volume":"19","author":"J. Randall Brown","year":"1972","unstructured":"Randall Brown, J.: Chromatic scheduling and the chromatic number problem. Management Science\u00a019(4), 456\u2013463 (1972)","journal-title":"Management Science"},{"key":"15_CR3","unstructured":"Burke, E.K., Mare\u010dek, J., Parkes, A.J., Rudov\u00e1, H.: On a clique-based integer programming formulation of vertex colouring with applications in course timetabling. Technical Report NOTTCS-TR-2007-10, The University of Nottingham, Nottingham (2007)"},{"issue":"3","key":"15_CR4","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1016\/S0166-218X(02)00242-1","volume":"127","author":"L. Cai","year":"2003","unstructured":"Cai, L.: Parameterized complexity of vertex colouring. Discrete Applied Mathematics\u00a0127(3), 415\u2013429 (2003)","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR5","unstructured":"Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms, 2nd edn. McGraw-Hill Higher Education (2001)"},{"key":"15_CR6","unstructured":"Culberson, J.: Graph coloring programs (2001), \n                    \n                      http:\/\/webdocs.cs.ualberta.ca\/~joe\/Coloring\/Colorsrc\/index.html"},{"key":"15_CR7","unstructured":"Erd\u00f6s, P., R\u00e9nyi, A.: On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences, 17\u201361 (1960)"},{"issue":"8","key":"15_CR8","doi-asserted-by":"publisher","first-page":"2384","DOI":"10.1016\/j.cor.2005.09.010","volume":"34","author":"M. Gamache","year":"2007","unstructured":"Gamache, M., Hertz, A., Ouellet, J.O.: A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding. Computers & Operations Research\u00a034(8), 2384\u20132395 (2007)","journal-title":"Computers & Operations Research"},{"key":"15_CR9","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/800119.803884","volume-title":"Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC 1974","author":"M.R. Garey","year":"1974","unstructured":"Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete problems. In: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, STOC 1974, pp. 47\u201363. ACM, New York (1974)"},{"issue":"1","key":"15_CR10","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1287\/ijoc.1100.0436","volume":"24","author":"S. Gualandi","year":"2012","unstructured":"Gualandi, S., Malucelli, F.: Exact solution of graph coloring problems via constraint programming and column generation. INFORMS Journal on Computing\u00a024(1), 81\u2013100 (2012)","journal-title":"INFORMS Journal on Computing"},{"issue":"2","key":"15_CR11","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/j.dam.2006.07.018","volume":"156","author":"S. Hossain","year":"2008","unstructured":"Hossain, S., Steihaug, T.: Graph coloring in the estimation of sparse derivative matrices: Instances and applications. Discrete Applied Mathematics\u00a0156(2), 280\u2013288 (2008)","journal-title":"Discrete Applied Mathematics"},{"volume-title":"Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop","year":"1996","key":"15_CR12","unstructured":"Johnson, D.J., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11-13, 1993. American Mathematical Society, Boston (1996)"},{"key":"15_CR13","first-page":"85","volume-title":"Complexity of Computer Computations","author":"M. Richard","year":"1972","unstructured":"Richard, M.: Karp. Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum, New York (1972)"},{"key":"15_CR14","unstructured":"Klotz, W.: Graph coloring algorithms. Technical Report Mathematik-Bericht 5, Clausthal University of Technology, Clausthal, Germany (2002)"},{"issue":"1","key":"15_CR15","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1016\/j.cor.2010.04.012","volume":"38","author":"R. Lewis","year":"2011","unstructured":"Lewis, R., Thompson, J.: On the application of graph colouring techniques in round-robin sports scheduling. Computers & Operations Research\u00a038(1), 190\u2013204 (2011)","journal-title":"Computers & Operations Research"},{"issue":"2","key":"15_CR16","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.disopt.2010.07.005","volume":"8","author":"E. Malaguti","year":"2011","unstructured":"Malaguti, E., Monaci, M., Toth, P.: An exact approach for the vertex coloring problem. Discrete Optimization\u00a08(2), 174\u2013190 (2011)","journal-title":"Discrete Optimization"},{"key":"15_CR17","unstructured":"Matula, D.W.: On the complete subgraphs of a random graph. In: Proceedings of the 2nd Chapel Hill Conference on Combinatorial Mathematics and its Applications, Chapel Hill, NC, pp. 356\u2013369 (1970)"},{"issue":"2","key":"15_CR18","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/j.dam.2006.07.010","volume":"156","author":"I. M\u00e9ndez-D\u00edaz","year":"2008","unstructured":"M\u00e9ndez-D\u00edaz, I., Zabala, P.: A cutting plane algorithm for graph coloring. Discrete Applied Mathematics\u00a0156(2), 159\u2013179 (2008)","journal-title":"Discrete Applied Mathematics"},{"key":"15_CR19","first-page":"424","volume":"8","author":"P.R.J. \u00d6sterg\u00e5rd","year":"2001","unstructured":"\u00d6sterg\u00e5rd, P.R.J.: A new algorithm for the maximum-weight clique problem. Nordic Journal of Computing\u00a08, 424\u2013436 (2001)","journal-title":"Nordic Journal of Computing"},{"issue":"7","key":"15_CR20","doi-asserted-by":"publisher","first-page":"1724","DOI":"10.1016\/j.cor.2011.10.008","volume":"39","author":"P.S. Segundo","year":"2012","unstructured":"Segundo, P.S.: A new DSATUR-based algorithm for exact vertex coloring. Computers & Operations Research\u00a039(7), 1724\u20131733 (2012)","journal-title":"Computers & Operations Research"},{"key":"15_CR21","doi-asserted-by":"crossref","unstructured":"Sewell, E.C.: An improved algorithm for exact graph coloring. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 359\u2013373 (1996)","DOI":"10.1090\/dimacs\/026\/17"},{"key":"15_CR22","unstructured":"Trick, M.: Network resources for coloring a graph (1994), \n                    \n                      http:\/\/mat.gsia.cmu.edu\/COLOR\/color.html"},{"key":"15_CR23","unstructured":"Trick, M.: ROIS: Registry for optimization instances and solutions (2009), \n                    \n                      http:\/\/mat.tepper.cmu.edu\/ROIS\/solutions\/coloring\/display_sol.php"}],"container-title":["Lecture Notes in Computer Science","Applied Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-04126-1_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T20:22:20Z","timestamp":1558815740000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-04126-1_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319041254","9783319041261"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-04126-1_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}