Using maximal independent sets to solve problems in parallel
type: Item
instance of: scholarly article
title: Using maximal independent sets to solve problems in parallel
zbMATH Open document ID: 0873.68160
DOI: 10.1016/0304-3975(94)00221-4
author: Takayoshi Shoudai
author: Satoru Miyano
published in: Theoretical Computer Science
publication date: 1997-02-28T00:00:00Z
full work available at URL: http://hdl.handle.net/2324/3143
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 984955
zbMATH Keywords: maximal vertex
MaRDI profile type: Publication
OpenAlex ID: W2008807330
cites work: Parallelism and the maximal path problem
cites work: A taxonomy of problems with fast parallel algorithms
cites work: A new fixed point approach for stable networks and stable marriages
cites work: A New Parallel Algorithm for the Maximal Independent Set Problem
cites work: Constructing a Maximal Independent Set in Parallel
cites work: An improved parallel algorithm for maximal matching
cites work: A fast parallel algorithm for the maximal independent set problem
cites work: A Simple Parallel Algorithm for the Maximal Independent Set Problem
cites work: The complexity of circuit value and network stability
cites work: A parallelizable lexicographically first maximal edge-induced subgraph problem
cites work: \(\Delta{} ^ p_ 2\)-complete lexicographically first maximal subgraph problems
cites work: The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
cites work: On uniform circuit complexity
cites work: Simulation of Parallel Random Access Machines by Circuits
Recommended article: Q4694725
Recommended article: Constructing a Maximal Independent Set in Parallel
Recommended article: A Simple Parallel Algorithm for the Maximal Independent Set Problem
Recommended article: A New Parallel Algorithm for the Maximal Independent Set Problem
Recommended article: A fast parallel algorithm for the maximal independent set problem
Recommended article: A fast and simple randomized parallel algorithm for the maximal independent set problem
Recommended article: Probabilistic analysis of a parallel algorithm for finding maximal independent sets
Recommended article: Lower bounds on parallel algorithms for finding the first maximal independent set
Recommended article: An Efficient Parallel Algorithm that Finds Independent Sets of Guaranteed Size
description: scientific article; zbMATH DE number 984955