NC algorithms for partitioning sparse graphs into induced forests with an application

DOI10.1007/BFB0015449MaRDI QIDQ6487991zbMATH OpenFDO

Authors Zhi-Zhong Chen

Publication date 21 March 2023

Full work available at URL https://doi.org/10.1007/BFB0015449

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Parallel complexity of partitioning a planar graph into vertex-induced forests
• NC Algorithms for Recognizing Partial 2-Trees and 3-Trees
• scientific article; zbMATH DE number 1263950
• Using maximal independent sets to solve problems in parallel
• Parallel Complexity of the Connected Subgraph Problem

Cites work

• An approach to the subgraph homeomorphism problem
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Homomorphism theorems for graphs
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 742981 (Why is no real title available?)
• Node-and edge-deletion NP-complete problems
• The point-arboricity of a graph
• The Point-Arboricity of Planar Graphs

Cited in

(3)

• Deciding whether graph \(G\) has page number one is in NC
• Parallel complexity of partitioning a planar graph into vertex-induced forests
• NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems

This page was built for publication: NC algorithms for partitioning sparse graphs into induced forests with an application

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