{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,11]],"date-time":"2024-07-11T11:20:02Z","timestamp":1720696802172},"reference-count":15,"publisher":"Elsevier BV","issue":"1-3","license":[{"start":{"date-parts":[[2007,5,1]],"date-time":"2007-05-01T00:00:00Z","timestamp":1177977600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":2269,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2007,5]]},"DOI":"10.1016\/j.tcs.2007.02.013","type":"journal-article","created":{"date-parts":[[2007,2,12]],"date-time":"2007-02-12T11:57:48Z","timestamp":1171281468000},"page":"271-276","source":"Crossref","is-referenced-by-count":23,"title":["MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs"],"prefix":"10.1016","volume":"377","author":[{"given":"Josep","family":"D\u00edaz","sequence":"first","affiliation":[]},{"given":"Marcin","family":"Kami\u0144ski","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2007.02.013_b1","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/S1389-1286(01)00302-4","article-title":"Wireless sensor networks: A survey","volume":"38","author":"Akyildiz","year":"2002","journal-title":"Computer Networks"},{"key":"10.1016\/j.tcs.2007.02.013_b2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","article-title":"Unit disk recognition is NP-hard","volume":"9","author":"Breu","year":"1998","journal-title":"Computational Geometry"},{"issue":"1","key":"10.1016\/j.tcs.2007.02.013_b3","first-page":"14","article-title":"On the complexity of the maximum cut problem","volume":"7","author":"Bodlaender","year":"2000","journal-title":"Nordic Journal of Computing"},{"key":"10.1016\/j.tcs.2007.02.013_b4","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","article-title":"Unit disk graphs","volume":"86","author":"Clark","year":"1990","journal-title":"Discrete Mathematics"},{"key":"10.1016\/j.tcs.2007.02.013_b5","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1006\/jagm.2000.1149","article-title":"Approximating layout problems on random geometric graphs","volume":"39","author":"D\u00edaz","year":"2001","journal-title":"Journal of Algorithms"},{"key":"10.1016\/j.tcs.2007.02.013_b6","series-title":"Computers and Intractability","author":"Garey","year":"1979"},{"key":"10.1016\/j.tcs.2007.02.013_b7","series-title":"Algorithmic Graph Theory and Perfect Graphs","author":"Golumbic","year":"1980"},{"issue":"3","key":"10.1016\/j.tcs.2007.02.013_b8","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1137\/0204019","article-title":"Finding a maximum cut of a planar graph in polynomial time","volume":"4","author":"Hadlock","year":"1975","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/j.tcs.2007.02.013_b9","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1006\/jagm.1997.0903","article-title":"NC-approximation schemes for NP- and PSPACE-Hard problems for geometric graphs","volume":"26","author":"Hunt","year":"1998","journal-title":"Journal of Algorithms"},{"issue":"1","key":"10.1016\/j.tcs.2007.02.013_b10","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1137\/S009753970139567X","article-title":"Polynomial-time approximation schemes for Max-bisection on planar and geometric graphs","volume":"35","author":"Jansen","year":"2005","journal-title":"SIAM Journal on Computing"},{"key":"10.1016\/j.tcs.2007.02.013_b11","series-title":"Complexity of Computer Computations","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1016\/j.tcs.2007.02.013_b12","unstructured":"E.J. van Leeuwen, J. van Leeuwen, On the representation of disk graphs Technical Report UU-CS-2006-037, Utrecht University, 2006"},{"key":"10.1016\/j.tcs.2007.02.013_b13","first-page":"502","article-title":"Finding the maximal cut in a graph","volume":"10","author":"Orlova","year":"1972","journal-title":"Engineering Cybernetics"},{"key":"10.1016\/j.tcs.2007.02.013_b14","series-title":"Efficient Graphs Representations","volume":"vol. 19","author":"Spinrad","year":"2003"},{"key":"10.1016\/j.tcs.2007.02.013_b15","doi-asserted-by":"crossref","unstructured":"M. Yannakakis, Node- and edge-deletion NP-complete problems, in: IEEE Symposium on Theory of Computing, STOC, 1978, pp. 253\u2013264","DOI":"10.1145\/800133.804355"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397507000801?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397507000801?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,24]],"date-time":"2019-04-24T15:20:44Z","timestamp":1556119244000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397507000801"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5]]},"references-count":15,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2007,5]]}},"alternative-id":["S0304397507000801"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2007.02.013","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2007,5]]}}}