Fast RNC and NC algorithms for maximal path sets

DOI10.1016/S0304-3975(97)00132-1MaRDI QIDQ1285573zbMATH OpenOpenAlexFDO

Authors Ryuhei Uehara, Zhi-Zhong Chen, Xin He

Publication date 28 April 1999

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(97)00132-1

zbMATH Keywords

approximation algorithmsgraph algorithmsparallel algorithmsrandomized parallel algorithmsmaximal path setsshortest common superstrings

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Recommendations

• NC algorithms for finding a maximal set of paths with application to compressing strings
• A fast and efficient NC algorithm for maximal matching
• scientific article; zbMATH DE number 7678024
• A parallel algorithm for the maximal path problem
• Parallel complexity of computing a maximal set of disjoint paths
• -Algorithms for Minimum Link Path and Related Problems
• NC algorithms for dynamically solving the all pairs shortest paths problem and related problems
• Efficient Algorithms for Finding the Maximum Number of Disjoint Paths in Grids
• A fast parameterized algorithm for co-path set
• Fast sequential and parallel algorithms for finding extremal sets

Cites work

• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A fast and efficient NC algorithm for maximal matching
• A fast and simple randomized parallel algorithm for maximal matching
• Parallel and sequential approximation of shortest superstrings
• Parallel constructions of maximal path sets and applications to short superstrings

Cited in

(4)

• NC algorithms for finding a maximal set of paths with application to compressing strings
• Parallelism and the maximal path problem
• Fast RNC and NC algorithms for finding a maximal set of paths with an application
• A randomized NC algorithm for the maximal tree cover problem

This page was built for publication: Fast RNC and NC algorithms for maximal path sets

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