{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:23:45Z","timestamp":1725488625473},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540441472"},{"type":"electronic","value":"9783540457268"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45726-7_11","type":"book-chapter","created":{"date-parts":[[2007,8,11]],"date-time":"2007-08-11T09:55:49Z","timestamp":1186826149000},"page":"126-138","source":"Crossref","is-referenced-by-count":0,"title":["Small k-Dominating Sets of Regular Graphs"],"prefix":"10.1007","author":[{"given":"William","family":"Duckworth","sequence":"first","affiliation":[]},{"given":"Bernard","family":"Mans","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,8,23]]},"reference":[{"key":"11_CR1","unstructured":"Chang, G.J. and Nemhauser, G.L.: The k-Domination and k-Stability Problems on Graphs. TR-540, School of Operations Research and Industrial Eng., Cornell University (1982)"},{"key":"11_CR2","volume-title":"PhD thesis","author":"W. Duckworth","year":"2001","unstructured":"Duckworth, W.: Greedy Algorithms and Cubic Graphs. PhD thesis, Department of Mathematics and Statistics, The University of Melbourne, Australia (2001)"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Duckworth, W. and Wormald, N.C.: Minimum Independent Dominating Sets of Random Cubic Graphs. Random Structures and Algorithms. To Appear.","DOI":"10.1002\/rsa.10047"},{"key":"11_CR4","first-page":"225","volume":"33","author":"O. Favaron","year":"2000","unstructured":"Favaron, O., Haynes, T.W. and Slater, P.J.: Distance-k Independent Domination Sequences. Journal of Combinatorial Mathematics and Combinatorial Computing (2000) 33 225\u2013237","journal-title":"Journal of Combinatorial Mathematics and Combinatorial Computing"},{"key":"11_CR5","unstructured":"Haynes, T.W., Hedetniemi, S.T. and Slater, P.J.: Domination in Graphs: Advanced topics. Marcel Dekker Inc. (1998) New York"},{"key":"11_CR6","doi-asserted-by":"crossref","unstructured":"Janson, S., FLuczak, T. and Rucinski, A.: Random Graphs. Wiley-Interscience (2000)","DOI":"10.1002\/9781118032718"},{"key":"11_CR7","first-page":"256","volume":"9","author":"D.S. Johnson","year":"1994","unstructured":"Johnson, D.S.: Approximation Algorithms for Combinatorial problems. In: Proceedings of the 5th Annual ACM STOC, Journal of Computer and System Sciences (1994) 9 256\u2013278","journal-title":"Proceedings of the 5th Annual ACM STOC, Journal of Computer and System Sciences"},{"issue":"1","key":"11_CR8","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1006\/jagm.1998.0929","volume":"28","author":"S. Kutten","year":"1998","unstructured":"Kutten, S. and Peleg, D.: Fast Distributed Construction of Small k-dominating Sets and Applications. Journal of Algorithms (1998) 28(1) 40\u201366","journal-title":"Journal of Algorithms"},{"issue":"3","key":"11_CR9","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/rsa.3240070303","volume":"7","author":"M. Molloy","year":"1995","unstructured":"Molloy, M. and Reed, B.: The Dominating Number of a Random Cubic Graph. Random Structures and Algorithms (1995) 7(3) 209\u2013221","journal-title":"Random Structures and Algorithms"},{"key":"11_CR10","unstructured":"Raz, R. and Safra, S.: A Sub-Constant Error-Probability Low-Degree Test and a Sub-Constant Error-Probability PCP Characterization of NP. In: Proceedings of the 29th Annual ACM STOC (1999) 475\u2013484 (electronic)"},{"issue":"3","key":"11_CR11","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H. and Yannakakis, M.: Optimization, Approximation and Complexity Classes. Journal of Computer and System Sciences (1991) 43(3) 425\u2013440","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1017\/S0963548300002042","volume":"5","author":"B. Reed","year":"1996","unstructured":"Reed, B.: Paths, Stars and the Number Three. Combinatorics, Probability and Computing (1996) 5 277\u2013295","journal-title":"Combinatorics, Probability and Computing"},{"issue":"2","key":"11_CR13","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1002\/rsa.3240050209","volume":"5","author":"R.W. Robinson","year":"1994","unstructured":"Robinson, R.W. and Wormald, N.C.: Almost All Regular Graphs are Hamiltonian. Random Structures and Algorithms (1994) 5(2) 363\u2013374","journal-title":"Random Structures and Algorithms"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"1217","DOI":"10.1214\/aoap\/1177004612","volume":"5","author":"N.C. Wormald","year":"1995","unstructured":"Wormald, N.C.: Differential Equations for Random Processes and Random Graphs. Annals of Applied Probability (1995) 5 1217\u20131235","journal-title":"Annals of Applied Probability"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Wormald, N.C.: Models of Random Regular Graphs. In: Surveys in Combinatorics (1999) 239\u2013298 Cambridge University Press","DOI":"10.1017\/CBO9780511721335.010"},{"key":"11_CR16","first-page":"73","volume-title":"Lectures on Approximation and Randomized Algorithms","author":"N.C. Wormald","year":"1999","unstructured":"Wormald, N.C.: The Differential Equation Method for Random Graph Processes and Greedy Algorithms. In: Lectures on Approximation and Randomized Algorithms (1999) 73\u2013155, PWN, Warsaw"},{"key":"11_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1007\/3-540-44676-1_44","volume-title":"Proceedings of the 19th European Symposium on Algorithms","author":"M. Zito","year":"2001","unstructured":"Zito, M.: Greedy Algorithms for Minimisation Problems in Random Regular Graphs. In: Proceedings of the 19th European Symposium on Algorithms. Lecture Notes in Computer Science (2001) 2161 524\u2013536, Springer-Verlag"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45726-7_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T07:49:08Z","timestamp":1550735348000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45726-7_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540441472","9783540457268"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-45726-7_11","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}