{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T11:08:49Z","timestamp":1648897729646},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2007,12,5]],"date-time":"2007-12-05T00:00:00Z","timestamp":1196812800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2009,4]]},"DOI":"10.1007\/s10878-007-9112-2","type":"journal-article","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T11:11:19Z","timestamp":1196939479000},"page":"274-311","source":"Crossref","is-referenced-by-count":6,"title":["Probabilistic graph-coloring in bipartite and split graphs"],"prefix":"10.1007","volume":"17","author":[{"given":"N.","family":"Bourgeois","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"F.","family":"Della Croce","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B.","family":"Escoffier","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Murat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"V. Th.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,12,5]]},"reference":[{"key":"9112_CR1","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1002\/1520-6750(199412)41:7<973::AID-NAV3220410709>3.0.CO;2-H","volume":"41","author":"I Averbakh","year":"1994","unstructured":"Averbakh I, Berman O, Simchi-Levi D (1994) Probabilistic a priori routing-location problems. Nav Res Logist 41:973\u2013989","journal-title":"Nav Res Logist"},{"issue":"3","key":"9112_CR2","doi-asserted-by":"crossref","first-page":"693","DOI":"10.1016\/0377-2217(95)00240-5","volume":"87","author":"M Bellalouna","year":"1995","unstructured":"Bellalouna M, Murat C, Paschos VTh (1995) Probabilistic combinatorial optimization problems: a new domain in operational research. Eur J Oper Res 87(3):693\u2013706","journal-title":"Eur J Oper Res"},{"key":"9112_CR3","volume-title":"Graphs and hypergraphs","author":"C Berge","year":"1973","unstructured":"Berge C (1973) Graphs and hypergraphs. North-Holland, Amsterdam"},{"key":"9112_CR4","unstructured":"Bertsimas DJ (1988) Probabilistic combinatorial optimization problems. PhD thesis, Operations Research Center, MIT, Cambridge, MA, USA"},{"key":"9112_CR5","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1287\/trsc.23.3.184","volume":"3","author":"DJ Bertsimas","year":"1989","unstructured":"Bertsimas DJ (1989) On probabilistic traveling salesman facility location problems. Transp Sci 3:184\u2013191","journal-title":"Transp Sci"},{"key":"9112_CR6","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1002\/net.3230200302","volume":"20","author":"DJ Bertsimas","year":"1990","unstructured":"Bertsimas DJ (1990) The probabilistic minimum spanning tree problem. Networks 20:245\u2013275","journal-title":"Networks"},{"issue":"6","key":"9112_CR7","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1287\/opre.38.6.1019","volume":"38","author":"DJ Bertsimas","year":"1990","unstructured":"Bertsimas DJ, Jaillet P, Odoni A (1990) A priori optimization. Oper Res 38(6):1019\u20131033","journal-title":"Oper Res"},{"issue":"1","key":"9112_CR8","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1016\/j.ejor.2003.10.016","volume":"161","author":"L Bianchi","year":"2005","unstructured":"Bianchi L, Knowles J, Bowler N (2005) Local search for the probabilistic traveling salesman problem: correction to the 2-p-opt and 1-shift algorithms. Eur J Oper Res 161(1):206\u2013219","journal-title":"Eur J Oper Res"},{"key":"9112_CR9","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0166-218X(94)90009-4","volume":"55","author":"HL Bodlaender","year":"1994","unstructured":"Bodlaender HL, Jansen K, Woeginger GJ (1994) Scheduling with incompatible jobs. Discrete Appl Math 55:219\u2013232","journal-title":"Discrete Appl Math"},{"key":"9112_CR10","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1007\/BFb0121007","volume":"22","author":"J-M Bourjolly","year":"1984","unstructured":"Bourjolly J-M, Hammer PL, Simeone B (1984) Node-weighted graphs having the K\u00f6nig\u2013Egervary property. Math Program Stud 22:44\u201363","journal-title":"Math Program Stud"},{"key":"9112_CR11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/0020-0190(94)90039-6","volume":"50","author":"M Demange","year":"1994","unstructured":"Demange M, Grisoni P, Paschos VTh (1994) Approximation results for the minimum graph coloring problem. Inform Process Lett 50:19\u201323","journal-title":"Inform Process Lett"},{"key":"9112_CR12","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/S0304-3975(97)00099-6","volume":"209","author":"M Demange","year":"1998","unstructured":"Demange M, Grisoni P, Paschos VTh (1998) Differential approximation algorithms for some combinatorial optimization problems. Theor Comput Sci 209:107\u2013122","journal-title":"Theor Comput Sci"},{"key":"9112_CR13","volume-title":"Computers and intractability. A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability. A guide to the theory of NP-completeness. Freeman, San Francisco"},{"key":"9112_CR14","unstructured":"Halld\u00f3rsson MM (1995) Approximating discrete collections via local improvements. In Proceedings of the symposium on discrete algorithms, SODA\u201995, pp 160\u2013169"},{"key":"9112_CR15","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1006\/jagm.2001.1187","volume":"41","author":"R Hassin","year":"2001","unstructured":"Hassin R, Khuller S (2001) z-approximations. J Algorithms 41:429\u2013442","journal-title":"J Algorithms"},{"key":"9112_CR16","unstructured":"Jaillet P (1985) Probabilistic traveling salesman problem. Technical Report 185, Operations Research Center, MIT, Cambridge, MA, USA"},{"issue":"6","key":"9112_CR17","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1287\/opre.36.6.929","volume":"36","author":"P Jaillet","year":"1988","unstructured":"Jaillet P (1988) A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Oper Res 36(6):929\u2013936","journal-title":"Oper Res"},{"key":"9112_CR18","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1002\/net.3230220607","volume":"22","author":"P Jaillet","year":"1992","unstructured":"Jaillet P (1992) Shortest path problems with node failures. Networks 22:589\u2013605","journal-title":"Networks"},{"key":"9112_CR19","volume-title":"Vehicle routing: methods and studies","author":"P Jaillet","year":"1988","unstructured":"Jaillet P, Odoni A (1988) The probabilistic vehicle routing problem. In: Golden BL, Assad AA (eds) Vehicle routing: methods and studies. North-Holland, Amsterdam"},{"key":"9112_CR20","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1016\/S0022-0000(74)80044-9","volume":"9","author":"DS Johnson","year":"1974","unstructured":"Johnson DS (1974) Approximation algorithms for combinatorial problems. J Comput Syst Sci 9:256\u2013278","journal-title":"J Comput Syst Sci"},{"key":"9112_CR21","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW (eds) Complexity of computer computations. Plenum, New York, pp 85\u2013103"},{"key":"9112_CR22","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1002\/(SICI)1097-0037(199905)33:3<207::AID-NET7>3.0.CO;2-7","volume":"33","author":"C Murat","year":"1999","unstructured":"Murat C, Paschos VTh (1999) The probabilistic longest path problem. Networks 33:207\u2013219","journal-title":"Networks"},{"key":"9112_CR23","doi-asserted-by":"crossref","first-page":"561","DOI":"10.1016\/S0304-3975(01)00005-6","volume":"270","author":"C Murat","year":"2002","unstructured":"Murat C, Paschos VTh (2002a) A priori optimization for the probabilistic maximum independent set problem. Theor Comput Sci 270:561\u2013590. Preliminary version available at http:\/\/www.lamsade.dauphine.fr\/~paschos\/documents\/c166.pdf","journal-title":"Theor Comput Sci"},{"issue":"1","key":"9112_CR24","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1111\/1475-3995.00338","volume":"9","author":"C Murat","year":"2002","unstructured":"Murat C, Paschos VTh (2002b) The probabilistic minimum vertex-covering problem. Int Trans Oper Res 9(1):19\u201332. Preliminary version available at http:\/\/www.lamsade.dauphine.fr\/~paschos\/documents\/c170.pdf","journal-title":"Int Trans Oper Res"},{"key":"9112_CR25","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1016\/j.dam.2005.06.007","volume":"154","author":"C Murat","year":"2006","unstructured":"Murat C, Paschos VTh (2006) On the probabilistic minimum coloring and minimum k-coloring. Discrete Appl Math 154:564\u2013586","journal-title":"Discrete Appl Math"},{"issue":"2","key":"9112_CR26","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1137\/0403025","volume":"3","author":"HU Simon","year":"1990","unstructured":"Simon HU (1990) On approximate solutions for combinatorial optimization problems. SIAM J Discrete Math 3(2):294\u2013310","journal-title":"SIAM J Discrete Math"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9112-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-007-9112-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-007-9112-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T00:18:12Z","timestamp":1559261892000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-007-9112-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,5]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["9112"],"URL":"https:\/\/doi.org\/10.1007\/s10878-007-9112-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,5]]}}}