{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T15:27:51Z","timestamp":1725809271849},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319126906"},{"type":"electronic","value":"9783319126913"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-12691-3_26","type":"book-chapter","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T16:11:32Z","timestamp":1415981492000},"page":"343-355","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for Optimization Problems in Random Power-Law Graphs"],"prefix":"10.1007","author":[{"given":"Yilin","family":"Shen","sequence":"first","affiliation":[]},{"given":"Xiang","family":"Li","sequence":"additional","affiliation":[]},{"given":"My T.","family":"Thai","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,13]]},"reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Aiello, W., Chung, F., Lu, L.: A random graph model for massive graphs. In: STOC \u201900, pp. 171\u2013180. ACM, New York (2000)","DOI":"10.1145\/335305.335326"},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1080\/10586458.2001.10504428","volume":"10","author":"W Aiello","year":"2000","unstructured":"Aiello, W., Chung, F., Lu, L.: A random graph model for power law graphs. Exp. Math. 10, 53\u201366 (2000)","journal-title":"Exp. Math."},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1038\/43601","volume":"401","author":"R Albert","year":"1999","unstructured":"Albert, R., Jeong, H., Barabasi, A.L.: The diameter of the world wide web. Nature 401, 130\u2013131 (1999)","journal-title":"Nature"},{"volume-title":"Handbook of Graphs and Networks: From the Genome to the Internet","year":"2003","key":"26_CR4","unstructured":"Bornholdt, S., Schuster, H.G. (eds.): Handbook of Graphs and Networks: From the Genome to the Internet. Wiley, New York (2003)"},{"issue":"2","key":"26_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/PL00012580","volume":"6","author":"F Chung","year":"2002","unstructured":"Chung, F., Lu, L.: Connected components in random graphs with given expected degree sequences. Ann. Comb. 6(2), 125\u2013145 (2002)","journal-title":"Ann. Comb."},{"key":"26_CR6","doi-asserted-by":"publisher","first-page":"439","DOI":"10.4007\/annals.2005.162.439","volume":"162","author":"I Dinur","year":"2005","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439\u2013485 (2005)","journal-title":"Ann. Math."},{"key":"26_CR7","unstructured":"Eubank, S., Kumar, V.S.A., Marathe, M.V., Srinivasan, A., Wang, N.: Structural and algorithmic aspects of massive social networks. In: SODA \u201904, pp. 718\u2013727. Society for Industrial and Applied Mathematics, Philadelphia (2004)"},{"key":"26_CR8","doi-asserted-by":"crossref","unstructured":"Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. In: Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM \u201999, pp. 251\u2013262. ACM, New York (1999)","DOI":"10.1145\/316188.316229"},{"issue":"1\u20133","key":"26_CR9","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.tcs.2007.12.007","volume":"393","author":"A Ferrante","year":"2008","unstructured":"Ferrante, A., Pandurangan, G., Park, K.: On the hardness of optimization in power-law graphs. Theoret. Comput. Sci. 393(1\u20133), 220\u2013230 (2008)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"26_CR10","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1145\/885651.781046","volume":"31","author":"C Gkantsidis","year":"2003","unstructured":"Gkantsidis, C., Mihail, M., Saberi, A.: Conductance and congestion in power law graphs. SIGMETRICS Perform. Eval. Rev. 31(1), 148\u2013159 (2003)","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"26_CR11","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M., Radhakrishnan, J.: Greed is good: approximating independent sets in sparse and bounded-degree graphs. In: Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC \u201994, pp. 439\u2013448. ACM, New York (1994)","DOI":"10.1145\/195058.195221"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Janson, S., Luczak, T., Norros, I.: Large cliques in a power-law random graph(2009)","DOI":"10.1239\/jap\/1294170524"},{"issue":"4","key":"26_CR13","doi-asserted-by":"publisher","first-page":"41:1","DOI":"10.1145\/1597036.1597045","volume":"5","author":"G Karakostas","year":"2009","unstructured":"Karakostas, G.: A better approximation ratio for the vertex cover problem. ACM Trans. Algorithms 5(4), 41:1\u201341:8 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"26_CR14","unstructured":"Pandurangan, G.: (2006). \n                      https:\/\/sites.google.com\/site\/gopalpandurangan\/papers-by-date"},{"issue":"2","key":"26_CR15","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s100510050359","volume":"4","author":"S Redner","year":"1998","unstructured":"Redner, S.: How popular is your paper? an empirical study of the citation distribution. Eur. Phys. J. B - Condens. Matter Complex Syst. 4(2), 131\u2013134 (1998)","journal-title":"Eur. Phys. J. B - Condens. Matter Complex Syst."},{"key":"26_CR16","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/j.tcs.2011.10.023","volume":"447","author":"Y Shen","year":"2012","unstructured":"Shen, Y., Nguyen, D.T., Xuan, Y., Thai, M.T.: New techniques for approximating optimal substructure problems in power-law graphs. Theoret. Comput. Sci. 447, 107\u2013119 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"26_CR17","volume-title":"Approximation Algorithms","author":"VV Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer-Verlag New York Inc., New York (2001)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-12691-3_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T14:54:51Z","timestamp":1559055291000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-12691-3_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319126906","9783319126913"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-12691-3_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}