NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems

DOI10.1007/3-540-60618-1_82OpenAlexW1535329538MaRDI QIDQ6122231

Xin He, Zhi-Zhong Chen

Publication date: 28 February 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-60618-1_82

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Parallel algorithms in computer science (68W10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• An approach to the subgraph homeomorphism problem
• The point-arboricity of a graph
• On the linear vertex-arboricity of a planar graph
• Deterministic coin tossing with applications to optimal parallel list ranking
• Binary tree algebraic computation and parallel algorithms for simple graphs
• Optimal Parallel 5-Colouring of Planar Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Node-and edge-deletion NP-complete problems
• The Point-Arboricity of Planar Graphs
• Acyclic colorings of planar graphs

This page was built for publication: NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems