A faster parallel algorithm for \(k\)-connectivity

DOI10.1016/S0020-0190(97)00015-XzbMath1336.68277OpenAlexW2073153454MaRDI QIDQ287014

Kazuo Iwama, T. Ohsawaa, Chuzo Iwamoto

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00015-x

zbMATH Keywords

computational complexityparallel algorithmsPRAM\(k\)-connectivity

Mathematics Subject Classification ID

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

Related Items (1)

OFDP: a distributed algorithm for finding disjoint paths with minimum total length in wireless sensor networks

Cites Work

• Unnamed Item
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• Constructing a perfect matching is in random NC
• Efficient Parallel Algorithms for Testingkand Finding Disjoints-tPaths in Graphs
• Parallel Prefix Computation
• Finding the maximum, merging, and sorting in a parallel computation model
• Network Flow and Testing Graph Connectivity
• A Simpler Parallel Algorithm for Graph Connectivity
• Routing Problems on the Mesh of Buses

This page was built for publication: A faster parallel algorithm for \(k\)-connectivity