{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:22:24Z","timestamp":1725488544678},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540401766"},{"type":"electronic","value":"9783540448495"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-44849-7_25","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T06:26:17Z","timestamp":1186727177000},"page":"201-212","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Detecting Fixed-Density Clusters"],"prefix":"10.1007","author":[{"given":"Klaus","family":"Holzapfel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sven","family":"Kosub","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moritz G.","family":"Maa\u00df","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanjo","family":"T\u00e4ubig","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,5,13]]},"reference":[{"issue":"1\u20133","key":"25_CR1","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0166-218X(01)00243-8","volume":"121","author":"Y. Asahiro","year":"2002","unstructured":"Y. Asahiro, R. Hassin, and K. Iwama. Complexity of finding dense subgraphs. Discrete Applied Mathematics, 121(1\u20133): 15\u201326, 2002.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"25_CR2","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1006\/jagm.1999.1062","volume":"34","author":"Y. Asahiro","year":"2000","unstructured":"Y. Asahiro, K. Iwama, H. Tamaki, and T. Tokuyama. Greedily finding a dense subgraph. Journal of Algorithms, 34(2): 203\u2013221, 2000.","journal-title":"Journal of Algorithms"},{"issue":"1\u20132","key":"25_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0167-9260(95)00008-4","volume":"19","author":"C. J. Alpert","year":"1995","unstructured":"C. J. Alpert and A. B. Kahng. Recent developments in netlist partitioning: A survey. Integration: The VLSI Journal, 19(1\u20132): 1\u201381, 1995.","journal-title":"Integration: The VLSI Journal"},{"issue":"1","key":"25_CR4","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1006\/jcss.1998.1605","volume":"58","author":"S. Arora","year":"1999","unstructured":"S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. Journal of Computer and System Sciences, 58(1): 193\u2013210, 1999.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"25_CR5","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R. B. Boppana","year":"1992","unstructured":"R. B. Boppana and M. M. Halld\u00f3rsson. Approximating maximum independent sets by excluding subgraphs. BIT, 32(2):180\u2013196, 1992.","journal-title":"BIT"},{"key":"25_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/3-540-44436-X_10","volume-title":"Proceedings 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization","author":"M. S. Charikar","year":"2000","unstructured":"M. S. Charikar. Greedy approximation algorithms for finding dense components in a graph. In Proceedings 3rd International Workshop on Approximation Algorithms for Combinatorial Optimization, volume 1913 of Lecture Notes in Computer Science, pages 84\u201395. Springer-Verlag, Berlin, 2000."},{"key":"25_CR7","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1145\/157485.165119","volume-title":"Proceedings 30th ACM\/IEEE Design Automation Conference","author":"J. Cong","year":"1993","unstructured":"J. Cong and M. Smith. A parallel bottom-up clustering algorithm with applications to circuit partitioning in VLSI design. In Proceedings 30th ACM\/IEEE Design Automation Conference, pages 755\u2013760. ACM Press, New York, 1993."},{"issue":"5","key":"25_CR8","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0167-6377(00)00058-4","volume":"27","author":"A. Czygrinow","year":"2000","unstructured":"A. Czygrinow. Maximum dispersion problem in dense graphs. Operations Research Letters, 27(5): 223\u2013227, 2000.","journal-title":"Operations Research Letters"},{"issue":"4","key":"25_CR9","doi-asserted-by":"publisher","first-page":"1268","DOI":"10.1287\/opre.42.4.688","volume":"42","author":"U. Faigle","year":"1994","unstructured":"U. Faigle and W. Kern. Computational complexity of some maximum average weight problems with precedence constraints. Operations Research, 42(4):1268\u20131272, 1994.","journal-title":"Operations Research"},{"issue":"3","key":"25_CR10","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/s004530010050","volume":"29","author":"U. Feige","year":"2001","unstructured":"U. Feige, G. Kortsarz, and D. Peleg. The dense k-subgraph problem. Algorithmica, 29(3): 410\u2013421, 2001.","journal-title":"Algorithmica"},{"key":"25_CR11","series-title":"Technical Report","volume-title":"On the densest k-subgraph problem","author":"U. Feige","year":"1997","unstructured":"U. Feige and M. Seltser. On the densest k-subgraph problem. Technical Report CS97-16, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel, 1997."},{"issue":"1","key":"25_CR12","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1137\/0218003","volume":"18","author":"G. Gallo","year":"1989","unstructured":"G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A fast parametric maximum flow algorithm and applications. SIAM Journal on Computing, 18(1):30\u201355, 1989.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"25_CR13","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1002\/1520-6750(199410)41:6<833::AID-NAV3220410611>3.0.CO;2-Q","volume":"41","author":"O. Goldschmidt","year":"1994","unstructured":"O. Goldschmidt, D. Nehme, and G. Yu. On the set union knapsack problem. Naval Research Logistics, 41(6):833\u2013842, 1994.","journal-title":"Naval Research Logistics"},{"issue":"1","key":"25_CR14","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5astad","year":"1999","unstructured":"J. H\u00e5astad. Clique is hard to approximate within n 1\u2212\u03b5 . Acta Mathematica, 182(1):105\u2013142, 1999.","journal-title":"Acta Mathematica"},{"key":"25_CR15","doi-asserted-by":"crossref","unstructured":"K. Holzapfel, S. Kosub, M. G. Maa\u00df, and H. T\u00e4ubig. The complexity of detecting fixed-density clusters. Technical Report TUM-I0212, Fakult\u00e4t f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen, 2002.","DOI":"10.1007\/3-540-44849-7_25"},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"D. J.-H. Huang and A. B. Kahng. When cluster meet partitions: New density-based methods for circuit decomposition. In Proceedings European Design and Test Conference, pages 60\u201364. IEEE Computer Society Press, Los Alamitos, 1995.","DOI":"10.1109\/EDTC.1995.470419"},{"key":"25_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-48686-0_1","volume-title":"Proceedings 5th International Conference on Computing and Combinatorics","author":"J. M. Kleinberg","year":"1999","unstructured":"J. M. Kleinberg, S. R. Kumar, P. Raghavan, S. Rajagopalan, and A. S. Tomkins. The Web as a graph: measurements, models, and methods. In Proceedings 5th International Conference on Computing and Combinatorics, volume 1627 of Lecture Notes in Computer Science, pages 1\u201317. Springer-Verlag, Berlin, 1999."},{"issue":"3","key":"25_CR18","doi-asserted-by":"publisher","first-page":"1481","DOI":"10.1016\/S1389-1286(99)00040-7","volume":"31","author":"S. R. Kumar","year":"1999","unstructured":"S. R. Kumar, P. Raghavan, S. Rajagopalan, and A. S. Tomkins. Trawling the Web for emerging cyber-communities. Computer Networks, 31(3):1481\u20131493, 1999.","journal-title":"Computer Networks"},{"key":"25_CR19","series-title":"Lecture Notes in Artificial Intelligence","first-page":"65","volume-title":"Proceedings 3th International Conference on Discovery Science","author":"T. Murata","year":"2000","unstructured":"T. Murata. Discovery of Web communities based on the co-occurrence of references. In Proceedings 3th International Conference on Discovery Science, volume 1967 of Lecture Notes in Artificial Intelligence, pages 65\u201375. Springer-Verlag, Berlin, 2000."},{"issue":"1","key":"25_CR20","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/S0166-218X(96)00015-7","volume":"74","author":"D. Nehme","year":"1997","unstructured":"D. Nehme and G. Yu. The cardinality and precedence constrained maximum value sub-hypergraph problem and its applications. Discrete Applied Mathematics, 74(1):57\u201368, 1997.","journal-title":"Discrete Applied Mathematics"},{"key":"25_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/BFb0053974","volume-title":"Proceedings International Workshop on Approximation Algorithms for Combinatorial Optimization","author":"A. Srivastav","year":"1998","unstructured":"A. Srivastav and K. Wolf. Finding dense subgraphs with semidefinite programming. In Proceedings International Workshop on Approximation Algorithms for Combinatorial Optimization, volume 1444 of Lecture Notes in Computer Science, pages 181\u2013191. Springer-Verlag, Berlin, 1998."},{"key":"25_CR22","first-page":"436","volume":"48","author":"P. Tur\u00e1n","year":"1941","unstructured":"P. Tur\u00e1n. On an extremal problem in graph theory. Matematikai \u00e9s Fizikai Lapok, 48: 436\u2013452, 1941. In Hungarian.","journal-title":"Matematikai \u00e9s Fizikai Lapok"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44849-7_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T18:12:25Z","timestamp":1556734345000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44849-7_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540401766","9783540448495"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-44849-7_25","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}