[{"publication_status":"published","oa_version":"Submitted Version","title":"Learning deposition policies for fused multi-material 3D printing","abstract":[{"lang":"eng","text":"3D printing based on continuous deposition of materials, such as filament-based 3D printing, has seen widespread adoption thanks to its versatility in working with a wide range of materials. An important shortcoming of this type of technology is its limited multi-material capabilities. While there are simple hardware designs that enable multi-material printing in principle, the required software is heavily underdeveloped. A typical hardware design fuses together individual materials fed into a single chamber from multiple inlets before they are deposited. This design, however, introduces a time delay between the intended material mixture and its actual deposition. In this work, inspired by diverse path planning research in robotics, we show that this mechanical challenge can be addressed via improved printer control. We propose to formulate the search for optimal multi-material printing policies in a reinforcement\r\nlearning setup. We put forward a simple numerical deposition model that takes into account the non-linear material mixing and delayed material deposition. To validate our system we focus on color fabrication, a problem known for its strict requirements for varying material mixtures at a high spatial frequency. We demonstrate that our learned control policy outperforms state-of-the-art hand-crafted algorithms."}],"file_date_updated":"2023-05-16T09:12:05Z","quality_controlled":"1","page":"12345-12352","publication_identifier":{"eisbn":["9798350323658"],"issn":["1050-4729"]},"volume":2023,"intvolume":"      2023","acknowledgement":"This work is graciously supported by FWF Lise Meitner (Grant M 3319). Kang Liao sincerely thank Emiliano Luci, Chunyu Lin, and Yao Zhao for their huge support.","date_published":"2023-07-04T00:00:00Z","oa":1,"citation":{"apa":"Liao, K., Tricard, T., Piovarci, M., Seidel, H.-P., &#38; Babaei, V. (2023). Learning deposition policies for fused multi-material 3D printing. In <i>2023 IEEE International Conference on Robotics and Automation</i> (Vol. 2023, pp. 12345–12352). London, United Kingdom: IEEE. <a href=\"https://doi.org/10.1109/ICRA48891.2023.10160465\">https://doi.org/10.1109/ICRA48891.2023.10160465</a>","ama":"Liao K, Tricard T, Piovarci M, Seidel H-P, Babaei V. Learning deposition policies for fused multi-material 3D printing. In: <i>2023 IEEE International Conference on Robotics and Automation</i>. Vol 2023. IEEE; 2023:12345-12352. doi:<a href=\"https://doi.org/10.1109/ICRA48891.2023.10160465\">10.1109/ICRA48891.2023.10160465</a>","chicago":"Liao, Kang, Thibault Tricard, Michael Piovarci, Hans-Peter Seidel, and Vahid Babaei. “Learning Deposition Policies for Fused Multi-Material 3D Printing.” In <i>2023 IEEE International Conference on Robotics and Automation</i>, 2023:12345–52. IEEE, 2023. <a href=\"https://doi.org/10.1109/ICRA48891.2023.10160465\">https://doi.org/10.1109/ICRA48891.2023.10160465</a>.","mla":"Liao, Kang, et al. “Learning Deposition Policies for Fused Multi-Material 3D Printing.” <i>2023 IEEE International Conference on Robotics and Automation</i>, vol. 2023, IEEE, 2023, pp. 12345–52, doi:<a href=\"https://doi.org/10.1109/ICRA48891.2023.10160465\">10.1109/ICRA48891.2023.10160465</a>.","short":"K. Liao, T. Tricard, M. Piovarci, H.-P. Seidel, V. Babaei, in:, 2023 IEEE International Conference on Robotics and Automation, IEEE, 2023, pp. 12345–12352.","ieee":"K. Liao, T. Tricard, M. Piovarci, H.-P. Seidel, and V. Babaei, “Learning deposition policies for fused multi-material 3D printing,” in <i>2023 IEEE International Conference on Robotics and Automation</i>, London, United Kingdom, 2023, vol. 2023, pp. 12345–12352.","ista":"Liao K, Tricard T, Piovarci M, Seidel H-P, Babaei V. 2023. Learning deposition policies for fused multi-material 3D printing. 2023 IEEE International Conference on Robotics and Automation. ICRA: International Conference on Robotics and Automation vol. 2023, 12345–12352."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Liao, Kang","last_name":"Liao","first_name":"Kang"},{"first_name":"Thibault","last_name":"Tricard","full_name":"Tricard, Thibault"},{"id":"62E473F4-5C99-11EA-A40E-AF823DDC885E","full_name":"Piovarci, Michael","orcid":"0000-0002-5062-4474","last_name":"Piovarci","first_name":"Michael"},{"full_name":"Seidel, Hans-Peter","last_name":"Seidel","first_name":"Hans-Peter"},{"first_name":"Vahid","last_name":"Babaei","full_name":"Babaei, Vahid"}],"date_created":"2023-05-16T09:14:09Z","doi":"10.1109/ICRA48891.2023.10160465","_id":"12976","scopus_import":"1","file":[{"relation":"main_file","creator":"mpiovarc","access_level":"open_access","checksum":"daeaa67124777d88487f933ea3f77164","date_created":"2023-05-16T09:12:05Z","file_name":"Liao2023.pdf","file_id":"12977","success":1,"file_size":5367986,"date_updated":"2023-05-16T09:12:05Z","content_type":"application/pdf"}],"ddc":["004"],"date_updated":"2025-04-15T07:43:52Z","language":[{"iso":"eng"}],"article_processing_charge":"No","publication":"2023 IEEE International Conference on Robotics and Automation","isi":1,"has_accepted_license":"1","department":[{"_id":"BeBi"}],"external_id":{"isi":["001048371104068"]},"status":"public","project":[{"_id":"eb901961-77a9-11ec-83b8-f5c883a62027","grant_number":"M03319","name":"Perception-Aware Appearance Fabrication"}],"type":"conference","year":"2023","keyword":["reinforcement learning","deposition","control","color","multi-filament"],"day":"04","conference":{"end_date":"2023-06-02","name":"ICRA: International Conference on Robotics and Automation","start_date":"2023-05-29","location":"London, United Kingdom"},"publisher":"IEEE","month":"07"},{"article_type":"original","volume":108,"publication_identifier":{"eissn":["1573-269X"],"issn":["0924-090X"]},"acknowledgement":"The authors thank Enrique Calisto,Michal Kowalczyk, and Michel Ferre for fructified discussions. This work was funded by ANID—Millennium Science Initiative Program—ICN17_012. MGC is thankful for financial support from the Fondecyt 1210353 project.\r\nOpen access funding provided by Institute of Science and Technology (IST Austria).","intvolume":"       108","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"apa":"Aguilera, E., Clerc, M. G., &#38; Zambra, V. (2022). Vortices nucleation by inherent fluctuations in nematic liquid crystal cells. <i>Nonlinear Dynamics</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11071-022-07396-5\">https://doi.org/10.1007/s11071-022-07396-5</a>","short":"E. Aguilera, M.G. Clerc, V. Zambra, Nonlinear Dynamics 108 (2022) 3209–3218.","chicago":"Aguilera, Esteban, Marcel G. Clerc, and Valeska Zambra. “Vortices Nucleation by Inherent Fluctuations in Nematic Liquid Crystal Cells.” <i>Nonlinear Dynamics</i>. Springer Nature, 2022. <a href=\"https://doi.org/10.1007/s11071-022-07396-5\">https://doi.org/10.1007/s11071-022-07396-5</a>.","mla":"Aguilera, Esteban, et al. “Vortices Nucleation by Inherent Fluctuations in Nematic Liquid Crystal Cells.” <i>Nonlinear Dynamics</i>, vol. 108, Springer Nature, 2022, pp. 3209–18, doi:<a href=\"https://doi.org/10.1007/s11071-022-07396-5\">10.1007/s11071-022-07396-5</a>.","ama":"Aguilera E, Clerc MG, Zambra V. Vortices nucleation by inherent fluctuations in nematic liquid crystal cells. <i>Nonlinear Dynamics</i>. 2022;108:3209-3218. doi:<a href=\"https://doi.org/10.1007/s11071-022-07396-5\">10.1007/s11071-022-07396-5</a>","ieee":"E. Aguilera, M. G. Clerc, and V. Zambra, “Vortices nucleation by inherent fluctuations in nematic liquid crystal cells,” <i>Nonlinear Dynamics</i>, vol. 108. Springer Nature, pp. 3209–3218, 2022.","ista":"Aguilera E, Clerc MG, Zambra V. 2022. Vortices nucleation by inherent fluctuations in nematic liquid crystal cells. Nonlinear Dynamics. 108, 3209–3218."},"oa":1,"date_published":"2022-06-01T00:00:00Z","scopus_import":"1","_id":"11343","doi":"10.1007/s11071-022-07396-5","author":[{"last_name":"Aguilera","first_name":"Esteban","full_name":"Aguilera, Esteban"},{"full_name":"Clerc, Marcel G.","last_name":"Clerc","first_name":"Marcel G."},{"first_name":"Valeska","last_name":"Zambra","full_name":"Zambra, Valeska","id":"467ed36b-dc96-11ea-b7c8-b043a380b282"}],"date_created":"2022-05-02T07:01:59Z","oa_version":"Published Version","title":"Vortices nucleation by inherent fluctuations in nematic liquid crystal cells","publication_status":"published","abstract":[{"text":"Multistable systems are characterized by exhibiting domain coexistence, where each domain accounts for the different equilibrium states. In case these systems are described by vectorial fields, domains can be connected through topological defects. Vortices are one of the most frequent and studied topological defect points. Optical vortices are equally relevant for their fundamental features as beams with topological features and their applications in image processing, telecommunications, optical tweezers, and quantum information. A natural source of optical vortices is the interaction of light beams with matter vortices in liquid crystal cells. The rhythms that govern the emergence of matter vortices due to fluctuations are not established. Here, we investigate the nucleation mechanisms of the matter vortices in liquid crystal cells and establish statistical laws that govern them. Based on a stochastic amplitude equation, the law for the number of nucleated vortices as a function of anisotropy, voltage, and noise level intensity is set. Experimental observations in a nematic liquid crystal cell with homeotropic anchoring and a negative anisotropic dielectric constant under the influence of a transversal electric field show a qualitative agreement with the theoretical findings.","lang":"eng"}],"quality_controlled":"1","file_date_updated":"2022-08-05T06:13:19Z","page":"3209-3218","year":"2022","type":"journal_article","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png"},"keyword":["Electrical and Electronic Engineering","Applied Mathematics","Mechanical Engineering","Ocean Engineering","Aerospace Engineering","Control and Systems Engineering"],"license":"https://creativecommons.org/licenses/by/4.0/","day":"01","month":"06","corr_author":"1","publisher":"Springer Nature","ddc":["530"],"date_updated":"2024-10-09T21:02:21Z","file":[{"checksum":"7d80cdece4e1b1c2106e6772a9622f60","date_created":"2022-08-05T06:13:19Z","file_id":"11728","file_name":"2022_NonlinearDyn_Aguilera.pdf","access_level":"open_access","creator":"dernst","relation":"main_file","date_updated":"2022-08-05T06:13:19Z","file_size":1416049,"content_type":"application/pdf","success":1}],"language":[{"iso":"eng"}],"department":[{"_id":"KiMo"}],"has_accepted_license":"1","isi":1,"publication":"Nonlinear Dynamics","article_processing_charge":"Yes (via OA deal)","status":"public","external_id":{"isi":["000784871800001"]}},{"intvolume":"        68","volume":68,"publication_identifier":{"issn":["0004-5411"],"eissn":["1557-735X"]},"article_type":"original","_id":"15267","doi":"10.1145/3446383","date_created":"2024-04-03T07:41:46Z","author":[{"full_name":"Czumaj, Artur","last_name":"Czumaj","first_name":"Artur"},{"full_name":"Davies, Peter","id":"11396234-BB50-11E9-B24C-90FCE5697425","first_name":"Peter","orcid":"0000-0002-5646-9524","last_name":"Davies"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"2021-01-28T00:00:00Z","oa":1,"citation":{"ama":"Czumaj A, Davies P. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. <i>Journal of the ACM</i>. 2021;68(2). doi:<a href=\"https://doi.org/10.1145/3446383\">10.1145/3446383</a>","chicago":"Czumaj, Artur, and Peter Davies. “Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks.” <i>Journal of the ACM</i>. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3446383\">https://doi.org/10.1145/3446383</a>.","mla":"Czumaj, Artur, and Peter Davies. “Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks.” <i>Journal of the ACM</i>, vol. 68, no. 2, 13, Association for Computing Machinery, 2021, doi:<a href=\"https://doi.org/10.1145/3446383\">10.1145/3446383</a>.","short":"A. Czumaj, P. Davies, Journal of the ACM 68 (2021).","apa":"Czumaj, A., &#38; Davies, P. (2021). Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. <i>Journal of the ACM</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3446383\">https://doi.org/10.1145/3446383</a>","ista":"Czumaj A, Davies P. 2021. Exploiting spontaneous transmissions for broadcasting and leader election in radio networks. Journal of the ACM. 68(2), 13.","ieee":"A. Czumaj and P. Davies, “Exploiting spontaneous transmissions for broadcasting and leader election in radio networks,” <i>Journal of the ACM</i>, vol. 68, no. 2. Association for Computing Machinery, 2021."},"arxiv":1,"abstract":[{"lang":"eng","text":"We study two fundamental communication primitives: broadcasting and leader election in the classical model of multi-hop radio networks with unknown topology and without collision detection mechanisms. It has been known for almost 20 years that in undirected networks with n nodes and diameter D, randomized broadcasting requires Ω(D log n/D + log2 n) rounds, assuming that uninformed nodes are not allowed to communicate (until they are informed). Only very recently, Haeupler and Wajc (PODC'2016) showed that this bound can be improved for the model with spontaneous transmissions, providing an O(D log n log log n/log D + logO(1) n)-time broadcasting algorithm. In this article, we give a new and faster algorithm that completes broadcasting in O(D log n/log D + logO(1) n) time, succeeding with high probability. This yields the first optimal O(D)-time broadcasting algorithm whenever n is polynomial in D.\r\n\r\nFurthermore, our approach can be applied to design a new leader election algorithm that matches the performance of our broadcasting algorithm. Previously, all fast randomized leader election algorithms have used broadcasting as a subroutine and their complexity has been asymptotically strictly larger than the complexity of broadcasting. In particular, the fastest previously known randomized leader election algorithm of Ghaffari and Haeupler (SODA'2013) requires O(D log n/D min {log log n, log n/D} + logO(1) n)-time, succeeding with high probability. Our new algorithm again requires O(D log n/log D + logO(1) n) time, also succeeding with high probability."}],"title":"Exploiting spontaneous transmissions for broadcasting and leader election in radio networks","oa_version":"Preprint","publication_status":"published","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.1703.01859"}],"quality_controlled":"1","keyword":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"year":"2021","type":"journal_article","month":"01","publisher":"Association for Computing Machinery","day":"28","issue":"2","language":[{"iso":"eng"}],"date_updated":"2024-04-29T06:47:59Z","status":"public","external_id":{"arxiv":["1703.01859"]},"article_number":"13","publication":"Journal of the ACM","department":[{"_id":"DaAl"}],"article_processing_charge":"No"},{"extern":"1","date_created":"2018-12-11T11:46:04Z","author":[{"id":"43C61214-F248-11E8-B48F-1D18A9856A87","full_name":"Ibáñez, Maria","last_name":"Ibáñez","orcid":"0000-0001-5013-2843","first_name":"Maria"},{"last_name":"Berestok","first_name":"Taisiia","full_name":"Berestok, Taisiia"},{"first_name":"Oleksandr","last_name":"Dobrozhan","full_name":"Dobrozhan, Oleksandr"},{"first_name":"Aaron","last_name":"Lalonde","full_name":"Lalonde, Aaron"},{"full_name":"Izquierdo Roca, Victor","first_name":"Victor","last_name":"Izquierdo Roca"},{"first_name":"Alexey","last_name":"Shavel","full_name":"Shavel, Alexey"},{"last_name":"Pérez Rodríguez","first_name":"Alejandro","full_name":"Pérez Rodríguez, Alejandro"},{"full_name":"Snyder, G Jeffrey","first_name":"G Jeffrey","last_name":"Snyder"},{"first_name":"Andreu","last_name":"Cabot","full_name":"Cabot, Andreu"}],"doi":"10.1007/s11051-016-3545-4","_id":"367","date_published":"2016-08-11T00:00:00Z","citation":{"short":"M. Ibáñez, T. Berestok, O. Dobrozhan, A. Lalonde, V. Izquierdo Roca, A. Shavel, A. Pérez Rodríguez, G.J. Snyder, A. Cabot, Journal of Nanoparticle Research 18 (2016).","chicago":"Ibáñez, Maria, Taisiia Berestok, Oleksandr Dobrozhan, Aaron Lalonde, Victor Izquierdo Roca, Alexey Shavel, Alejandro Pérez Rodríguez, G Jeffrey Snyder, and Andreu Cabot. “Phosphonic Acids Aid Composition Adjustment in the Synthesis of Cu2+xZn1−xSnSe4−y Nanoparticles.” <i>Journal of Nanoparticle Research</i>. Springer Nature, 2016. <a href=\"https://doi.org/10.1007/s11051-016-3545-4\">https://doi.org/10.1007/s11051-016-3545-4</a>.","mla":"Ibáñez, Maria, et al. “Phosphonic Acids Aid Composition Adjustment in the Synthesis of Cu2+xZn1−xSnSe4−y Nanoparticles.” <i>Journal of Nanoparticle Research</i>, vol. 18, 226, Springer Nature, 2016, doi:<a href=\"https://doi.org/10.1007/s11051-016-3545-4\">10.1007/s11051-016-3545-4</a>.","ama":"Ibáñez M, Berestok T, Dobrozhan O, et al. Phosphonic acids aid composition adjustment in the synthesis of Cu2+xZn1−xSnSe4−y nanoparticles. <i>Journal of Nanoparticle Research</i>. 2016;18. doi:<a href=\"https://doi.org/10.1007/s11051-016-3545-4\">10.1007/s11051-016-3545-4</a>","apa":"Ibáñez, M., Berestok, T., Dobrozhan, O., Lalonde, A., Izquierdo Roca, V., Shavel, A., … Cabot, A. (2016). Phosphonic acids aid composition adjustment in the synthesis of Cu2+xZn1−xSnSe4−y nanoparticles. <i>Journal of Nanoparticle Research</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s11051-016-3545-4\">https://doi.org/10.1007/s11051-016-3545-4</a>","ista":"Ibáñez M, Berestok T, Dobrozhan O, Lalonde A, Izquierdo Roca V, Shavel A, Pérez Rodríguez A, Snyder GJ, Cabot A. 2016. Phosphonic acids aid composition adjustment in the synthesis of Cu2+xZn1−xSnSe4−y nanoparticles. Journal of Nanoparticle Research. 18, 226.","ieee":"M. Ibáñez <i>et al.</i>, “Phosphonic acids aid composition adjustment in the synthesis of Cu2+xZn1−xSnSe4−y nanoparticles,” <i>Journal of Nanoparticle Research</i>, vol. 18. Springer Nature, 2016."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"        18","publication_identifier":{"eissn":["1572-896X"],"issn":["1388-0764"]},"volume":18,"article_type":"original","quality_controlled":"1","abstract":[{"text":"The functional properties of quaternary I2–II–IV–VI4 nanomaterials, with potential interest in various technological fields, are highly sensitive to compositional variations, which is a challenging parameter to adjust. Here we demonstrate the presence of phosphonic acids to aid controlling the reactivity of the II element monomer to be incorporated in quaternary Cu2ZnSnSe4 nanoparticles and thus to provide a more reliable way to adjust the final nanoparticle metal ratios. Furthermore, we demonstrate the composition control in such multivalence nanoparticles to allow modifying charge carrier concentrations in nanomaterials produced from the assembly of these building blocks. ","lang":"eng"}],"publication_status":"published","title":"Phosphonic acids aid composition adjustment in the synthesis of Cu2+xZn1−xSnSe4−y nanoparticles","oa_version":"None","publisher":"Springer Nature","month":"08","publist_id":"7461","day":"11","OA_type":"closed access","keyword":["CZTSe","Nanostructured materials","Colloidal synthesis","Composition control","Electrical transport:  Thermoelectric"],"type":"journal_article","year":"2016","article_number":"226","status":"public","article_processing_charge":"No","publication":"Journal of Nanoparticle Research","language":[{"iso":"eng"}],"date_updated":"2026-05-18T09:21:57Z"},{"publisher":"Elsevier","month":"02","issue":"2","day":"01","keyword":["Computational Theory and Mathematics","Computational Mathematics","Control and Optimization"],"type":"journal_article","year":"2000","status":"public","article_processing_charge":"No","publication":"Journal of Algorithms","language":[{"iso":"eng"}],"date_updated":"2024-11-04T11:42:08Z","date_created":"2022-07-28T08:56:10Z","extern":"1","doi":"10.1006/jagm.1999.1055","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","orcid":"0000-0002-5008-6530","last_name":"Henzinger","first_name":"Monika H"},{"full_name":"Rao, Satish","last_name":"Rao","first_name":"Satish"},{"last_name":"Gabow","first_name":"Harold N.","full_name":"Gabow, Harold N."}],"_id":"11683","scopus_import":"1","date_published":"2000-02-01T00:00:00Z","citation":{"ista":"Henzinger M, Rao S, Gabow HN. 2000. Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms. 34(2), 222–250.","ieee":"M. Henzinger, S. Rao, and H. N. Gabow, “Computing vertex connectivity: New bounds from old techniques,” <i>Journal of Algorithms</i>, vol. 34, no. 2. Elsevier, pp. 222–250, 2000.","mla":"Henzinger, Monika, et al. “Computing Vertex Connectivity: New Bounds from Old Techniques.” <i>Journal of Algorithms</i>, vol. 34, no. 2, Elsevier, 2000, pp. 222–50, doi:<a href=\"https://doi.org/10.1006/jagm.1999.1055\">10.1006/jagm.1999.1055</a>.","chicago":"Henzinger, Monika, Satish Rao, and Harold N. Gabow. “Computing Vertex Connectivity: New Bounds from Old Techniques.” <i>Journal of Algorithms</i>. Elsevier, 2000. <a href=\"https://doi.org/10.1006/jagm.1999.1055\">https://doi.org/10.1006/jagm.1999.1055</a>.","short":"M. Henzinger, S. Rao, H.N. Gabow, Journal of Algorithms 34 (2000) 222–250.","ama":"Henzinger M, Rao S, Gabow HN. Computing vertex connectivity: New bounds from old techniques. <i>Journal of Algorithms</i>. 2000;34(2):222-250. doi:<a href=\"https://doi.org/10.1006/jagm.1999.1055\">10.1006/jagm.1999.1055</a>","apa":"Henzinger, M., Rao, S., &#38; Gabow, H. N. (2000). Computing vertex connectivity: New bounds from old techniques. <i>Journal of Algorithms</i>. Elsevier. <a href=\"https://doi.org/10.1006/jagm.1999.1055\">https://doi.org/10.1006/jagm.1999.1055</a>"},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":"        34","publication_identifier":{"issn":["0196-6774"]},"volume":34,"article_type":"original","page":"222-250","quality_controlled":"1","abstract":[{"text":"The vertex connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{κ3 + n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(κ1nmlog(n2/m)) where κ1 ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n2/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorithms17, 424–446) that computes edge connectivity.","lang":"eng"}],"publication_status":"published","title":"Computing vertex connectivity: New bounds from old techniques","oa_version":"None"}]