scientific article; zbMATH DE number 3750313

MaRDI QIDQ3933762zbMATH OpenFDO

Authors Norishige Chiba, Nobuji Saito, Takao Nishizeki

Publication date 1981

zbMATH Keywords

approximation algorithmsmaximum induced subgraph problemsmaximum matching problemminimum vertex cover problemplanar graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(9)

• A graph approximation heuristic for the vertex cover problem on planar graphs
• Perfect Matching in General vs. Cubic Graphs: A Note on the Planar and Bipartite Cases
• Minimum vertex cover in rectangle graphs
• Theory and application of width bounded geometric separators
• \(N\)-separators in planar graphs
• Separator theorem and algorithms for planar hyperbolic graphs
• Structure of polynomial-time approximation
• On approximation problems related to the independent set and vertex cover problems
• How to catch marathon cheaters: new approximation algorithms for tracking paths

This page was built for publication:

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