An efficient NC algorithm for a sparse k-edge-connectivity certificate

DOI10.1007/3-540-49381-6_47MaRDI QIDQ4249538zbMATH OpenFDO

Authors Hiroshi Nagamochi, Toru Hasunuma

Publication date 17 June 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-49381-6_47

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• An efficient \({\mathcal {NC}}\) algorithm for a sparse \(k\)-edge-connectivity certificate
• A faster parallel algorithm for k-connectivity
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
• Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components

Cited in

(4)

• Sparse graph certificates for mixed connectivity
• An efficient \({\mathcal {NC}}\) algorithm for a sparse \(k\)-edge-connectivity certificate
• Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
• Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity

This page was built for publication: An efficient \({\mathcal NC}\) algorithm for a sparse \(k\)-edge-connectivity certificate

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