Using maximal independent sets to solve problems in parallel

DOI10.1016/0304-3975(94)00221-4zbMath0873.68160OpenAlexW2008807330MaRDI QIDQ672378

Satoru Miyano, Takayoshi Shoudai

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

zbMATH Keywords

maximal vertex

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

A MEASURE FOR THE LEXICOGRAPHICALLY FIRST MAXIMAL INDEPENDENT SET PROBLEM AND ITS LIMITS

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

This page was built for publication: Using maximal independent sets to solve problems in parallel