{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T15:26:06Z","timestamp":1720625166647},"reference-count":27,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2016,7,1]],"date-time":"2016-07-01T00:00:00Z","timestamp":1467331200000},"content-version":"vor","delay-in-days":1461,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Discrete Algorithms"],"published-print":{"date-parts":[[2012,7]]},"DOI":"10.1016\/j.jda.2011.12.008","type":"journal-article","created":{"date-parts":[[2011,12,10]],"date-time":"2011-12-10T14:07:04Z","timestamp":1323526024000},"page":"136-149","source":"Crossref","is-referenced-by-count":8,"special_numbering":"C","title":["The complexity of finding uniform sparsest cuts in various graph classes"],"prefix":"10.1016","volume":"14","author":[{"given":"Paul","family":"Bonsma","sequence":"first","affiliation":[]},{"given":"Hajo","family":"Broersma","sequence":"additional","affiliation":[]},{"given":"Viresh","family":"Patel","sequence":"additional","affiliation":[]},{"given":"Artem","family":"Pyatkin","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.jda.2011.12.008_br0010","author":"Aloise"},{"key":"10.1016\/j.jda.2011.12.008_br0020","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","article-title":"NP-hardness of Euclidean sum-of-squares clustering","volume":"75","author":"Aloise","year":"2009","journal-title":"Mach. Learn."},{"key":"10.1016\/j.jda.2011.12.008_br0030","series-title":"FOCS 2007","first-page":"329","article-title":"Inapproximability results for sparsest cut, optimal linear arrangement, and precedence constrained scheduling","author":"Amb\u00fchl","year":"2007"},{"issue":"2","key":"10.1016\/j.jda.2011.12.008_br0040","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1502793.1502794","article-title":"Expander flows, geometric embeddings and graph partitioning","volume":"56","author":"Arora","year":"2009","journal-title":"J. ACM"},{"issue":"5","key":"10.1016\/j.jda.2011.12.008_br0050","doi-asserted-by":"crossref","first-page":"1748","DOI":"10.1137\/080731049","article-title":"O(logn) approximation to SPARSEST CUT in O\u02dc(n2) time","volume":"39","author":"Arora","year":"2010","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jda.2011.12.008_br0060","doi-asserted-by":"crossref","first-page":"1305","DOI":"10.1137\/S0097539793251219","article-title":"A linear-time algorithm for finding tree-decompositions of small treewidth","volume":"25","author":"Bodlaender","year":"1996","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.jda.2011.12.008_br0070","series-title":"MFCS 1997","first-page":"19","article-title":"Treewidth: algorithmic techniques and results","volume":"vol. 1295","author":"Bodlaender","year":"1997"},{"issue":"2\u20133","key":"10.1016\/j.jda.2011.12.008_br0080","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0166-218X(03)00439-6","article-title":"Sparsest cuts and concurrent flows in product graphs","volume":"136","author":"Bonsma","year":"2004","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.jda.2011.12.008_br0090","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/j.endm.2007.01.039","article-title":"Linear time algorithms for finding sparsest cuts in various graph classes","volume":"28","author":"Bonsma","year":"2007","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"10.1016\/j.jda.2011.12.008_br0100","series-title":"IWOCA 2010","first-page":"125","article-title":"The complexity status of problems related to sparsest cuts","volume":"vol. 6460","author":"Bonsma","year":"2011"},{"key":"10.1016\/j.jda.2011.12.008_br0110","series-title":"APPROX and RANDOM 2010","first-page":"124","article-title":"Approximating sparsest cuts in graphs of bounded treewidth","volume":"vol. 6302","author":"Chlamtac","year":"2010"},{"issue":"3","key":"10.1016\/j.jda.2011.12.008_br0120","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/j.dam.2003.07.001","article-title":"A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs","volume":"138","author":"Corneil","year":"2004","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/j.jda.2011.12.008_br0130","series-title":"LATIN 2000","first-page":"126","article-title":"Polynomial time recognition of clique-width \u2a7d3 graphs (extended abstract)","volume":"vol. 1776","author":"Corneil","year":"2000"},{"key":"10.1016\/j.jda.2011.12.008_br0140","first-page":"193","article-title":"Graph rewriting: An algebraic and logic approach","volume":"vol. B","author":"Courcelle","year":"1990"},{"key":"10.1016\/j.jda.2011.12.008_br0150","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","article-title":"Upper bounds to the clique width of graphs","volume":"101","author":"Courcelle","year":"2000","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"10.1016\/j.jda.2011.12.008_br0160","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1007\/s002249910009","article-title":"Linear time solvable optimization problems on graphs of bounded clique-width","volume":"33","author":"Courcelle","year":"2000","journal-title":"Theory Comput. Syst."},{"issue":"1\u20133","key":"10.1016\/j.jda.2011.12.008_br0170","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1023\/B:MACH.0000033113.59016.96","article-title":"Clustering large graphs via the singular value decomposition","volume":"56","author":"Drineas","year":"2004","journal-title":"Mach. Learn."},{"key":"10.1016\/j.jda.2011.12.008_br0180","series-title":"Parameterized Complexity Theory","author":"Flum","year":"2006"},{"key":"10.1016\/j.jda.2011.12.008_br0190","series-title":"SODA 2010","first-page":"493","article-title":"Algorithmic lower bounds for problems parameterized with clique-width","author":"Fomin","year":"2010"},{"key":"10.1016\/j.jda.2011.12.008_br0200","series-title":"Computers and Intractability, A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"issue":"3","key":"10.1016\/j.jda.2011.12.008_br0210","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1142\/S0129054100000260","article-title":"On the clique-width of some perfect graph classes","volume":"11","author":"Golumbic","year":"2000","journal-title":"Internat. J. Found. Comput. Sci."},{"key":"10.1016\/j.jda.2011.12.008_br0220","series-title":"STACS 2001","first-page":"365","article-title":"Polynomial time approximation schemes for max-bisection in planar and geometric graphs","volume":"vol. 2010","author":"Jansen","year":"2001"},{"issue":"6","key":"10.1016\/j.jda.2011.12.008_br0230","doi-asserted-by":"crossref","first-page":"787","DOI":"10.1145\/331524.331526","article-title":"Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms","volume":"46","author":"Leighton","year":"1999","journal-title":"J. ACM"},{"key":"10.1016\/j.jda.2011.12.008_br0240","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0166-218X(90)90133-W","article-title":"Sparsest cuts and bottlenecks in graphs","volume":"27","author":"Matula","year":"1990","journal-title":"Discrete Appl. Math."},{"issue":"4","key":"10.1016\/j.jda.2011.12.008_br0250","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1016\/j.jctb.2005.10.006","article-title":"Approximating clique-width and branch-width","volume":"96","author":"Oum","year":"2006","journal-title":"J. Combin. Theory Ser. B"},{"key":"10.1016\/j.jda.2011.12.008_br0260","series-title":"Algorithms \u2013 ESA 2010","first-page":"561","article-title":"Determining edge expansion and other connectivity measures of graphs of bounded genus","volume":"vol. 6346","author":"Patel","year":"2010"},{"issue":"2","key":"10.1016\/j.jda.2011.12.008_br0270","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM J. Comput."}],"container-title":["Journal of Discrete Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1570866711001110?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1570866711001110?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2018,11,27]],"date-time":"2018-11-27T19:52:19Z","timestamp":1543348339000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1570866711001110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":27,"alternative-id":["S1570866711001110"],"URL":"https:\/\/doi.org\/10.1016\/j.jda.2011.12.008","relation":{},"ISSN":["1570-8667"],"issn-type":[{"value":"1570-8667","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}
