{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T21:27:13Z","timestamp":1725571633345},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642174575"},{"type":"electronic","value":"9783642174582"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17458-2_17","type":"book-chapter","created":{"date-parts":[[2010,12,15]],"date-time":"2010-12-15T06:12:57Z","timestamp":1292393577000},"page":"197-211","source":"Crossref","is-referenced-by-count":1,"title":["On the Hardness and Inapproximability of Optimization Problems on Power Law Graphs"],"prefix":"10.1007","author":[{"given":"Yilin","family":"Shen","sequence":"first","affiliation":[]},{"given":"Dung T.","family":"Nguyen","sequence":"additional","affiliation":[]},{"given":"My T.","family":"Thai","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"17_CR1","first-page":"171","volume-title":"STOC 2000","author":"W. Aiello","year":"2000","unstructured":"Aiello, W., Chung, F., Lu, L.: A random graph model for massive graphs. In: STOC 2000, pp. 171\u2013180. ACM, New York (2000)"},{"key":"17_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. Experimental Math.\u00a010, 53\u201366 (2000)","journal-title":"Experimental Math."},{"key":"17_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-62592-5_80","volume-title":"Algorithms and Complexity","author":"P. Alimonti","year":"1997","unstructured":"Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds.) CIAC 1997. LNCS, vol.\u00a01203, pp. 288\u2013298. Springer, Heidelberg (1997)"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Austrin, P., Khot, S., Safra, M.: Inapproximability of vertex cover and independent set in bounded degree graphs. In: CCC 2009, pp. 74\u201380 (2009)","DOI":"10.1109\/CCC.2009.38"},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A.-L. Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si, A.-L., Albert, R.: Emergence of scaling in random networks. Science\u00a0286, 509\u2013512 (1999)","journal-title":"Science"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Bianconi, G., Barab\u00e1si, A.L.: Bose-einstein condensation in complex networks (2000)","DOI":"10.1103\/PhysRevLett.86.5632"},{"key":"17_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-349-03521-2","volume-title":"Graph theory with applications","author":"J. Bondy","year":"1976","unstructured":"Bondy, J., Murty, U.: Graph theory with applications. MacMillan, London (1976)"},{"volume-title":"Handbook of Graphs and Networks: From the Genome to the Internet","year":"2003","key":"17_CR8","unstructured":"Bornholdt, S., Schuster, H.G. (eds.): Handbook of Graphs and Networks: From the Genome to the Internet. John Wiley & Sons, Inc., New York (2003)"},{"issue":"11","key":"17_CR9","doi-asserted-by":"publisher","first-page":"1264","DOI":"10.1016\/j.ic.2008.07.003","volume":"206","author":"M. Chleb\u00edk","year":"2008","unstructured":"Chleb\u00edk, M., Chleb\u00edkov\u00e1, J.: Approximation hardness of dominating set problems in bounded degree graphs. Inf. Comput.\u00a0206(11), 1264\u20131275 (2008)","journal-title":"Inf. Comput."},{"key":"17_CR10","first-page":"2005","volume":"162","author":"I. Dinur","year":"2004","unstructured":"Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Annals of Mathematics\u00a0162, 2005 (2004)","journal-title":"Annals of Mathematics"},{"key":"17_CR11","first-page":"264","volume":"11","author":"P. Erdos","year":"1960","unstructured":"Erdos, P., Gallai, T.: Graphs with prescribed degrees of vertices. Mat. Lapok\u00a011, 264\u2013274 (1960)","journal-title":"Mat. Lapok"},{"key":"17_CR12","first-page":"718","volume-title":"SODA 2004","author":"S. Eubank","year":"2004","unstructured":"Eubank, S., Kumar, V.S.A., Marathe, M.V., Srinivasan, A., Wang, N.: Structural and algorithmic aspects of massive social networks. In: SODA 2004, pp. 718\u2013727. Society for Industrial and Applied Mathematics, Philadelphia (2004)"},{"issue":"1-3","key":"17_CR13","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. Theoretical Computer Science\u00a0393(1-3), 220\u2013230 (2008)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"17_CR14","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.\u00a031(1), 148\u2013159 (2003)","journal-title":"SIGMETRICS Perform. Eval. Rev."},{"key":"17_CR15","first-page":"627","volume-title":"FOCS 1996","author":"J. Hastad","year":"1996","unstructured":"Hastad, J.: Clique is hard to approximate within n 1\u2009\u2212\u2009\u03b5 . In: FOCS 1996, Washington, DC, USA, p. 627. IEEE Computer Society, Los Alamitos (1996)"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Janson, S., Luczak, T., Norros, I.: Large cliques in a power-law random graph (2009)","DOI":"10.1017\/S0021900200007415"},{"key":"17_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1127","DOI":"10.1007\/11523468_91","volume-title":"Automata, Languages and Programming","author":"D. Kempe","year":"2005","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Influential nodes in a diffusion model for social networks. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 1127\u20131138. Springer, Heidelberg (2005)"},{"key":"17_CR18","first-page":"137","volume-title":"KDD","author":"D. Kempe","year":"2003","unstructured":"Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: KDD, pp. 137\u2013146. ACM Press, New York (2003)"},{"key":"17_CR19","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: 32nd STOC, pp. 163\u2013170 (2000)","DOI":"10.1145\/335305.335325"},{"key":"17_CR20","doi-asserted-by":"crossref","unstructured":"Kumar, R., Raghavan, P., Rajagopalan, S., Sivakumar, D., Tomkins, A., Upfal, E.: Stochastic models for the web graph. In: FOCS 2000, p. 57 (2000)","DOI":"10.1109\/SFCS.2000.892065"},{"key":"17_CR21","doi-asserted-by":"crossref","unstructured":"Norros, I., Reittu, H.: On a conditionally poissonian graph process. In: Advances in Applied Probability, pp. 38\u201359 (2006)","DOI":"10.1017\/S000186780000080X"},{"key":"17_CR22","unstructured":"Pandurangan, G., http:\/\/www.cs.purdue.edu\/homes\/gopal\/powerlawtalk.pdf"}],"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-642-17458-2_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T22:57:25Z","timestamp":1559861845000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17458-2_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642174575","9783642174582"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17458-2_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}