The $(2,k)$-connectivity augmentation problem: Algorithmic aspects

DOI10.1007/S00453-021-00829-4arXiv2004.08645MaRDI QIDQ6338957

Zoltán Szigeti, Florian Hoersch

Publication date: 18 April 2020

Abstract: Durand de Gevigney and Szigeti cite{DgGSz} have recently given a min-max theorem for the $(2,k)$-connectivity augmentation problem. This article provides an $O(n^3(m+nextrmlogextrmn))$ algorithm to find an optimal solution for this problem.

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

This page was built for publication: The $(2,k)$-connectivity augmentation problem: Algorithmic aspects

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6338957)