The maximal f-dependent set problem for planar graphs is in NC

DOI10.1007/3-540-59071-4_51zbMath1528.68281OpenAlexW1596701945MaRDI QIDQ6184372

Zhi-Zhong Chen

Publication date: 5 January 2024

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-59071-4_51

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An improved parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for maximal matching
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• Fast algorithms for edge-coloring planar graphs
• A New Parallel Algorithm for the Maximal Independent Set Problem
• Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets
• PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
• Constructing a Maximal Independent Set in Parallel

This page was built for publication: The maximal f-dependent set problem for planar graphs is in NC