{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,5]],"date-time":"2026-02-05T10:11:34Z","timestamp":1770286294267,"version":"3.49.0"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031083327","type":"print"},{"value":"9783031083334","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-08333-4_40","type":"book-chapter","created":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T15:52:13Z","timestamp":1655394733000},"page":"495-506","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Quantum Approach for\u00a0Vertex Separator Problem in\u00a0Directed Graphs"],"prefix":"10.1007","author":[{"given":"Ahmed","family":"Zaiou","sequence":"first","affiliation":[]},{"given":"Youn\u00e8s","family":"Bennani","sequence":"additional","affiliation":[]},{"given":"Mohamed","family":"Hibti","sequence":"additional","affiliation":[]},{"given":"Basarab","family":"Matei","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"issue":"1","key":"40_CR1","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/S0097539705447311","volume":"37","author":"A Ambainis","year":"2007","unstructured":"Ambainis, A.: Quantum walk algorithm for element distinctness. SIAM J. Comput. 37(1), 210\u2013239 (2007)","journal-title":"SIAM J. Comput."},{"key":"40_CR2","unstructured":"Apers, S., Lee, T.: Quantum complexity of minimum cut. arXiv preprint arXiv:2011.09823 (2020)"},{"key":"40_CR3","unstructured":"Ashcraft, C., Liu, J.W.H.: A partition improvement algorithm for generalized nested dissection. Boeing Computer Services, Seattle, WA, Technical report, BCSTECH-94-020 (1994)"},{"issue":"3","key":"40_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1016\/0020-0190(92)90140-Q","volume":"42","author":"TN Bui","year":"1992","unstructured":"Bui, T.N., Jones, C.: Finding good approximate vertex and edge partitions is NP-hard. Inf. Process. Lett. 42(3), 153\u2013159 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"6","key":"40_CR5","doi-asserted-by":"publisher","DOI":"10.1063\/1.4954231","volume":"57","author":"SX Cui","year":"2016","unstructured":"Cui, S.X., Freedman, M.H., Sattath, O., Stong, R., Minton, G.: Quantum max-flow\/min-cut. J. Math. Phys. 57(6), 062206 (2016)","journal-title":"J. Math. Phys."},{"issue":"1","key":"40_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3337792","volume":"46","author":"TA Davis","year":"2019","unstructured":"Davis, T.A., Hager, W.W., Kolodziej, S.P., Yeralan, S.N.: Algorithm 1003: mongoose, a graph coarsening and partitioning library. ACM Trans. Math. Softw. 46(1), 1\u201318 (2019)","journal-title":"ACM Trans. Math. Softw."},{"key":"40_CR7","doi-asserted-by":"crossref","unstructured":"D\u00f6rn, S.: Quantum algorithms for graph traversals and related problems. In: Proceedings of CIE, vol. 7, pp. 123\u2013131. Citeseer (2007)","DOI":"10.1117\/12.719158"},{"issue":"3","key":"40_CR8","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.2.033316","volume":"2","author":"Z Eldredge","year":"2020","unstructured":"Eldredge, Z., et al.: Entanglement bounds on the performance of quantum computing architectures. Phys. Rev. Res. 2(3), 033316 (2020)","journal-title":"Phys. Rev. Res."},{"key":"40_CR9","doi-asserted-by":"crossref","unstructured":"Fiduccia, C.M., Mattheyses, R.M.: A linear-time heuristic for improving network partitions. In: 19th Design Automation Conference, pp. 175\u2013181. IEEE (1982)","DOI":"10.1109\/DAC.1982.1585498"},{"key":"40_CR10","doi-asserted-by":"crossref","unstructured":"Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 212\u2013219 (1996)","DOI":"10.1145\/237814.237866"},{"issue":"2","key":"40_CR11","doi-asserted-by":"publisher","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(2), 328\u2013337 (2015)","journal-title":"Eur. J. Oper. Res."},{"issue":"1","key":"40_CR12","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10589-017-9945-2","volume":"69","author":"WW Hager","year":"2017","unstructured":"Hager, W.W., Hungerford, J.T., Safro, I.: A multilevel bilinear programming algorithm for the vertex separator problem. Comput. Optim. Appl. 69(1), 189\u2013223 (2017). https:\/\/doi.org\/10.1007\/s10589-017-9945-2","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"40_CR13","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1137\/S1064827596300656","volume":"20","author":"B Hendrickson","year":"1998","unstructured":"Hendrickson, B., Rothberg, E.: Improving the run time and quality of nested dissection ordering. SIAM J. Sci. Comput. 20(2), 468\u2013489 (1998)","journal-title":"SIAM J. Sci. Comput."},{"key":"40_CR14","doi-asserted-by":"publisher","first-page":"26","DOI":"10.22331\/q-2017-08-17-26","volume":"1","author":"S Jeffery","year":"2017","unstructured":"Jeffery, S., Kimmel, S.: Quantum algorithms for graph connectivity and formula evaluation. Quantum 1, 26 (2017)","journal-title":"Quantum"},{"issue":"2","key":"40_CR15","doi-asserted-by":"publisher","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(2), 291\u2013307 (1970)","journal-title":"Bell Syst. Tech. J."},{"issue":"3","key":"40_CR16","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1137\/S009753979427087X","volume":"27","author":"T Kloks","year":"1998","unstructured":"Kloks, T., Kratsch, D.: Listing all minimal separators of a graph. SIAM J. Comput. 27(3), 605\u2013613 (1998)","journal-title":"SIAM J. Comput."},{"key":"40_CR17","unstructured":"Kolodziej, S., Davis, T.: Vertex separators with mixed-integer linear optimization. In: 17th SIAM Conference on Parallel Processing for Scientific Computing (2016)"},{"key":"40_CR18","doi-asserted-by":"crossref","unstructured":"Kolodziej, S.P., Davis, T.A.: Generalized gains for hybrid vertex separator algorithms. In: 2020 Proceedings of the SIAM Workshop on Combinatorial Scientific Computing, pp. 96\u2013105. SIAM (2020)","DOI":"10.1137\/1.9781611976229.10"},{"key":"40_CR19","unstructured":"Kolodziej, S.P.: Computational optimization techniques for graph partitioning. Ph.D. thesis (2019)"},{"key":"40_CR20","unstructured":"Bellac, M.L.: Introduction \u00e0 l\u2019information quantique. Belin (2005)"},{"issue":"2","key":"40_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"40_CR22","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"RJ Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput. 9(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"40_CR23","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/050643684","volume":"37","author":"F Magniez","year":"2007","unstructured":"Magniez, F., Santha, M., Szegedy, M.: Quantum algorithms for the triangle problem. SIAM J. Comput. 37(2), 413\u2013424 (2007)","journal-title":"SIAM J. Comput."},{"key":"40_CR24","doi-asserted-by":"crossref","unstructured":"Nielsen, M.A., Chuang, I.: Quantum computation and quantum information (2002)","DOI":"10.1119\/1.1463744"},{"key":"40_CR25","unstructured":"Pednault, E., Gunnels, J.A., Nannicini, G., Horesh, L., Wisnieff, R.: Leveraging secondary storage to simulate deep 54-qubit sycamore circuits. arXiv preprint arXiv:1910.09534 (2019)"},{"key":"40_CR26","unstructured":"Preskill, J.: Quantum computing and the entanglement frontier. arXiv preprint arXiv:1203.5813 (2012)"},{"key":"40_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/978-3-030-61792-9_31","volume-title":"LATIN 2020: Theoretical Informatics","author":"K Shimizu","year":"2020","unstructured":"Shimizu, K., Mori, R.: Exponential-time quantum algorithms for graph coloring problems. In: Kohayakawa, Y., Miyazawa, F.K. (eds.) LATIN 2021. LNCS, vol. 12118, pp. 387\u2013398. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-61792-9_31"},{"issue":"2","key":"40_CR28","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0036144598347011","volume":"41","author":"PW Shor","year":"1999","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 41(2), 303\u2013332 (1999)","journal-title":"SIAM Rev."},{"issue":"6523","key":"40_CR29","doi-asserted-by":"publisher","first-page":"1460","DOI":"10.1126\/science.abe8770","volume":"370","author":"H-S Zhong","year":"2020","unstructured":"Zhong, H.-S., et al.: Quantum computational advantage using photons. Science 370(6523), 1460\u20131463 (2020)","journal-title":"Science"}],"container-title":["IFIP Advances in Information and Communication Technology","Artificial Intelligence Applications and Innovations"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-08333-4_40","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,16]],"date-time":"2022-06-16T16:08:04Z","timestamp":1655395684000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-08333-4_40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031083327","9783031083334"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-08333-4_40","relation":{},"ISSN":["1868-4238","1868-422X"],"issn-type":[{"value":"1868-4238","type":"print"},{"value":"1868-422X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"10 June 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AIAI","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"IFIP International Conference on Artificial Intelligence Applications and Innovations","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hersonissos","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 June 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 June 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"aiai2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ifipaiai.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}