The maximal f-dependent set problem for planar graphs is in NC
From MaRDI portal
Publication:673069
DOI10.1016/0304-3975(94)00112-VzbMATH Open0873.68154MaRDI QIDQ673069FDOQ673069
Authors: Zhi-Zhong Chen 
Publication date: 28 February 1997
Published in: Theoretical Computer Science (Search for Journal in Brave)
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
Cites Work
- Graph theory
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- An improved parallel algorithm for maximal matching
- A fast and simple randomized parallel algorithm for maximal matching
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
- Constructing a Maximal Independent Set in Parallel
Cited In (4)
- 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
- PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS
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)
