Linear-Time Test for Small Face Covers in any Fixed Surface

DOI10.1137/0219063zbMATH Open0711.68056OpenAlexW2026394492MaRDI QIDQ3495650FDOQ3495650

Authors: Daniel Bienstock 

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0219063

Recommendations

• scientific article; zbMATH DE number 1256757
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• Parameterized and Exact Computation
• On obstructions to small face covers in planar graphs

zbMATH Keywords

graph algorithmspolynomial time

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cited In (2)

• On obstructions to small face covers in planar graphs
• On the Complexity of Covering Vertices by Faces in a Planar Graph

This page was built for publication: Linear-Time Test for Small Face Covers in any Fixed Surface

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