Using maximal independent sets to solve problems in parallel
From MaRDI portal
Publication:672378
DOI10.1016/0304-3975(94)00221-4zbMath0873.68160MaRDI QIDQ672378
Takayoshi Shoudai, Satoru Miyano
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2324/3143
68R10: Graph theory (including graph drawing) in computer science
Related Items
Cites Work
- An improved parallel algorithm for maximal matching
- Parallelism and the maximal path problem
- A parallelizable lexicographically first maximal edge-induced subgraph problem
- On uniform circuit complexity
- \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
- The complexity of circuit value and network stability
- A new fixed point approach for stable networks and stable marriages
- Simulation of Parallel Random Access Machines by Circuits
- A taxonomy of problems with fast parallel algorithms
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A fast parallel algorithm for the maximal independent set problem
- A New Parallel Algorithm for the Maximal Independent Set Problem
- The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
- Constructing a Maximal Independent Set in Parallel
