Parallel complexity of partitioning a planar graph into vertex-induced forests

DOI10.1016/0166-218X(96)00089-3zbMath0855.68040OpenAlexW2046693802MaRDI QIDQ1923610

Xin He, Zhi-Zhong Chen

Publication date: 3 February 1997

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(96)00089-3

zbMATH Keywords

vertex-arboricityoptimal NC algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items (6)

Some recent progress and applications in graph minor theory ⋮ Vertex-arboricity of planar graphs without intersecting triangles ⋮ On the vertex-arboricity of planar graphs ⋮ Drawing Graphs on Few Lines and Few Planes ⋮ Efficient algorithms for acyclic colorings of graphs ⋮ Vertex arboricity of planar graphs without chordal 6-cycles

Cites Work

• 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
• Optimal Parallel 5-Colouring of Planar Graphs
• The Point-Arboricity of Planar Graphs
• Acyclic colorings of planar graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: Parallel complexity of partitioning a planar graph into vertex-induced forests