{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T09:33:53Z","timestamp":1725788033634},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2005,5,22]]},"DOI":"10.1145\/1060590.1060674","type":"proceedings-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:31:47Z","timestamp":1123057907000},"page":"563-572","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":55,"title":["Improved approximation algorithms for minimum-weight vertex separators"],"prefix":"10.1145","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[{"name":"Microsoft Research and The Weizmann Institute"}]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}]},{"given":"James R.","family":"Lee","sequence":"additional","affiliation":[{"name":"U.C. Berkeley"}]}],"member":"320","published-online":{"date-parts":[[2005,5,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-1990-1065053-0"},{"key":"e_1_3_2_1_2_1","first-page":"7","volume-title":"Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence","author":"Amir E.","year":"2001","unstructured":"E. Amir , Efficient approximation for triangulation of minimum treewidth , in Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence , Morgan Kaufmann , 2001 , pp. 7 -- 15 . Journal version titled \"Approximation Algorithms for Treewidth\" is available at the author's homepage. E. Amir, Efficient approximation for triangulation of minimum treewidth, in Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, 2001, pp. 7--15. Journal version titled \"Approximation Algorithms for Treewidth\" is available at the author's homepage."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780557"},{"volume-title":"Manuscript","year":"2004","author":"Arora S.","key":"e_1_3_2_1_4_1","unstructured":"S. Arora , J. R. Lee , and A. Naor , Euclidean distortion and the Sparsest Cut . Manuscript , 2004 . S. Arora, J. R. Lee, and A. Naor, Euclidean distortion and the Sparsest Cut. Manuscript, 2004."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007355"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794285983"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(84)90071-0"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00228-4"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0653(05)80091-5"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359683"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90140-Q"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005","year":"2005","author":"Chawla S.","key":"e_1_3_2_1_14_1","unstructured":"S. Chawla , A. Gupta , and H. Raecke , Embeddings of negative-type metrics and improved approximations to sparsest cut , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005 ), Vancouver, Canada , January 2005 . S. Chawla, A. Gupta, and H. Raecke, Embeddings of negative-type metrics and improved approximations to sparsest cut, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, Canada, January 2005."},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005","year":"2005","author":"Demaine E. D.","key":"e_1_3_2_1_15_1","unstructured":"E. D. Demaine and M. Hajiaghayi , Bidimensionality: New connections between FPT algorithms and PTASs , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005 ), Vancouver, Canada , January 2005 . E. D. Demaine and M. Hajiaghayi, Bidimensionality: New connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, Canada, January 2005."},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005","year":"2005","author":"Demaine E. D.","key":"e_1_3_2_1_16_1","unstructured":"E. D. Demaine and M. Hajiaghayi , Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005 ), Vancouver, Canada , January 2005 . -------------, Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, Canada, January 2005."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.12.001"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/347476.347478"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"volume-title":"Technical report MCS04-04, Department of Computer Science and Applied Math.","year":"2004","author":"Feige U.","key":"e_1_3_2_1_21_1","unstructured":"U. Feige and S. Kogan , Hardness of approximation of the balanced complete bipartite subgraph problem , Technical report MCS04-04, Department of Computer Science and Applied Math. , The Weizmann Institute of Science , ( 2004 ). U. Feige and S. Kogan, Hardness of approximation of the balanced complete bipartite subgraph problem, Technical report MCS04-04, Department of Computer Science and Applied Math., The Weizmann Institute of Science, (2004)."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10036"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90019-1"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-003-0037-9"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80059-5"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007357"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.59"},{"volume-title":"Manuscript","year":"2004","author":"Khot S.","key":"e_1_3_2_1_28_1","unstructured":"S. Khot and N. Vishnoi , On embeddability of negative type metrics into l1 . Manuscript , 2004 . S. Khot and N. Vishnoi, On embeddability of negative type metrics into l1. Manuscript, 2004."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.41"},{"volume-title":"Holt","year":"1976","author":"Lawler E. L.","key":"e_1_3_2_1_31_1","unstructured":"E. L. Lawler , Combinatorial optimization: networks and matroids , Holt , Rinehart and Winston , New York , 1976 . E. L. Lawler, Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, New York, 1976."},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms","year":"2005","author":"Lee J. R.","key":"e_1_3_2_1_32_1","unstructured":"J. R. Lee , On distance scales, embeddings, and efficient relaxations of the cut cone , in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms , Vancouver , 2005 , ACM. J. R. Lee, On distance scales, embeddings, and efficient relaxations of the cut cone, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, 2005, ACM."},{"volume-title":"Complexity Issues in VLSI: Optimal Layout for the Shuffle-Exchange Graph and Other Networks","year":"1983","author":"Leighton F. T.","key":"e_1_3_2_1_33_1","unstructured":"F. T. Leighton , Complexity Issues in VLSI: Optimal Layout for the Shuffle-Exchange Graph and Other Networks , MIT Press , Cambridge, MA , 1983 . F. T. Leighton, Complexity Issues in VLSI: Optimal Layout for the Shuffle-Exchange Graph and Other Networks, MIT Press, Cambridge, MA, 1983."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/331524.331526"},{"key":"e_1_3_2_1_35_1","first-page":"270","volume-title":"21th Annual Symposium on Foundations of Computer Science, IEEE Computer Soc.","author":"Leiserson C.","year":"1980","unstructured":"C. Leiserson , Area-efficient graph layouts (for VLSI) , in 21th Annual Symposium on Foundations of Computer Science, IEEE Computer Soc. , Los Alamitos, CA , 1980 , pp. 270 -- 280 . C. Leiserson, Area-efficient graph layouts (for VLSI), in 21th Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, CA, 1980, pp. 270--280."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200757"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0209046"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/256292.256294"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827594262613"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780609"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304983"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(91)90061-N"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215352"},{"volume-title":"Introduction to Graph Theory","year":"1996","author":"West D. B.","key":"e_1_3_2_1_45_1","unstructured":"D. B. West , Introduction to Graph Theory , Prentice Hall Inc ., Upper Saddle River, NJ, 1996 . D. B. West, Introduction to Graph Theory, Prentice Hall Inc., Upper Saddle River, NJ, 1996."}],"event":{"name":"STOC05: Symposium on Theory of Computing","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Baltimore MD USA","acronym":"STOC05"},"container-title":["Proceedings of the thirty-seventh annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1060590.1060674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T08:28:18Z","timestamp":1673166498000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1060590.1060674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5,22]]},"references-count":45,"alternative-id":["10.1145\/1060590.1060674","10.1145\/1060590"],"URL":"http:\/\/dx.doi.org\/10.1145\/1060590.1060674","relation":{},"subject":[],"published":{"date-parts":[[2005,5,22]]},"assertion":[{"value":"2005-05-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}