Parallel algorithms for fractional and maximal independent sets in planar graphs

DOI10.1016/0166-218X(90)90130-5zbMath0699.68086MaRDI QIDQ913519

N. Dadoun, David G. Kirkpatrick

Publication date: 1990

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

parallel algorithmsmaximal independent setsEREW processorsparallel models of computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Finding a closet visible vertex pair between two polygons ⋮ Parallel construction of subdivision hierarchies ⋮ Optimal parallel 3-coloring algorithm for rooted trees and its applications ⋮ Simplification of FEM-Models on Cell BE

Cites Work

• Unnamed Item
• Parallel construction of subdivision hierarchies
• A new point-location algorithm and its practical efficiency: comparison with existing algorithms
• A simple parallel tree contraction algorithm