{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:19:07Z","timestamp":1742617147464,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540578994"},{"type":"electronic","value":"9783540483854"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57899-4_36","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:39:47Z","timestamp":1330263587000},"page":"1-10","source":"Crossref","is-referenced-by-count":3,"title":["Near-optimal dominating sets in dense random graphs in polynomial expected time"],"prefix":"10.1007","author":[{"given":"Sotiris E.","family":"Nikoletseas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul G.","family":"Spirakis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,26]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"\u201cFast Probabilistic Algorithms for Hamiltonian Circuits and Matchings\u201d, by D.Angluin and L.Valiant, Journal of Computer and System Sciences, vol.18, p.155\u2013193 (1979)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR2","unstructured":"\u201cRandom Graphs\u201d, by B. Bollob\u00e1s, Academic Press (1985)"},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1016\/0196-6774(89)90001-1","volume":"10","author":"M. Dyer","year":"1989","unstructured":"\u201cThe Solution of Some Random NP-hard Problems in Polynomial Expected Time\u201d, by M.Dyer and A.Frieze, Journal of Algorithms, vol.10, p.451\u2013489 (1989)","journal-title":"Journal of Algorithms"},{"key":"1_CR4","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"\u201cComputers and Intractability: A Guide to the Theory of NP-Completeness\u201d, by M.Garey and D.Johnson, W.H.Freeman and Co., NY (1979)"},{"key":"1_CR5","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1017\/S0305004100051124","volume":"77","author":"G. Grimmett","year":"1975","unstructured":"\u201cOn colouring random graphs\u201d, by G. Grimmett and C. McDiarmid, Math. Proc. Cambridge Phil. Soc. 77, p.313\u2013324 (1975)","journal-title":"Math. Proc. Cambridge Phil. Soc."},{"key":"1_CR6","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1016\/0022-0000(91)90007-R","volume":"42","author":"Y. Gurevitch","year":"1991","unstructured":"\u201cAverage Case Completeness\u201d, by Y.Gurevitch, Journal of Computer and System Sciences, vol.42, p.346\u2013348 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"1_CR7","unstructured":"\u201cProbabilistic Analysis\u201d, by R.Karp, Lecture Notes CS 292F, U.C.Berkeley (1989)"},{"key":"1_CR8","volume-title":"Technical Report","author":"L. Ku\u010dera","year":"1991","unstructured":"\u201cParallel coloring of graphs with small chromatic numbers\u201d, by L. Ku\u010dera, Technical Report, Charles Univ. Prague (1991)"},{"key":"1_CR9","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"L. Levin","year":"1986","unstructured":"\u201cAverage Case Complete Problems\u201d, by L.Levin, vol.15, SIAM J. Comp., p.285\u2013286 (1986)","journal-title":"SIAM J. Comp."},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"\u201cColouring random graphs\u201d, by C. McDiarmid, Ann. Oper. Res. 1 (1984)","DOI":"10.1007\/BF01874388"},{"key":"1_CR11","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0012-365X(76)90068-6","volume":"14","author":"L. Posa","year":"1976","unstructured":"\u201cHamiltonian Circuits in Random Graphs\u201d, by L.Posa, Discrete Mathematics, vol.14, p.359\u2013364 (1976)","journal-title":"Discrete Mathematics"},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"\u201cRandom Matroids\u201d, by J.Reif and P.Spirakis, Proc. 12th Annual ACM Symp. Theory of Computing, p.385\u2013397 (1980)","DOI":"10.1145\/800141.804688"},{"key":"1_CR13","unstructured":"\u201cTen Lectures On The Probabilistic Method\u201d, by J.Spencer, SIAM CBMS-NSF Regional Conference Series (1987)"}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57899-4_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:16:25Z","timestamp":1742595385000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57899-4_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578994","9783540483854"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-57899-4_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}