A new graph triconnectivity algorithm and its parallelization

DOI10.1007/BF01191205MaRDI QIDQ1193533zbMATH OpenFDO

Authors Vijaya Ramachandran, Gary L. Miller

Publication date 27 September 1992

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01191205

zbMATH Keywords

graph triconnectivity algorithmparallelization

Mathematics Subject Classification ID

Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Distributed algorithms (68W15)

Recommendations

• Finding Triconnected Components by Local Replacement
• A parallel algorithm for finding a triconnected component separator with an application
• scientific article; zbMATH DE number 1102788
• scientific article; zbMATH DE number 4155927
• Improved algorithms for graph four-connectivity

Cites work

• An Efficient Parallel Biconnectivity Algorithm
• Dividing a Graph into Triconnected Components
• scientific article; zbMATH DE number 3688740 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• Improved algorithms for graph four-connectivity
• Non-Separable and Planar Graphs
• Parallel Algorithms in Graph Theory: Planarity Testing
• Parallel ear decomposition search (EDS) and st-numbering in graphs
• Parallel Merge Sort

Cited in

(17)

• Parallel search algorithms for graphs and trees
• A parallel algorithm for finding a triconnected component separator with an application
• Planarity testing in parallel
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors
• An O(n+m) certifying triconnnectivity algorithm for Hamiltonian graphs
• scientific article; zbMATH DE number 4155927 (Why is no real title available?)
• scientific article; zbMATH DE number 4060743 (Why is no real title available?)
• scientific article; zbMATH DE number 4065021 (Why is no real title available?)
• Finding Triconnected Components by Local Replacement
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• Certifying algorithms
• Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge
• Counting the number of perfect matchings in \(K_{5}\)-free graphs
• Fully dynamic 2-edge-connectivity in planar graphs
• A simple randomized 3-edge connected component algorithm
• Efficient parallel graph algorithms based on open ear decomposition
• Successive approximation in parallel graph algorithms

This page was built for publication: A new graph triconnectivity algorithm and its parallelization

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