Using maximal independent sets to solve problems in parallel
From MaRDI portal
Recommendations
- scientific article; zbMATH DE number 219239
- Constructing a Maximal Independent Set in Parallel
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A New Parallel Algorithm for the Maximal Independent Set Problem
- A fast parallel algorithm for the maximal independent set problem
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- Probabilistic analysis of a parallel algorithm for finding maximal independent sets
- Lower bounds on parallel algorithms for finding the first maximal independent set
- An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
Cites work
- \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
- A fast parallel algorithm for the maximal independent set problem
- A new fixed point approach for stable networks and stable marriages
- A New Parallel Algorithm for the Maximal Independent Set Problem
- A parallelizable lexicographically first maximal edge-induced subgraph problem
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A taxonomy of problems with fast parallel algorithms
- An improved parallel algorithm for maximal matching
- Constructing a Maximal Independent Set in Parallel
- On uniform circuit complexity
- Parallelism and the maximal path problem
- Simulation of Parallel Random Access Machines by Circuits
- The complexity of circuit value and network stability
- The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
Cited in
(8)- Parallelism and the maximal path problem
- An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
- Parallel algorithms for maximal acyclic sets
- On the essence of parallel independence for the double-pushout and sesqui-pushout approaches
- PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
- A measure for the lexicographically first maximal independent set problem and its limits
- The parallel complexity of approximating the High Degree Subgraph problem
- NC algorithms for partitioning sparse graphs into induced forests with an application
This page was built for publication: Using maximal independent sets to solve problems in parallel
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q672378)
