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

DOI10.1016/0304-3975(94)00112-VMaRDI QIDQ673069zbMATHFDO

Authors 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)

Recommendations

• The maximal f-dependent set problem for planar graphs is in NC
• The Maximum Independent Set Problem in Planar Graphs
• On the maximum independent set problem in subclasses of planar graphs
• The maximum independent set problem for cubic planar graphs
• A simple proof that finding a maximal independent set in a graph is in NC
• Building a maximal independent set for the vertex-coloring problem on planar graphs
• The complexity of some problems on maximal independent sets in graphs
• On maximal planarization of nonplanar graphs
• An approximation algorithm for the maximum independent set problem in cubic planar graphs
• scientific article; zbMATH DE number 6004934

Cites work

• scientific article; zbMATH DE number 3814981 (Why is no real title available?)
• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 219239 (Why is no real title available?)
• A New Parallel Algorithm for the Maximal Independent Set Problem
• A Simple Parallel Algorithm for the Maximal Independent Set Problem
• A fast and simple randomized parallel algorithm for maximal matching
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A fast parallel algorithm for the maximal independent set problem
• An improved parallel algorithm for maximal matching
• Constructing a Maximal Independent Set in Parallel
• Efficient Sequential and Parallel Algorithms for Maximal Bipartite Sets
• Fast algorithms for edge-coloring planar graphs
• Graph theory
• Matching theory

Cited in

(5)

• PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
• On parallel complexity of maximum \(f\)-matching and the degree sequence problem
• Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application.
• A simple proof that finding a maximal independent set in a graph is in NC
• The maximal f-dependent set problem for planar graphs is in NC

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q673069)