Approximating connectivity domination in weighted bounded-genus graphs

DOI10.1145/2897518.2897635zbMath1376.68171OpenAlexW2417586110MaRDI QIDQ5361863

Vincent Cohen-Addad, Claire Mathieu, David Meierfrankenfeld, Éric Colin de Verdière, Philip N. Klein

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2897518.2897635

zbMATH Keywords

graphapproximation algorithmplanar graphconnected dominating setfeedback vertex setpolynomial-time approximation schemebounded genus

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Signed and weighted graphs (05C22)

Related Items (4)

Hitting Weighted Even Cycles in Planar Graphs ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Local search is a PTAS for feedback vertex set in minor-free graphs ⋮ A Quasi-Polynomial-Time Approximation Scheme for Vehicle Routing on Planar and Bounded-Genus Graphs

This page was built for publication: Approximating connectivity domination in weighted bounded-genus graphs