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

DOI10.1016/0304-3975(94)00112-VzbMath0873.68154MaRDI QIDQ673069

Zhi-Zhong Chen

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

maximal \(f\)-dependent set

Mathematics Subject Classification ID

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

Related Items (1)

Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.

Cites Work

• Unnamed Item
• 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
• Matching theory
• 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
• 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