{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,21]],"date-time":"2025-12-21T10:03:39Z","timestamp":1766311419193},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,10,4]],"date-time":"2017-10-04T00:00:00Z","timestamp":1507075200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s10589-017-9945-2","type":"journal-article","created":{"date-parts":[[2017,10,4]],"date-time":"2017-10-04T16:10:22Z","timestamp":1507133422000},"page":"189-223","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["A multilevel bilinear programming algorithm for the vertex separator problem"],"prefix":"10.1007","volume":"69","author":[{"given":"William W.","family":"Hager","sequence":"first","affiliation":[]},{"given":"James T.","family":"Hungerford","sequence":"additional","affiliation":[]},{"given":"Ilya","family":"Safro","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,10,4]]},"reference":[{"key":"9945_CR1","doi-asserted-by":"publisher","unstructured":"Acer, S., Kayaaslan, E., Aykanat, C.: A recursive bipartitioning algorithm for permuting sparse square matrices into block diagonal form with overlap. SIAM J. Sci. Comput. 35(1), C99\u2013C121 (2013). doi: 10.1137\/120861242","DOI":"10.1137\/120861242"},{"key":"9945_CR2","unstructured":"Ashcraft, C.C., Liu, J.W.H.: A partition improvement algorithm for generalized nested dissection. Technical Report BCSTECH-94-020, Boeing Computer Services, Seattle, WA (1994)"},{"key":"9945_CR3","doi-asserted-by":"crossref","unstructured":"Benlic, U., Hao, J.: Breakout local search for the vertex separator problem. In: Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (2013)","DOI":"10.1016\/j.engappai.2012.09.001"},{"key":"9945_CR4","volume-title":"Multilevel Optimization and VLSICAD","author":"A Brandt","year":"2003","unstructured":"Brandt, A., Ron, D.: Chapter 1: Multigrid solvers and multilevel optimization strategies. In: Cong, J., Shinnerl, J.R. (eds.) Multilevel Optimization and VLSICAD. Kluwer, Alphen (2003)"},{"key":"9945_CR5","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/0020-0190(92)90140-Q","volume":"42","author":"T Bui","year":"1992","unstructured":"Bui, T., Jones, C.: Finding good approximate vertex and edge partitions is NP-hard. Inf. Process. Lett. 42, 153\u2013159 (1992)","journal-title":"Inf. Process. Lett."},{"key":"9945_CR6","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/978-3-319-49487-6_4","volume-title":"Algorithm Engineering: Selected Results and Surveys","author":"A Bulu\u00e7","year":"2016","unstructured":"Bulu\u00e7, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in graph partitioning. In: Kliemann, L., Sanders, P. (eds.) Algorithm Engineering: Selected Results and Surveys, pp. 117\u2013158. Springer, Berlin (2016)"},{"key":"9945_CR7","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/3-540-49543-6_15","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"M Burmester","year":"1998","unstructured":"Burmester, M., Desmedt, Y., Wang, Y.: Using approximation hardness to achieve dependable computation. In: Luby, M., Rolim, J., Serna, M. (eds.) Randomization and Approximation Techniques in Computer Science, vol. 1518, pp. 172\u2013186. Springer, Berlin (1998). doi: 10.1007\/3-540-49543-6_15 . Lecture Notes in Computer Science"},{"key":"9945_CR8","doi-asserted-by":"crossref","first-page":"3468","DOI":"10.1137\/090775087","volume":"33","author":"J Chen","year":"2011","unstructured":"Chen, J., Safro, I.: Algebraic distance on graphs. SIAM J. Sci. Comput. 33, 3468\u20133490 (2011)","journal-title":"SIAM J. Sci. Comput."},{"key":"9945_CR9","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718881","volume-title":"Direct Methods for Sparse Linear Systems","author":"TA Davis","year":"2006","unstructured":"Davis, T.A.: Direct Methods for Sparse Linear Systems. SIAM, Philadelphia (2006)"},{"key":"9945_CR10","first-page":"1","volume":"38","author":"TA Davis","year":"2011","unstructured":"Davis, T.A.: University of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1\u201325 (2011)","journal-title":"ACM Trans. Math. Softw."},{"key":"9945_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2828635","volume":"42","author":"TA Davis","year":"2016","unstructured":"Davis, T.A., Hager, W.W., Hungerford, J.T.: The separable convex quadratic knapsack problem. ACM Trans. Math. Softw. 42, 1\u201325 (2016)","journal-title":"ACM Trans. Math. Softw."},{"key":"9945_CR12","doi-asserted-by":"crossref","first-page":"635","DOI":"10.3390\/s8020635","volume":"8","author":"C Evrendilek","year":"2008","unstructured":"Evrendilek, C.: Vertex separators for partitioning a graph. Sensors 8, 635\u2013657 (2008)","journal-title":"Sensors"},{"key":"9945_CR13","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1137\/05064299X","volume":"38","author":"U Feige","year":"2008","unstructured":"Feige, U., Hajiaghayi, M., Lee, J.: Improved approximation algorithms for vertex separators. SIAM J. Comput. 38, 629\u2013657 (2008)","journal-title":"SIAM J. Comput."},{"key":"9945_CR14","doi-asserted-by":"crossref","unstructured":"Fiduccia, C.M., Mattheyses, R.M.: A linear-time heuristic for improving network partitions. In: Proceedings of 19th Design Automation Conference, pp. 175\u2013181. Las Vegas, NV (1982)","DOI":"10.1109\/DAC.1982.1585498"},{"issue":"2","key":"9945_CR15","doi-asserted-by":"crossref","first-page":"317","DOI":"10.7155\/jgaa.00130","volume":"10","author":"J Fukuyama","year":"2006","unstructured":"Fukuyama, J.: NP-completeness of the planar separator problems. J. Graph Algorithms Appl. 10(2), 317\u2013328 (2006)","journal-title":"J. Graph Algorithms Appl."},{"key":"9945_CR16","volume-title":"Computer Solution of Large Sparse Positive Definite Systems","author":"A George","year":"1981","unstructured":"George, A., Liu, J.W.H.: Computer Solution of Large Sparse Positive Definite Systems. Prentice-Hall, Englewood Cliffs (1981)"},{"key":"9945_CR17","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1007\/BF01388998","volume":"16","author":"JR Gilbert","year":"1987","unstructured":"Gilbert, J.R., Zmijewski, E.: A parallel graph partitioning algorithm for a message-passing multiprocessor. Intl. J. Parallel Program. 16, 498\u2013513 (1987)","journal-title":"Intl. J. Parallel Program."},{"key":"9945_CR18","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1007\/s10107-013-0644-1","volume":"145","author":"WW Hager","year":"2014","unstructured":"Hager, W.W., Hungerford, J.T.: Optimality conditions for maximizing a function over a polyhedron. Math. Program. 145, 179\u2013198 (2014)","journal-title":"Math. Program."},{"key":"9945_CR19","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1016\/j.ejor.2014.05.042","volume":"240","author":"WW Hager","year":"2015","unstructured":"Hager, W.W., Hungerford, J.T.: Continuous quadratic programming formulations of optimization problems on graphs. Eur. J. Oper. Res. 240, 328\u2013337 (2015)","journal-title":"Eur. J. Oper. Res."},{"key":"9945_CR20","doi-asserted-by":"crossref","unstructured":"Hendrickson, B., Leland, R.: A multilevel algorithm for partitioning graphs. In: Proceedings of Supercomputing \u201995. IEEE (1995)","DOI":"10.1145\/224170.224228"},{"key":"9945_CR21","unstructured":"Hendrickson, B., Rothberg, E.: Effective sparse matrix ordering: just around the bend. In: Proceedings of 8th SIAM Conference on Parallel Processing for Scientific Computing (1997)"},{"key":"9945_CR22","unstructured":"http:\/\/snap.stanford.edu\/data\/"},{"key":"9945_CR23","unstructured":"Karypis, G., Kumar, V.: METIS: unstructured graph partitioning and sparse matrix ordering system. Technical Report, Department of Computer Science, University of Minnesota (1995)"},{"key":"9945_CR24","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1137\/S1064827595287997","volume":"20","author":"G Karypis","year":"1998","unstructured":"Karypis, G., Kumar, V.: A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. Sci. Comput. 20, 359\u2013392 (1998)","journal-title":"SIAM J. Sci. Comput."},{"issue":"2","key":"9945_CR25","doi-asserted-by":"crossref","first-page":"A970","DOI":"10.1137\/100810022","volume":"34","author":"E Kayaaslan","year":"2012","unstructured":"Kayaaslan, E., Pinar, A., Cataly\u00fcrek, U., Aykanat, C.: Partitioning hypergraphs in scientific computing applications through vertex separators. SIAM J. Sci. Comput. 34(2), A970\u2013A992 (2012)","journal-title":"SIAM J. Sci. Comput."},{"key":"9945_CR26","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","volume":"49","author":"BW Kernighan","year":"1970","unstructured":"Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, 291\u2013307 (1970)","journal-title":"Bell Syst. Tech. J."},{"key":"9945_CR27","doi-asserted-by":"crossref","unstructured":"Kim, D., Frye, G.R., Kwon, S.S., Chang, H.J., Tokuta, A.O.: On combinatoric approach to circumvent internet censorship using decoy routers. In: Military Communications Conference, 2013. MILCOM 2013., pp. 1\u20136. IEEE (2013)","DOI":"10.1109\/MILCOM.2013.107"},{"key":"9945_CR28","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/BF01580367","volume":"11","author":"H Konno","year":"1976","unstructured":"Konno, H.: A cutting plane algorithm for solving bilinear programs. Math. Program. 11, 14\u201327 (1976)","journal-title":"Math. Program."},{"key":"9945_CR29","unstructured":"Leiserson, C., Lewis, J.: Orderings for parallel sparse symmetric factorization. In: Third SIAM Conference on Parallel Processing for Scientific Computing, pp. 27\u201331. SIAM Publications (1987)"},{"key":"9945_CR30","doi-asserted-by":"crossref","unstructured":"Leiserson, C.: Area-efficient graph layout (for VLSI). In: Proceedings of 21st Annual Symposium on the Foundations of Computer Science, pp. 270\u2013281. IEEE (1980)","DOI":"10.1109\/SFCS.1980.13"},{"key":"9945_CR31","unstructured":"Litsas, C., Pagourtzis, A., Panagiotakos, G., Sakavalas, D.: On the resilience and uniqueness of CPA for secure broadcast. In: IACR Cryptology ePrint Archive (2013)"},{"key":"9945_CR32","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1137\/S1064827594262613","volume":"19","author":"G Miller","year":"1998","unstructured":"Miller, G., Teng, S.H., Thurston, W., Vavasis, S.: Geometric separators for finite element meshes. SIAM J. Sci. Comput. 19, 364\u2013386 (1998)","journal-title":"SIAM J. Sci. Comput."},{"key":"9945_CR33","volume-title":"Numerical Optimization","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.J.: Numerical Optimization, 2nd edn. Springer, New York (2006)","edition":"2"},{"issue":"3","key":"9945_CR34","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A Pothen","year":"1990","unstructured":"Pothen, A., Simon, H.D., Liou, K.: Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl. 11(3), 430\u2013452 (1990)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"9945_CR35","doi-asserted-by":"publisher","unstructured":"Rendl, F., Sotirov, R.: The min-cut and vertex separator problem. Comput. Optim. Appl. (2017). doi: 10.1007\/s10589-017-9943-4","DOI":"10.1007\/s10589-017-9943-4"},{"issue":"1","key":"9945_CR36","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1137\/100791142","volume":"9","author":"D Ron","year":"2011","unstructured":"Ron, D., Safro, I., Brandt, A.: Relaxation-based coarsening and multiscale graph organization. Multiscale Model. Simul. 9(1), 407\u2013423 (2011)","journal-title":"Multiscale Model. Simul."},{"key":"9945_CR37","doi-asserted-by":"crossref","unstructured":"Safro, I., Sanders, P., Schulz, C.: Advanced coarsening schemes for graph partitioning. ACM J. Exp. Algorithm. 19(2), Article 2.2 (2014)","DOI":"10.1145\/2670338"},{"key":"9945_CR38","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/j.jalgor.2004.10.004","volume":"60","author":"I Safro","year":"2006","unstructured":"Safro, I., Ron, D., Brandt, A.: Graph minimum linear arrangement by multilevel weighted edge contractions. J. Algorithms 60, 24\u201341 (2006)","journal-title":"J. Algorithms"},{"key":"9945_CR39","volume-title":"Computational Aspects of VLSI","author":"J Ullman","year":"1984","unstructured":"Ullman, J.: Computational Aspects of VLSI. Computer Science Press, Rockville (1984)"},{"key":"9945_CR40","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4614-7630-6","volume-title":"Linear Programming: Foundations and Extensions","author":"RJ Vanderbei","year":"2014","unstructured":"Vanderbei, R.J.: Linear Programming: Foundations and Extensions, 4th edn. Springer, Berlin (2014)","edition":"4"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-017-9945-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-017-9945-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-017-9945-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,18]],"date-time":"2020-10-18T18:44:48Z","timestamp":1603046688000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-017-9945-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,4]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9945"],"URL":"https:\/\/doi.org\/10.1007\/s10589-017-9945-2","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,4]]}}}